Polynomial Approximation, Local Polynomial convexity, and Degenerate CR Singularities- II

We provide some conditions for the graph of a Holder-continuous function on (D) over bar, where (D) over bar is a closed disk in C, to be polynomially convex. Almost all sufficient conditions known to date - provided the function (say F) is smooth - arise from versions of the Weierstrass Approximation Theorem on (D) over bar. These conditions often fail to yield any conclusion if rank(R)DF is not maximal on a sufficiently large subset of (D) over bar. We bypass this difficulty by introducing a technique that relies on the interplay of certain plurisubharmonic functions. This technique also allows us to make some observations on the polynomial hull of a graph in C(2) at an isolated complex tangency.

Signal tracking approach for phase estimation in digital holographic interferometry

In this research work, we introduce a novel approach for phase estimation from noisy reconstructed interference fields in digital holographic interferometry using an unscented Kalman filter. Unlike conventionally used unwrapping algorithms and piecewise polynomial approximation approaches, this paper proposes, for the first time to the best of our knowledge, a signal tracking approach for phase estimation. The state space model derived in this approach is inspired from the Taylor series expansion of the phase function as the process model, and polar to Cartesian conversion as the measurement model. We have characterized our approach by simulations and validated the performance on experimental data (holograms) recorded under various practical conditions. Our study reveals that the proposed approach, when compared with various phase estimation methods available in the literature, outperforms at lower SNR values (i.e., especially in the range 0-20 dB). It is demonstrated with experimental data as well that the proposed approach is a better choice for estimating rapidly varying phase with high dynamic range and noise. (C) 2014 Optical Society of America

Extrinsic Analog Synthesis using Piecewise Linear Current-Mode Circuits

A methodology is presented for the synthesis of analog circuits using piecewise linear (PWL) approximations. The function to be synthesized is divided into PWL segments such that each segment can be realized using elementary MOS current-mode programmable-gain circuits. A number of these elementary current-mode circuits when connected in parallel, it is possible to realize piecewise linear approximation of any arbitrary analog function with in the allowed approximation error bounds. Simulation results show a close agreement between the desired function and the synthesized output. The number of PWL segments used for approximation and hence the circuit area is determined by the required accuracy and the smoothness of the resulting function.

The transient response of certain third-ordernon-linear systems

In this paper a method of solving certain third-order non-linear systems by using themethod of ultraspherical polynomial approximation is proposed. By using the method of variation of parameters the third-order equation is reduced to three partial differential equations. Instead of being averaged over a cycle, the non-linear functions are expanded in ultraspherical polynomials and with only the constant term retained, the equations are solved. The results of the procedure are compared with the numerical solutions obtained on a digital computer. A degenerate third-order system is also considered and results obtained for the above system are compared with numerical results obtained on the digital computer. There is good agreement between the results obtained by the proposed method and the numerical solution obtained on digital computer.

Application of ultraspherical polynomials to forced oscillations of a third-order non-linear system

In this paper the method of ultraspherical polynomial approximation is applied to study the steady-state response in forced oscillations of a third-order non-linear system. The non-linear function is expanded in ultraspherical polynomials and the expansion is restricted to the linear term. The equation for the response curve is obtained by using the linearized equation and the results are presented graphically. The agreement between the approximate solution and the analog computer solution is satisfactory. The problem of stability is not dealt with in this paper.

Transient response of coupled non-linear non-conservative systems

This paper deals with an approximate method of analysis of non-linear, non-conservative systems of two degrees of freedom. The approximate equations for amplitude and phase are obtained by a generalized averaging technique based on the ultraspherical polynomial approximation. The method is illustrated by an example of a spring-mass-damper system.

Kernels for large margin time-series classification

In this paper we propose a novel family of kernels for multivariate time-series classification problems. Each time-series is approximated by a linear combination of piecewise polynomial functions in a Reproducing Kernel Hilbert Space by a novel kernel interpolation technique. Using the associated kernel function a large margin classification formulation is proposed which can discriminate between two classes. The formulation leads to kernels, between two multivariate time-series, which can be efficiently computed. The kernels have been successfully applied to writer independent handwritten character recognition.

Can one electrochemically measure the statistical morphology of a rough electrode

We have developed a theory for an electrochemical way of measuring the statistical properties of a nonfractally rough electrode. We obtained the expression for the current transient on a rough electrode which shows three times regions: short and long time limits and the transition region between them. The expressions for these time ranges are exploited to extract morphological information about the surface roughness. In the short and long time regimes, we extract information regarding various morphological features like the roughness factor, average roughness, curvature, correlation length, dimensionality of roughness, and polynomial approximation for the correlation function. The formulas for the surface structure factors (the measure of surface roughness) of rough surfaces in terms of measured reversible and diffusion-limited current transients are also obtained. Finally, we explore the feasibility of making such measurements.

Nonlinear static and dynamic damped response of a composite rectangular plate resting on a two-parameter elastic foundation

Nonlinear static and dynamic response analyses of a clamped. rectangular composite plate resting on a two-parameter elastic foundation have been studied using von Karman's relations. Incorporating the material damping, the governing coupled, nonlinear partial differential equations are obtained for the plate under step pressure pulse load excitation. These equations have been solved by a one-term solution and by applying Galerkin's technique to the deflection equation. This yields an ordinary nonlinear differential equation in time. The nonlinear static solution is obtained by neglecting the time-dependent variables. Thc nonlinear dynamic damped response is obtained by applying the ultraspherical polynomial approximation (UPA) technique. The influences of foundation modulus, shear modulus, orthotropy, etc. upon the nonlinear static and dynamic responses have been presented.

On the Selection of Optimum Savitzky-Golay Filters

Savitzky-Golay (S-G) filters are finite impulse response lowpass filters obtained while smoothing data using a local least-squares (LS) polynomial approximation. Savitzky and Golay proved in their hallmark paper that local LS fitting of polynomials and their evaluation at the mid-point of the approximation interval is equivalent to filtering with a fixed impulse response. The problem that we address here is, ``how to choose a pointwise minimum mean squared error (MMSE) S-G filter length or order for smoothing, while preserving the temporal structure of a time-varying signal.'' We solve the bias-variance tradeoff involved in the MMSE optimization using Stein's unbiased risk estimator (SURE). We observe that the 3-dB cutoff frequency of the SURE-optimal S-G filter is higher where the signal varies fast locally, and vice versa, essentially enabling us to suitably trade off the bias and variance, thereby resulting in near-MMSE performance. At low signal-to-noise ratios (SNRs), it is seen that the adaptive filter length algorithm performance improves by incorporating a regularization term in the SURE objective function. We consider the algorithm performance on real-world electrocardiogram (ECG) signals. The results exhibit considerable SNR improvement. Noise performance analysis shows that the proposed algorithms are comparable, and in some cases, better than some standard denoising techniques available in the literature.

Robust Savitzky-Golay Filters

Local polynomial approximation of data is an approach towards signal denoising. Savitzky-Golay (SG) filters are finite-impulse-response kernels, which convolve with the data to result in polynomial approximation for a chosen set of filter parameters. In the case of noise following Gaussian statistics, minimization of mean-squared error (MSE) between noisy signal and its polynomial approximation is optimum in the maximum-likelihood (ML) sense but the MSE criterion is not optimal for non-Gaussian noise conditions. In this paper, we robustify the SG filter for applications involving noise following a heavy-tailed distribution. The optimal filtering criterion is achieved by l(1) norm minimization of error through iteratively reweighted least-squares (IRLS) technique. It is interesting to note that at any stage of the iteration, we solve a weighted SG filter by minimizing l(2) norm but the process converges to l(1) minimized output. The results show consistent improvement over the standard SG filter performance.

Polynomial time and parameterized approximation algorithms for boxicity

The boxicity (cubicity) of a graph G, denoted by box(G) (respectively cub(G)), is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (cubes) in ℝ k . The problem of computing boxicity (cubicity) is known to be inapproximable in polynomial time even for graph classes like bipartite, co-bipartite and split graphs, within an O(n 0.5 − ε ) factor for any ε > 0, unless NP = ZPP. We prove that if a graph G on n vertices has a clique on n − k vertices, then box(G) can be computed in time n22O(k2logk) . Using this fact, various FPT approximation algorithms for boxicity are derived. The parameter used is the vertex (or edge) edit distance of the input graph from certain graph families of bounded boxicity - like interval graphs and planar graphs. Using the same fact, we also derive an O(nloglogn√logn√) factor approximation algorithm for computing boxicity, which, to our knowledge, is the first o(n) factor approximation algorithm for the problem. We also present an FPT approximation algorithm for computing the cubicity of graphs, with vertex cover number as the parameter.

Approximation algorithm for maximum independent set in planar traingle-free graphs

The maximum independent set problem is NP-complete even when restricted to planar graphs, cubic planar graphs or triangle free graphs. The problem of finding an absolute approximation still remains NP-complete. Various polynomial time approximation algorithms, that guarantee a fixed worst case ratio between the independent set size obtained to the maximum independent set size, in planar graphs have been proposed. We present in this paper a simple and efficient, O(|V|) algorithm that guarantees a ratio 1/2, for planar triangle free graphs. The algorithm differs completely from other approaches, in that, it collects groups of independent vertices at a time. Certain bounds we obtain in this paper relate to some interesting questions in the theory of extremal graphs.

Design of multiunit electronic exchanges through decomposition

In this paper, we exploit the idea of decomposition to match buyers and sellers in an electronic exchange for trading large volumes of homogeneous goods, where the buyers and sellers specify marginal-decreasing piecewise constant price curves to capture volume discounts. Such exchanges are relevant for automated trading in many e-business applications. The problem of determining winners and Vickrey prices in such exchanges is known to have a worst-case complexity equal to that of as many as (1 + m + n) NP-hard problems, where m is the number of buyers and n is the number of sellers. Our method proposes the overall exchange problem to be solved as two separate and simpler problems: 1) forward auction and 2) reverse auction, which turns out to be generalized knapsack problems. In the proposed approach, we first determine the quantity of units to be traded between the sellers and the buyers using fast heuristics developed by us. Next, we solve a forward auction and a reverse auction using fully polynomial time approximation schemes available in the literature. The proposed approach has worst-case polynomial time complexity. and our experimentation shows that the approach produces good quality solutions to the problem. Note to Practitioners- In recent times, electronic marketplaces have provided an efficient way for businesses and consumers to trade goods and services. The use of innovative mechanisms and algorithms has made it possible to improve the efficiency of electronic marketplaces by enabling optimization of revenues for the marketplace and of utilities for the buyers and sellers. In this paper, we look at single-item, multiunit electronic exchanges. These are electronic marketplaces where buyers submit bids and sellers ask for multiple units of a single item. We allow buyers and sellers to specify volume discounts using suitable functions. Such exchanges are relevant for high-volume business-to-business trading of standard products, such as silicon wafers, very large-scale integrated chips, desktops, telecommunications equipment, commoditized goods, etc. The problem of determining winners and prices in such exchanges is known to involve solving many NP-hard problems. Our paper exploits the familiar idea of decomposition, uses certain algorithms from the literature, and develops two fast heuristics to solve the problem in a near optimal way in worst-case polynomial time.

Hardness of approximation results for the problem of finding the stopping distance in Tanner graphs

Tanner Graph representation of linear block codes is widely used by iterative decoding algorithms for recovering data transmitted across a noisy communication channel from errors and erasures introduced by the channel. The stopping distance of a Tanner graph T for a binary linear block code C determines the number of erasures correctable using iterative decoding on the Tanner graph T when data is transmitted across a binary erasure channel using the code C. We show that the problem of finding the stopping distance of a Tanner graph is hard to approximate within any positive constant approximation ratio in polynomial time unless P = NP. It is also shown as a consequence that there can be no approximation algorithm for the problem achieving an approximation ratio of 2(log n)(1-epsilon) for any epsilon > 0 unless NP subset of DTIME(n(poly(log n))).