We consider simultaneously identifying the membership and locations of point sources that are convolved with different band-limited point spread functions, from the observation of their superpositions. This problem arises in three-dimensional super-resolution single-molecule imaging, neural spike sorting, multi-user channel identification, among other applications. We propose a novel algorithm, based on convex programming, and establish its near-optimal performance guarantee for exact recovery in the noise-free setting by exploiting the spectral sparsity of the point source model as well as the incoherence between point spread functions. Furthermore, robustness of the recovery algorithm in the presence of bounded noise is also established. Numerical examples are provided to demonstrate the effectiveness of the proposed approach.
In this paper, we study the problem of super-resolving the mixture model when there are two modalities, i.e. @math . The methodology in this paper can be extended straightforwardly to the analysis of the case @math and is left for future work. We start by recognizing that in the Fourier domain, the observed signal can be regarded as a linear combination of two spectrally-sparse signals, each composed of a small number of distinct complex sinusoids. The atomic norm @cite_19 @cite_23 of spectrally-sparse signals is developed and proposed as an efficient convex optimization framework to motivate parsimonious structures @cite_26 @cite_20 @cite_23 @cite_8 @cite_5 recently, which can be computed efficiently via semidefinite programming. We then separate and recover the two signals by motivating their spectral structures using atomic norm minimization, in addition to satisfying the observation constraints. The proposed algorithm, denoted by AtomicDemix , is reminiscent of the algorithms for sparse error correction @cite_32 , robust principal component analysis @cite_36 , demixing of sines and spikes @cite_21 @cite_24 , and source separation @cite_38 , where one aims to separate two low-dimensional signals with incoherent structures via convex optimization.
@cite_38 @cite_26 @cite_8 @cite_36 @cite_21 @cite_32 @cite_24 @cite_19 @cite_23 @cite_5 @cite_20
2099641086 2096586829 2032665768 2038237443 2011677178 2064771273 2095343758 2126025632 2163973643 2172028873 2953076353 2114789426 589200591 2295566694 2041507040 2161431029 1907927509 2055064119 2114595593 2062616135
Suppose a discrete-time signal S(t), 0 spl les t<N, is a superposition of atoms taken from a combined time-frequency dictionary made of spike sequences 1 sub t= spl tau and sinusoids exp 2 spl pi iwt N spl radic N. Can one recover, from knowledge of S alone, the precise collection of atoms going to make up S? Because every discrete-time signal can be represented as a superposition of spikes alone, or as a superposition of sinusoids alone, there is no unique way of writing S as a sum of spikes and sinusoids in general. We prove that if S is representable as a highly sparse superposition of atoms from this time-frequency dictionary, then there is only one such highly sparse representation of S, and it can be obtained by solving the convex optimization problem of minimizing the l sup 1 norm of the coefficients among all decompositions. Here "highly sparse" means that N sub t +N sub w < spl radic N 2 where N sub t is the number of time atoms, N sub w is the number of frequency atoms, and N is the length of the discrete-time signal. Underlying this result is a general l sup 1 uncertainty principle which says that if two bases are mutually incoherent, no nonzero signal can have a sparse representation in both bases simultaneously. For the above setting, the bases are sinusoids and spikes, and mutual incoherence is measured in terms of the largest inner product between different basis elements. The uncertainty principle holds for a variety of interesting basis pairs, not just sinusoids and spikes. The results have idealized applications to band-limited approximation with gross errors, to error-correcting encryption, and to separation of uncoordinated sources. Related phenomena hold for functions of a real variable, with basis pairs such as sinusoids and wavelets, and for functions of two variables, with basis pairs such as wavelets and ridgelets. In these settings, if a function f is representable by a sufficiently sparse superposition of terms taken from both bases, then there is only one such sparse representation; it may be obtained by minimum l sup 1 norm atomic decomposition. The condition "sufficiently sparse" becomes a multiscale condition; for example, that the number of wavelets at level j plus the number of sinusoids in the jth dyadic frequency band are together less than a constant times 2 sup j 2 . This paper studies the problem of recovering a sparse signal x ∈ ℝn from highly corrupted linear measurements y = Ax + e ∈ ℝm, where e is an unknown error vector whose nonzero entries may be unbounded. Motivated by an observation from face recognition in computer vision, this paper proves that for highly correlated (and possibly overcomplete) dictionaries A, any sufficiently sparse signal x can be recovered by solving an l1 -minimization problem min ||x||1 + ||e||1 subject to y = Ax + e. More precisely, if the fraction of the support of the error e is bounded away from one and the support of a: is a very small fraction of the dimension m, then as m becomes large the above l1 -minimization succeeds for all signals x and almost all sign-and-support patterns of e. This result suggests that accurate recovery of sparse signals is possible and computationally feasible even with nearly 100 of the observations corrupted. The proof relies on a careful characterization of the faces of a convex polytope spanned together by the standard crosspolytope and a set of independent identically distributed (i.i.d.) Gaussian vectors with nonzero mean and small variance, dubbed the "cross-and-bouquet" (CAB) model. Simulations and experiments corroborate the findings, and suggest extensions to the result. In this paper, a novel algorithm to blindly separate an instantaneous linear underdetermined mixture of nonstationary sources is proposed. It means that the number of sources exceeds the number of channels of the available data. The separation is based on the working assumption that the sources are piecewise stationary with a different variance in each block. It proceeds in two steps: 1) estimating the mixing matrix, and 2) computing the optimum beamformer in each block to maximize the signal-to-interference ratio of each separated signal with respect to the remaining signals. Estimating the mixing matrix is accomplished through a specialized tensor decomposition of the set of sample covariance matrices of the received mixture in each block. It utilizes optimum weighting, which allows statistically efficient (CRB attaining) estimation provided that the data obey the assumed Gaussian piecewise stationary model. In simulations, performance of the algorithm is successfully tested on blind separation of 16 speech signals from nine linear instantaneous mixtures of these signals. The scope of this work is the separation of N sources from M linear mixtures when the underlying system is underdetermined, that is, when Mi N. If the input distribution is sparse the mixing matrix can be estimated either by external optimization or by clustering and, given the mixing matrix, a minimal l1 norm representation of the sources can be obtained by solving a low-dimensional linear programming problem for each of the data points. Yet, when the signals per se do not satisfy this assumption, sparsity can still be achieved by realizing the separation in a sparser transformed domain. The approach is illustrated here for M = 2. In this case we estimate both the number of sources and the mixing matrix by the maxima of a potential function along the circle of unit length, and we obtain the minimal l1 norm representation of each data point by a linear combination of the pair of basis vectors that enclose it. Several experiments with music and speech signals show that their time-domain representation is not sparse enough. Yet, excellent results were obtained using their short-time Fourier transform, including the separation of up to six sources from two mixtures. ? 2001 Elsevier Science B.V. All rights reserved. A time domain blind source separation algorithm of convolutive sound mixtures is studied based on a compact partial inversion formula in closed form. An l1-constrained minimization problem is formulated to find demixing filter coefficients for source separation while capturing scaling invariance and sparseness of solutions. The minimization aims to reduce (lagged) cross correlations of the mixture signals which are modeled stochastically. The problem is non-convex, however it is put in a nonlinear least square form where the robust and convergent Levenberg-Marquardt iterative method is applicable to compute local minimizers. Efficiency is achieved in recovering lower dimensional demixing filter solutions than the physical ones. Computations on recorded and synthetic mixtures show satisfactory performance, and are compared with other iterative methods. This paper explores the problem of spectral compressed sensing, which aims to recover a spectrally sparse signal from a small random subset of its n time domain samples. The signal of interest is assumed to be a superposition of r multidimensional complex sinusoids, while the underlying frequencies can assume any continuous values in the normalized frequency domain. Conventional compressed sensing paradigms suffer from the basis mismatch issue when imposing a discrete dictionary on the Fourier representation. To address this issue, we develop a novel algorithm, called enhanced matrix completion (EMaC), based on structured matrix completion that does not require prior knowledge of the model order. The algorithm starts by arranging the data into a low-rank enhanced form exhibiting multifold Hankel structure, and then attempts recovery via nuclear norm minimization. Under mild incoherence conditions, EMaC allows perfect recovery as soon as the number of samples exceeds the order of r log4 n, and is stable against bounded noise. Even if a constant portion of samples are corrupted with arbitrary magnitude, EMaC still allows exact recovery, provided that the sample complexity exceeds the order of r2 log3 n. Along the way, our results demonstrate the power of convex relaxation in completing a low-rank multifold Hankel or Toeplitz matrix from minimal observed entries. The performance of our algorithm and its applicability to super resolution are further validated by numerical experiments. Linear spectral unmixing aims at estimating the number of pure spectral substances, also called endmembers ,t heir spectral signatures, and their abundance fractions in remotely sensed hyperspectral images. This paper describes a method for unsupervised hyperspectral unmixing called minimum volume simplex analysis (MVSA) and introduces a new computationally efficient implementation. MVSA approaches hyperspectral un- mixing by fitting a minimum volume simplex to the hyperspec- tral data, constraining the abundance fractions to belong to the probability simplex. The resulting optimization problem, which is computationally complex, is solved in this paper by implementing a sequence of quadratically constrained subproblems using the interior point method, which is particularly effective from the computational viewpoint. The proposed implementation (available online: www.lx.it.pt 7ejun DemoMVSA.zip) is shown to exhibit state-of-the-art performance not only in terms of unmixing accu- racy, particularly in nonpure pixel scenarios, but also in terms of computational performance. Our experiments have been con- ducted using both synthetic and real data sets. An important assumption of MVSA is that pure pixels may not be present in the hyperspectral data, thus addressing a common situation in real scenarios which are often dominated by highly mixed pixels. In our experiments, we observe that MVSA yields competitive perfor- mance when compared with other available algorithms that work under the nonpure pixel regime. Our results also demonstrate that MVSA is well suited to problems involving a high number of endmembers (i.e., complex scenes) and also for problems involving a high number of pixels (i.e., large scenes). For the instrument limitation and imperfect imaging optics, it is difficult to acquire high spatial resolution hyperspectral imagery. Low spatial resolution will result in a lot of mixed pixels and greatly degrade the detection and recognition performance, affect the related application in civil and military fields. As a powerful statistical image modeling technique, sparse representation can be utilized to analyze the hyperspectral image efficiently. Hyperspectral imagery is intrinsically sparse in spatial and spectral domains, and image super-resolution quality largely depends on whether the prior knowledge is utilized properly. In this article, we propose a novel hyperspectral imagery super-resolution method by utilizing the sparse representation and spectral mixing model. Based on the sparse representation model and hyperspectral image acquisition process model, small patches of hyperspectral observations from different wavelengths can be represented as weighted linear combinations of a small number of atoms in pre-trained dictionary. Then super-resolution is treated as a least squares problem with sparse constraints. To maintain the spectral consistency, we further introduce an adaptive regularization terms into the sparse representation framework by combining the linear spectrum mixing model. Extensive experiments validate that the proposed method achieves much better results. Recent compressive sensing results show that it is possible to accurately reconstruct certain compressible signals from relatively few linear measurements via solving nonsmooth convex optimization problems. In this paper, we propose the use of the alternating direction method - a classic approach for optimization problems with separable variables (D. Gabay and B. Mercier, ?A dual algorithm for the solution of nonlinear variational problems via finite-element approximations,? Computer and Mathematics with Applications, vol. 2, pp. 17-40, 1976; R. Glowinski and A. Marrocco, ?Sur lapproximation par elements finis dordre un, et la resolution par penalisation-dualite dune classe de problemes de Dirichlet nonlineaires,? Rev. Francaise dAut. Inf. Rech. Oper., vol. R-2, pp. 41-76, 1975) - for signal reconstruction from partial Fourier (i.e., incomplete frequency) measurements. Signals are reconstructed as minimizers of the sum of three terms corresponding to total variation, ?1-norm of a certain transform, and least squares data fitting. Our algorithm, called RecPF and published online, runs very fast (typically in a few seconds on a laptop) because it requires a small number of iterations, each involving simple shrinkages and two fast Fourier transforms (or alternatively discrete cosine transforms when measurements are in the corresponding domain). RecPF was compared with two state-of-the-art algorithms on recovering magnetic resonance images, and the results show that it is highly efficient, stable, and robust. We analyze a sublinear RA@?SFA (randomized algorithm for Sparse Fourier analysis) that finds a near-optimal B-term Sparse representation R for a given discrete signal S of length N, in time and space poly(B,log(N)), following the approach given in [A.C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Near-Optimal Sparse Fourier Representations via Sampling, STOC, 2002]. Its time cost poly(log(N)) should be compared with the superlinear @W(NlogN) time requirement of the Fast Fourier Transform (FFT). A straightforward implementation of the RA@?SFA, as presented in the theoretical paper [A.C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Near-Optimal Sparse Fourier Representations via Sampling, STOC, 2002], turns out to be very slow in practice. Our main result is a greatly improved and practical RA@?SFA. We introduce several new ideas and techniques that speed up the algorithm. Both rigorous and heuristic arguments for parameter choices are presented. Our RA@?SFA constructs, with probability at least 1-@d, a near-optimal B-term representation R in time poly(B)log(N)log(1 @d) @e^2log(M) such that @?S-R@?"2^2=<(1+@e)@?S-R"o"p"t@?"2^2. Furthermore, this RA@?SFA implementation already beats the FFTW for not unreasonably large N. We extend the algorithm to higher dimensional cases both theoretically and numerically. The crossover point lies at N 70,000 in one dimension, and at N 900 for data on a NxN grid in two dimensions for small B signals where there is noise. This paper provides novel results for the recovery of signals from undersampled measurements based on analysis @math -minimization, when the analysis operator is given by a frame. We both provide so-called uniform and nonuniform recovery guarantees for cosparse (analysis-sparse) signals using Gaussian random measurement matrices. The nonuniform result relies on a recovery condition via tangent cones and the uniform recovery guarantee is based on an analysis version of the null space property. Examining these conditions for Gaussian random matrices leads to precise bounds on the number of measurements required for successful recovery. In the special case of standard sparsity, our result improves a bound due to Rudelson and Vershynin concerning the exact reconstruction of sparse signals from Gaussian measurements with respect to the constant and extends it to stability under passing to approximately sparse signals and to robustness under noise on the measurements. We consider the problem of robustly recovering a @math -sparse coefficient vector from the Fourier series that it generates, restricted to the interval @math . The difficulty of this problem is linked to the superresolution factor SRF, equal to the ratio of the Rayleigh length (inverse of @math ) by the spacing of the grid supporting the sparse vector. In the presence of additive deterministic noise of norm @math , we show upper and lower bounds on the minimax error rate that both scale like @math , providing a partial answer to a question posed by Donoho in 1992. The scaling arises from comparing the noise level to a restricted isometry constant at sparsity @math , or equivalently from comparing @math to the so-called @math -spark of the Fourier system. The proof involves new bounds on the singular values of restricted Fourier matrices, obtained in part from old techniques in complex analysis. Neural recordings, returns from radars and sonars, images in astronomy and single-molecule microscopy can be modeled as a linear superposition of a small number of scaled and delayed copies of a band-limited or diffraction-limited point spread function, which is either determined by the nature or designed by the users; in other words, we observe the convolution between a point spread function and a sparse spike signal with unknown amplitudes and delays. While it is of great interest to accurately resolve the spike signal from as few samples as possible, however, when the point spread function is not known a priori, this problem is terribly ill-posed. This paper proposes a convex optimization framework to simultaneously estimate the point spread function as well as the spike signal, by mildly constraining the point spread function to lie in a known low-dimensional subspace. By applying the lifting trick, we obtain an underdetermined linear system of an ensemble of signals with joint spectral sparsity, to which atomic norm minimization is applied. Under mild randomness assumptions of the low-dimensional subspace as well as a separation condition of the spike signal, we prove the proposed algorithm, dubbed as AtomicLift, is guaranteed to recover the spike signal up to a scaling factor as soon as the number of samples is large enough. The extension of AtomicLift to handle noisy measurements is also discussed. Numerical examples are provided to validate the effectiveness of the proposed approaches. In Part I of this paper, we proposed and analyzed a novel algorithmic framework for the minimization of a nonconvex (smooth) objective function, subject to nonconvex constraints, based on inner convex approximations. This Part II is devoted to the application of the framework to some resource allocation problems in communication networks. In particular, we consider two non-trivial case-study applications, namely: (generalizations of) i) the rate profile maximization in MIMO interference broadcast networks; and the ii) the max-min fair multicast multigroup beamforming problem in a multi-cell environment. We develop a new class of algorithms enjoying the following distinctive features: i) they are across the base stations (with limited signaling) and lead to subproblems whose solutions are computable in closed form; and ii) differently from current relaxation-based schemes (e.g., semidefinite relaxation), they are proved to always converge to d-stationary solutions of the aforementioned class of nonconvex problems. Numerical results show that the proposed (distributed) schemes achieve larger worst-case rates (resp. signal-to-noise interference ratios) than state-of-the-art centralized ones while having comparable computational complexity. We investigate a compressive sensing framework in which the sensors introduce a distortion to the measurements in the form of unknown gains. We focus on blind calibration, using measures performed on multiple unknown (but sparse) signals and formulate the joint recovery of the gains and the sparse signals as a convex optimization problem. We divide this problem in 3 sub-problems with different conditions on the gains, specifially i) gains with different amplitude and the same phase, ii) gains with the same amplitude and different phase and iii) gains with different amplitude and phase. In order to solve the first case, we propose an extension to the basis pursuit optimization which can estimate the unknown gains along with the unknown sparse signals. For the second case, we formulate a quadratic approach that eliminates the unknown phase shifts and retrieves the unknown sparse signals. An alternative form of this approach is also formulated to reduce complexity and memory requirements and provide scalability with respect to the number of input signals. Finally for the third case, we propose a formulation that combines the earlier two approaches to solve the problem. The performance of the proposed algorithms is investigated extensively through numerical simulations, which demonstrates that simultaneous signal recovery and calibration is possible with convex methods when sufficiently many (unknown, but sparse) calibrating signals are provided. This paper considers constrained lscr1 minimization methods in a unified framework for the recovery of high-dimensional sparse signals in three settings: noiseless, bounded error, and Gaussian noise. Both lscr1 minimization with an lscrinfin constraint (Dantzig selector) and lscr1 minimization under an llscr2 constraint are considered. The results of this paper improve the existing results in the literature by weakening the conditions and tightening the error bounds. The improvement on the conditions shows that signals with larger support can be recovered accurately. In particular, our results illustrate the relationship between lscr1 minimization with an llscr2 constraint and lscr1 minimization with an lscrinfin constraint. This paper also establishes connections between restricted isometry property and the mutual incoherence property. Some results of Candes, Romberg, and Tao (2006), Candes and Tao (2007), and Donoho, Elad, and Temlyakov (2006) are extended. In recent years analysis of complexity of learning Gaussian mixture models from sampled data has received significant attention in computational machine learning and theory communities. In this paper we present the first result showing that polynomial time learning of multidimensional Gaussian Mixture distributions is possible when the separation between the component means is arbitrarily small. Specifically, we present an algorithm for learning the parameters of a mixture of k identical spherical Gaussians in n-dimensional space with an arbitrarily small separation between the components, which is polynomial in dimension, inverse component separation and other input parameters for a fixed number of components k. The algorithm uses a projection to k dimensions and then a reduction to the 1-dimensional case. It relies on a theoretical analysis showing that two 1-dimensional mixtures whose densities are close in the L norm must have similar means and mixing coefficients. To produce the necessary lower bound for the L norm in terms of the distances between the corresponding means, we analyze the behavior of the Fourier transform of a mixture of Gaussians in one dimension around the origin, which turns out to be closely related to the properties of the Vandermonde matrix obtained from the component means. Analysis of minors of the Vandermonde matrix together with basic function approximation results allows us to provide a lower bound for the norm of the mixture in the Fourier domain and hence a bound in the original space. Additionally, we present a separate argument for reconstructing variance. This paper improves upon best-known guarantees for exact reconstruction of a sparse signal f from a small universal sample of Fourier measurements. The method for reconstruction that has recently gained momentum in the sparse approximation theory is to relax this highly nonconvex problem to a convex problem and then solve it as a linear program. We show that there exists a set of frequencies Ω such that one can exactly reconstruct every r-sparse signal f of length n from its frequencies in Ω, using the convex relaxation, and Ω has size k(r, n) = O(r log(n)·log 2 (r) log(r logn)) = O(r log 4 n ). A random set Ω satisfies this with high probability. This estimate is optimal within the log log n and log 3 r factors. We also give a relatively short argument for a similar problem with k(r, n) ≈ r[12 + 8 log(n r)] Gaussian measurements. We use methods of geometric functional analysis and probability theory in Banach spaces, which makes our arguments quite short. Given a dictionary that consists of multiple blocks and a signal that lives in the range space of only a few blocks, we study the problem of finding a block-sparse representation of the signal, i.e., a representation that uses the minimum number of blocks. Motivated by signal image processing and computer vision applications, such as face recognition, we consider the block-sparse recovery problem in the case where the number of atoms in each block is arbitrary, possibly much larger than the dimension of the underlying subspace. To find a block-sparse representation of a signal, we propose two classes of nonconvex optimization programs, which aim to minimize the number of nonzero coefficient blocks and the number of nonzero reconstructed vectors from the blocks, respectively. Since both classes of problems are NP-hard, we propose convex relaxations and derive conditions under which each class of the convex programs is equivalent to the original nonconvex formulation. Our conditions depend on the notions of mutual and cumulative subspace coherence of a dictionary, which are natural generalizations of existing notions of mutual and cumulative coherence. We evaluate the performance of the proposed convex programs through simulations as well as real experiments on face recognition. We show that treating the face recognition problem as a block-sparse recovery problem improves the state-of-the-art results by 10 with only 25 of the training data. Abstract We present a sublinear randomized algorithm to compute a sparse Fourier transform for nonequispaced data of a special type. More precisely, we address the situation where a signal S is known to consist of N equispaced time samples, of which only L N samples are available. If the ratio p = L N is much smaller than 1, the available data typically look like nonequispaced samples, with little or no visible trace of the equispacing of the full set of N samples. We extend an approach for equispaced data that was presented in [J. Zou, A.C. Gilbert, M. Strauss, I. Daubechies, Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis, J. Comput. Phys. 211 (2006) 572–595]; the extended algorithm reconstructs, from the incomplete data, a near-optimal B-term representation R with high probability 1 − δ , in time and space poly ( B , log ( N ) , log ( 1 δ ) , e −1 ) , such that ‖ S − R ‖ 2 2 ⩽ ( 1 + e ) ‖ S − R opt B ‖ 2 2 , where R opt B is the optimal B-term Fourier representation of signal S. The sublinear poly ( log N ) time is compared to the superlinear O ( L 1 + ( d − 1 ) β log L ) time requirement of the present best known inverse nonequispaced fast Fourier transform (INFFT) algorithms, in the sense of weighted norm with the number of dimensions d and smoothness parameter β. Numerical experiments support the advantage of our algorithm in speed over other methods for sparse signals: it already outperforms the INFFT for large but realistic size N and works well even in the situation of a large percentage of missing data and in the presence of large noise.