This paper aims to provide a new perspective on understanding the resolution limit by examining a recently proposed spectrum estimator based on the Christoffel-Darboux Kernel. Different from other estimators, this estimator possesses a definite criterion of resolvability building on the well known Szegö extremum on the unit circle and the source estimates are allowed to merge. For a uniform linear array of length M and two uncorrelated sources, we show that there is a sharp transition of the limiting extremum at a separation of order O(M–1.5). Our result sheds light on understanding the fundamental difference between on-grid and gridless models, the meaning of super-resolution region, and the benefit of sparse arrays that have been widely exploited in recent literature.

Sparse support recovery from multiple measurement vectors is studied in this paper. Instead of using any relaxations, we impose the explicit ℓ0-norm constraint and propose to identify the joint sparse support in the correlation domain. We simultaneously bound the prediction and parameter estimation errors of three algorithms with and without additional ℓq-norm (q = 1, 2) based regularization besides the ℓ0-norm constraint. Our analysis is in sharp contrast to the prior random sampling based results as our measurement matrix is deterministic Fourier and available technical arguments will not apply. Moreover, the error bounds are derived without any restriction on the tuning parameters’ ranges. The numerical implementations are carried out with customized branch and bound algorithms capable of enforcing discrete constraints.

This letter considers the estimation of block sparse signal with unknown partition. We take a variational approach to separate the estimates of support partition and signal amplitudes. Instead of using any surrogate, we propose to apply the exact$\ell _{0}$-norm constraint to promote the desired block sparsity. As for the companion algorithmic design, we exploit the ADMM framework to iteratively update our partition and signal estimates. Our main contribution lies in the novel convergence guarantee of the proposed non-convex and non-smooth ADMM algorithm. The insight brought up by our theoretical analysis sheds light on other programs involving$\ell _{0}$-norm constraints. The superior performance of the proposed method is empirically demonstrated by extensive experiments with the state-of-art competing methods.

Separation-aware super resolution algorithms are studied in this paper. Motivated by the optics applications, we consider the mixture model of Airy disks, and propose to develop general mapping operators that can enforce a specific separation constraint. The proposed operators can work with existing algorithms, and bridge the gap in prior works that the separation is only assumed in theoretical analysis while not exploited in algorithmic designs. The performance of the operators is theoretically analyzed and demonstrated by numerical experiments under both one and two dimensional settings.

This paper studies the problem of discrete super-resolution. Existing stability guarantees rely on the fact that certain separation conditions are satisfied by the true support. However, such structural conditions have not been exploited in the corresponding algorithmic designs. This paper proposes a novel Bayesian approach based on the model aggregation idea that can generate an exact sparse estimate, and maintain the required structures of the support. The proposed method is implemented within the MCMC framework and empirically provides better support recovery than available algorithms.

Sparse support recovery from multiple measurement vectors (MMV) is studied in this paper. For years, a noticeable mismatch exists between the theories and algorithms in the research of super-resolution and direction-of-arrival (DOA) estimation that variants of separation conditions are assumed to ensure stable recovery while the corresponding algorithms rarely exploit such structural constraints. Due to the discrete nature of the separation condition, we propose to incorporate such prior information in a Mixed Integer Programming (MIP) problem with an$\ell _{0}$-based constraint. We develop a specialized branch and bound (B&B) algorithm that can efficiently exploit the separation prior with guaranteed complexity reduction. Moreover, we show that computational complexity can be further reduced by leveraging the sparse array idea along with a particular perspective formulation of the MIP. The superior performance of the proposed algorithm is demonstrated via numerical experiments.

Exact sparse support recovery from noisy deterministic Fourier measurements is studied in this paper. The ideal$\ell _{0}$-regularized least squares (LS) program is known to have strict local minimizers for multiple sparse supports. By applying a specific non-convex surrogate of the$\ell _{0}$-regularizer, we show that, under certain conditions, the set of local minimizers with particularly separated supports is a singleton. Thus, any converging algorithms that can enforce the corresponding separation constraint will lead to the true support as the unique solution. In this regard, we construct a novel optimal mapping operator that can fulfill the separation condition, and several empirically effective algorithms are developed. The simulation results demonstrate the theoretical claims made in this paper.

This paper studies the overfitting in discrete super-resolution problem. In particular, we solve for the estimate that simply overfits the noisy measurements. By doing this, we no longer require the prior knowledge of additive noise to set the parameter of sparse reconstruction algorithm to ensure the feasibility of target signal. The analysis of overfitting is based on a new proof of the quotient property of deterministic Fourier measurement matrix as well as a novel insight of the widely used interpolation-based proof technique in super-resolution literature. Our theoretical result shows that a similar stability guarantee holds for the overfitting algorithm as those for nonoverfitting ones. The derived error bound is demonstrated by the numerical experiments.

This letter considers the performance of the SPICE method in the context of line spectrum estimation by exploiting its equivalent square-root lasso (SR-LASSO) representation established in previous work. The inefficiencies of existing analyses are that the guarantees are not applicable to deterministic Fourier measurement matrices, and the studied range of the tuning parameter excludes the SR-LASSO formulation of the SPICE method. The key observation of this letter is that, for a particular range of tuning parameter, the solutions which overfit the noisy measurements are valid SR-LASSO solutions. Based on this observation, we propose to analyze these overfitting solutions and derive the condition of exact on-grid source localization that is applicable to the SPICE method. The numerical experiments demonstrate our theoretical claims.

Computer usage behaviour information can be used by anomaly detection algorithms to identify the current user of the computer system for security reasons. However, the data collected in this setup can be binary and very sparse, resulting in poor performance for some widely used anomaly detection methods. In this study, we propose a novel reconstruction criterion inspired by the F1score and the cross-entropy loss, that tackles the class imbalance problem introduced by binary and sparse data distribution with effectively merging reconstruction criterion calculated from vector elements of both positive and negative classes. Our experiments show that the proposed criterion can effectively improve the performance of reconstruction based anomaly detection methods, including both the PCA and the autoencoder.

This paper considers the problem of lower bounding the mean-squared-error (MSE) of unbiased super-resolution estimates. In literature, only upper bounds on the MSE are available which scale with the so-called super-resolution factor (SRF). However, the upper bound does not indicate whether the MSE indeed exhibits noise amplification that increases with the target resolution. The main contribution of this paper is to derive the Cramér-Rao Bound for noisy super- resolution problem and understand its scaling as a function of the super-resolution factor. We compare our lower bound with the upper bound established in prior work and show that the dependency of MSE on SRF is fundamental. Our analysis can be applied to other unbiased estimates in the problem of super-resolution. Numerical experiments are conducted to demonstrate our theoretical claims.

This paper considers the problem of estimating the number of sinusoidal signals in additive sub-Gaussian noise. We develop a novel non-asymptotic analysis of the eigenvalues of a Hermitian Toeplitz data matrix with finite noisy measurements. With this analysis, we propose a new threshold-based estimation algorithm which is guaranteed to correctly recover the true source number with high probability under certain conditions. The analysis is applicable to any independent sub-Gaussian additive noise. In particular, exact knowledge of the likelihood function is not needed and the noise terms may not be identically distributed. The theoretical claims are demonstrated by extensive numerical experiments.

This leter develops a universal technique for analyzing discrete super-resolution algorithms with ℓ1-norm based objective function. Though the super-resolution problem with sparsity constraints is of intense research interest in the past decade, only a modified Dantzig selector has been non-asymptotically analyzed without additional structural information whereas this theoretical guarantee does not match the numerical results in the Gaussian noise case. More importantly, the relation between the analyses of discrete super-resolution problem and other underdetermined inverse problems in compressed sensing is still not clear. Using the proposed universal technique, this letter aims to close this gap in understanding the characteristics of discrete super-resolution problem. The theoretical claims are demonstrated by extensive numerical experiments.

This paper considers the problem of super-resolution reconstruction by casting it as an optimization problem with positive constraints and non-convex objective function. Enforcing the solution to be simultaneously sparse and non-negative naturally leads to a non-convex l1/2quasinorm minimization problem. A reweighted l1norm minimization algorithm is proposed to solve this problem, which is tailored for l1/2quasinorm minimization using the idea of Majorization-Minimization. Although the problem is non-convex and non-smooth, and the measurement matrix does not satisfy restricted isometry conditions, we are able to obtain deterministic stable reconstruction guarantees in presence of bounded noise by using the structure of the measurement matrix and non-negativity of the signal. Numerical results demonstrate that l1/2minimization promotes sparser solution and outperforms l1minimization.

This paper considers the problem of super-resolution with positive constraints. By utilizing the concept of Modulus of Continuity (MC), we propose a unified framework for analyzing the robustness of super-resolution reconstruction in presence of noise, which is algorithm-independent and emphasizes the role of signal structures. In contrast to earlier works, we show that incorporation of positive constraints improves the scaling factor of MC and provides tighter upper bound on the estimation error of any algorithm that exploits such structure. The unified framework is further applied to analyze convex algorithms for positive super-resolution, and the theoretical results are validated by numerical experiments.

This paper considers the problem of co-array interpolation for direction-of-arrival (DOA) estimation with sparse nonuniform arrays. By utilizing the much longer difference co-array associated with these arrays, it is possible to perform DOA estimation of more sources than sensors. Since the co-array may contain holes (or missing lags), interpolation algorithms have been proposed to fully utilize the remaining elements of the co-array beyond that captured in the contiguous ULA segment. However, the quality and stability of interpolation performed by such algorithms (especially in presence of modeling errors) have not been analyzed. This paper provides a unified analysis of co-array interpolation algorithms to bound the interpolation error in terms of modeling errors. The results are universal in the sense that they can be applied to analyze any algorithm that utilizes the positive semidefinite (PSD) structure of the interpolated covariance matrix. The general framework is then applied to analyze specific algorithms and simulations are conducted to study their interpolation errors.

This letter offers several new insights into the maximum-likelihood direction-of-arrival (DOA) estimation problem, when the number of sources exceeds the number of sensors. Two maximum-likelihood problems are studied: one for estimating the Toeplitz-structured coarray covariance matrix from the measurements, and the other for estimating the DOAs directly from the measurements. We establish the equivalence of both problems when the number of sources is assumed to be unknown and can potentially exceed the number of sensors. Additionally, it is shown that when the source waveforms satisfy certain orthogonality conditions, the Toeplitz-constrained maximum-likelihood covariance estimation framework provably produces the true DOAs without requiring to know the number of sources. When the number of sources exceeds the number of sensors, the maximum-likelihood algorithms studied in this letter outperform other recently studied methods, as demonstrated through numerical experiments.

The problem of sparse phase retrieval is considered where the goal is to recover a sparse complex valued vector (with s non zero elements) from the magnitudes of its linear measurements. Using a modified and partially randomized version of a newly proposed structured sampler, namely the Partial Nested Fourier Sampler (PNFS), it is shown to be possible to recover the unknown signal (up to a global phase ambiguity) from O(s log N) phaseless measurements where N is the dimension of the vector. The reconstruction is based on a novel idea of "decoupling" certain quadratic terms in the phaseless measurements acquired by the PNFS, leading to a simple l1-minimization-based recovery algorithm, without the need for "lifting" the unknown variable to a higher dimensional space. The proposed algorithm is also proved to be stable in presence of bounded noise.

This paper considers the problem of compressively sampling wide sense stationary random vectors with a low rank Toeplitz correlation matrix. A new structured deterministic sampling method known as the “Generalized Nested Sampling” (GNS) is used to fully exploit the inherent redundancy of low rank Toeplitz matrices. For a Toeplitz matrix of size N ×N with rank r, this sampling scheme uses only O(√r) measurements and allows exact recovery from noiseless measurements. This compression factor is independent of N and is shown to be larger than that achieved by existing random sampling based techniques for compressing Toeplitz matrices. The recovery procedure exploits the connection between Toeplitz matrices and linear prediction.