Covariance matrix estimation is of great importance in statistical signal processing. This paper considers covariance matrix estimation from correlated complex sub-Gaussian samples via the shrinkage estimator. We establish non-asymptotic error bounds for this estimator in both tail and expectation forms. Our theoretical results demonstrate that the error bounds depend on the signal dimension, the sample size, the shape parameter, and the shrinkage coefficient$\alpha$. These results reveal that the shrinkage estimator can reduce the sample complexity of the standard sample covariance matrix estimator when the target matrix is reliable and$\alpha$is properly chosen.

The Capon method is one of the classical direction-of-arrival (DOA) estimation methods in array signal processing. The standard analysis of the additional bias of this method is asymptotic, which assumes the number of snapshots$K$goes to infinity. This paper provides a non-asymptotic analysis for the additional bias by employing some tools from high-dimensional probability and perturbation analysis of optimization problems. We establish upper bounds for the additional bias in both expectation and tail forms, which reveal that the additional bias has an error rate of$O(K^{-\frac{1}{2}})$when the number of snapshots satisfies a certain condition. We demonstrate our results by some numerical experiments.

In this paper, we characterize data-time tradeoffs of the proximal-gradient homotopy method used for solving linear inverse problems under sub-Gaussian measurements. Our results are sharp up to an absolute constant factor. We demonstrate that, in the absence of the strong convexity assumption, the proximal-gradient homotopy update can achieve a linear rate of convergence when the number of measurements is sufficiently large. Numerical simulations are provided to verify our theoretical results.

In this letter, we present a sharp algorithmic analysis for alternating projected gradient descent which is used to solve the covariate adjusted precision matrix estimation problem in high-dimensional settings. By introducing a new analytical tool (the generic chaining), we remove the impractical resampling assumption used in the literature. The new analysis also demonstrates that this algorithm not only enjoys a linear convergence rate in the absence of convexity, but also attains the minimax rate with optimal order of sample complexity. Our results, meanwhile, reveal a time-data tradeoff in this problem. Numerical experiments are provided to verify our theoretical results.

This paper is concerned with the problem of recovering a structured signal from a relatively small number of corrupted random measurements. Sharp phase transitions have been numerically observed in practice when different convex programming procedures are used to solve this problem. This paper is devoted to presenting theoretical explanations for these phenomena by employing some basic tools from Gaussian process theory. Specifically, we identify the precise locations of the phase transitions for both constrained and penalized recovery procedures. Our theoretical results show that these phase transitions are determined by some geometric measures of structure, e.g., the spherical Gaussian width of a tangent cone and the Gaussian (squared) distance to a scaled subdifferential. By utilizing the established phase transition theory, we further investigate the relationship between these two kinds of recovery procedures, which also reveals an optimal strategy (in the sense of Lagrange theory) for choosing the tradeoff parameter in the penalized recovery procedure. Numerical experiments are provided to verify our theoretical results.

This paper is concerned with the problem of recovering a structured signal from a relatively small number of corrupted random measurements. Sharp phase transitions have been numerically observed in practice when different convex programming procedures are used to solve this problem. This paper is devoted to presenting theoretical explanations for these phenomena by employing some basic tools from Gaussian process theory. Specifically, we identify the precise locations of the phase transitions for both constrained and penalized recovery procedures. Our theoretical results show that these phase transitions are determined by some geometric measures of structure, e.g., the spherical Gaussian width of a tangent cone and the Gaussian (squared) distance to a scaled subdifferential. By utilizing the established phase transition theory, we further investigate the relationship between these two kinds of recovery procedures, which also reveals an optimal strategy (in the sense of Lagrange theory) for choosing the tradeoff parameter in the penalized recovery procedure. Numerical experiments are provided to verify our theoretical results.

In this paper, we present non-asymptotic optimization guarantees of gradient descent methods for estimating structured transition matrices in high-dimensional vector autoregressive (VAR) models. We adopt the projected gradient descent (PGD) for single-structured transition matrices and the alternating projected gradient descent (AltPGD) for superposition-structured ones. Our analysis demonstrates that both gradient algorithms converge linearly to the statistical error even though the strong convexity of the objective function is absent under the high-dimensional settings. Moreover our result is sharp (up to a constant factor) in the sense of matching the phase transition theory of the corresponding model with independent samples. To the best of our knowledge, this analysis constitutes first non-asymptotic optimization guarantees of the linear rate for regularized estimation in high-dimensional VAR models. Numerical results are provided to support our theoretical analysis.

Quantized corrupted sensing concerns the problem of estimating structured signals from their quantized corrupted samples. A typical case is that when the measurements y = Φx* + v* + n are corrupted with both structured corruption v* and unstructured noise n, we wish to reconstruct x* and v* from the quantized samples of y. Our work shows that the Generalized Lasso can be applied for the recovery of signal provided that a uniform random dithering is added to the measurements before quantization. The theoretical results illustrate that the influence of quantization behaves as independent unstructured noise. We also confirm our results numerically in several scenarios such as sparse vectors and low-rank matrices.

This paper studies the problem of recovering a structured signal from a relatively small number of corrupted non-linear measurements. Assuming that signal and corruption are contained in some structure-promoted set, we suggest an extended Lasso to disentangle signal and corruption. We also provide conditions under which this recovery procedure can successfully reconstruct both signal and corruption.

This paper studies the problem of accurately recovering a structured signal from a small number of corrupted sub-Gaussian measurements. We consider three different procedures to reconstruct signal and corruption when different kinds of prior knowledge are available. In each case, we provide conditions (in terms of the number of measurements) for stable signal recovery from structured corruption with added unstructured noise. Our results theoretically demonstrate how to choose the regularization parameters in both partially and fully penalized recovery procedures and shed some light on the relationships among the three procedures. The key ingredient in our analysis is an extended matrix deviation inequality for isotropic sub-Gaussian matrices, which implies a tight lower bound for the restricted singular value of the extended sensing matrix. Numerical experiments are presented to verify our theoretical results.

In this letter, we characterize a data-time tradeoff for projected gradient descent (PGD) algorithms used for solving corrupted sensing problems under sub-Gaussian measurements. We also show that with a proper step size, the PGD method can achieve a linear rate of convergence when the number of measurements is sufficiently large.

This paper studies the problem of accurately recovering a structured signal from a small number of corrupted sub-Gaussian measurements. We consider three different procedures to reconstruct signal and corruption when different kinds of prior knowledge are available. In each case, we provide conditions for stable signal recovery from structured corruption with added unstructured noise. The key ingredient in our analysis is an extended matrix deviation inequality for isotropic sub-Gaussian matrices.

Compressed sensing (CS) with prior information concerns the problem of reconstructing a sparse signal with the aid of a similar signal which is known beforehand. We consider a new approach to integrate the prior information into CS via maximizing the correlation between the prior knowledge and the desired signal. We then present a geometric analysis for the proposed method under sub-Gaussian measurements. Our results reveal that if the prior information is good enough, then the proposed approach can improve the performance of the standard CS. Simulations are provided to verify our results.

In [1], a sharp phase transition has been numerically observed when a constrained convex procedure is used to solve the corrupted sensing problem. In this paper, we present a theoretical analysis for this phenomenon. Specifically, we establish the threshold below which this convex procedure fails to recover signal and corruption with high probability. Together with the work in [1], we prove that a sharp phase transition occurs around the sum of the squares of spherical Gaussian widths of two tangent cones. Numerical experiments are provided to demonstrate the correctness and sharpness of our results.

Signals with sparse representations in frames comprise a much more realistic model of nature, it is therefore highly desirable to extend the compressed sensing methodology to redundant dictionaries (or frames) as opposed to orthonormal bases only. In the generalized setting, the standard approach to recover the signal is known as ℓ1-synthesis (or Basis Pursuit). In this paper, we present the performance analysis of this approach in which the dictionary may be highly - and even perfectly - correlated. Our results do not depend on an accurate recovery of the coefficients. We demonstrate the validity of the results via several experiments.

A sparse-dual-frame based ℓ1-analysis approach for compressed sensing (CS) is proposed. The sparse dual frame is a notion of optimal dual frames of a non-exact frame. It is motivated in the study of compressed sensing problems where signals are sparse with respect to redundant dictionaries (frames). An alternating iterative algorithm is proposed. An error bound ensuring the correct signal recovery is obtained. Empirical studies over generally difficult CS problems demonstrate that the new sparse-dual-based approach provides satisfactory solutions, whereas other existing means may not.

Compressed sensing with sparse frame representations is seen to have much greater range of practical applications than that with orthonormal bases. In such settings, one approach to recover the signal is known as ℓ1-analysis. We expand in this paper the performance analysis of this approach by providing a weaker recovery condition than existing results in the literature. Our analysis is also broadly based on general frames and alter native dual frames (as analysis operators). As one application to such a general-dual-based approach and performance analysis, an optimal-dual-based technique is proposed to demonstrate the effectiveness of using alternative dual frames as ℓ1-analysis operators. An iterative algorithm is outlined for solving the optimal-dual-based -analysis problem. The effectiveness of the proposed method and algorithm is demonstrated through several experiments.