Search

The presence of missing entries in data often creates challenges for pattern recognition algorithms. Traditional algorithms for clustering data assume that all the feature values are known for every data point. We propose a method to cluster data in the presence of missing information. Unlike conventional clustering techniques where every feature is known for each point, our algorithm can handle cases where a few feature values are unknown for every point. For this more challenging problem, we provide theoretical guarantees for clustering using a $l_0$ fusion penalty based optimization problem. Furthermore, we propose an algorithm to solve a relaxation of this problem using saturating non-convex fusion penalties. It is observed that this algorithm produces solutions that degrade gradually with an increase in the fraction of missing feature values. We demonstrate the utility of the proposed method using a simulated dataset, the Wine dataset and the ASL dataset. It is shown that the proposed method is a promising clustering technique for datasets with large fractions of missing entries. [ABSTRACT FROM AUTHOR]

The main focus of this paper is to derive a memory efficient approximation to the nonuniform Fourier transform of a support limited sequence. We show that the standard nonuniform fast Fourier transform (NUFFT) scheme is a shift invariant approximation of the exact Fourier transform. Based on the theory of shift-invariant representations, we derive an exact expression for the worst-case mean square approximation error. Using this metric, we evaluate the optimal scale-factors and the interpolator that provides the least approximation error. We also derive the upper-bound for the error component due to the lookup table based evaluation of the interpolator; we use this metric to ensure that this component is not the dominant one. Theoretical and experimental comparisons with standard NUFFT schemes clearly demonstrate the significant improvement in accuracy over conventional schemes, especially when the size of the uniform fast Fourier transform (FFT) is small. Since the memory requirement of the algorithm is dependent on the size of the uniform FFT, the proposed developments can lead to iterative signal reconstruction algorithms with significantly lower memory demands. [ABSTRACT FROM AUTHOR]

Presents an expression for the L[sub2] error that occurs when one approximates a periodic signal in a basis of shifted and scaled versions of a generating function. Overview of classical sampling theory; Fourier series representation; Computation of the square error; Experimental verification of the error formula.

We introduce a continuous domain framework for the recovery of a planar curve from a few samples. We model the curve as the zero level set of a trigonometric polynomial. We show that the exponential feature maps of the points on the curve lie on a low-dimensional subspace. We show that the null-space vector of the feature matrix can be used to uniquely identify the curve, given a sufficient number of samples. The worst-case theoretical guarantees show that the number of samples required for unique recovery depends on the bandwidth of the underlying trigonometric polynomial, which is a measure of the complexity of the curve. We introduce an iterative algorithm that relies on the low-rank property of the feature maps to recover the curves when the samples are noisy or when the true bandwidth of the curve is unknown. We also demonstrate the preliminary utility of the proposed curve representation in the context of image segmentation. [ABSTRACT FROM AUTHOR]

We consider the recovery of a continuous domain piecewise constant image from its nonuniform Fourier samples using a convex matrix completion algorithm. We assume the discontinuities/edges of the image are localized to the zero level set of a bandlimited function. This assumption induces linear dependencies between the Fourier coefficients of the image, which results in a two-fold block Toeplitz matrix constructed from the Fourier coefficients being low rank. The proposed algorithm reformulates the recovery of the unknown Fourier coefficients as a structured low-rank matrix completion problem, where the nuclear norm of the matrix is minimized subject to structure and data constraints. We show that the exact recovery is possible with high probability when the edge set of the image satisfies an incoherency property. We also show that the incoherency property is dependent on the geometry of the edge set curve, implying higher sampling burden for smaller curves. This paper generalizes recent work on the super-resolution recovery of isolated Diracs or signals with finite rate of innovation to the recovery of piecewise constant images. [ABSTRACT FROM AUTHOR]