This note demonstrates that we can stably recover rank-rToeplitz matrix$\pmb {X}\in \mathbb {R}^{n\times n}$from a number of rank-one subgaussian measurements on the order of$r\log ^{2} n$with an exponentially decreasing failure probability by employing a nuclear norm minimization program. Our approach utilizes descent cone analysis through Mendelson’s small ball method with the Toeplitz constraint. The key ingredient is to determine the spectral norm of the random matrix of the Toeplitz structure, which may be of independent interest. This improves upon earlier analyses and resolves the conjecture in Chen et al. (IEEE Transactions on Information Theory, 61(7):4034–4059, 2015).

We investigate the phase retrieval problem perturbed by dense bounded noise and sparse outliers that can change an adversarially chosen s-fraction of the measurement vector. The adversarial sparse outliers may depend on both the observation and measurements. We demonstrate that the nonlinear least absolute deviation based on amplitude measurements can tolerate adversarial outliers up to a fraction ofs*, 1≈ 0.2043, while the intensity-based model can tolerate a fraction ofs*, 2≈ 0.1185. Furthermore, we construct adaptive counterexamples to show that these thresholds are theoretically sharp, thereby showing the presentation of phase transition in the adversarial phase retrieval problem when the corruption fraction exceeds the sharp thresholds. This implies that the amplitude-based model exhibits superior adversarial robustness in comparison with the intensity-based model. Corresponding experimental results are presented to further illustrate our theoretical findings. To the best of our knowledge, our results provide the first theoretical examination of the differences in robustness performance between amplitude and intensity measurement. A crucial aspect of our analysis is the exploration of the exact distribution of a combination of two non-independent Gaussian random variables, leading to the presentation of novel probability density functions to derive the sharp thresholds.

We consider sparse representations of signals from redundant dictionaries which are unions of several orthonormal bases. The spark introduced by Donoho and Elad plays an important role in sparse representations. However, numerical computations of sparks are generally combinatorial. For unions of several orthonormal bases, two lower bounds on the spark via the mutual coherence were established in previous work. We constructively prove that both of them are tight. Our main results give positive answers to Gribonval and Nielsen’s open problem on sparse representations in unions of orthonormal bases. Constructive proofs rely on a family of mutually unbiased bases which first appears in quantum information theory.

One-bit compressive sensing theory shows that the sparse signals can be almost exactly reconstructed from a small number of one-bit quantized linear measurements. This paper presents the convergence analysis of the binary iterative hard thresholding (BIHT) algorithm which is a state-of-the-art recovery algorithm in one-bit compressive sensing. The basic idea of the convergence analysis is to view BIHT as a kind of projected subgradient method under sparsity constrains. To the best of our knowledge, this is the first convergence analysis of BIHT. We first consider a general convex function subject to sparsity constraints and connect it with the non-convex model in one-bit compressive sensing literatures. A projected subgradient method is proposed to solve the general model and some convergence results are established. A stronger convergence theorem for α-strongly convex functions without assumption on differentiable condition is also established. Furthermore, the corresponding stochastic projected subgradient method is provided with convergence guarantee. In our settings, BIHT is a special case of the projected subgradient method. Therefore, the convergence analysis can be applied to BIHT naturally. Then, we apply the projected subgradient method to some related non-convex optimization models arising in compressive sensing with 11-constraint, sparse support vector machines, and rectifier linear units regression. Finally, some numerical examples are presented to show the validity of our convergence analysis. The numerical experiments also show that the proposed projected subgradient method is very simple to implement, robust to sparse noise, and effective for sparse recovery problems.

In this paper, we give a complete answer to the conjecture on restricted isometry property (RIP) constants δtk(0<;t<;(4/3)), which was proposed by T. Cai and A. Zhang. We have shown that when 0 <; t <; (4/3), the condition δtk<; (t/(4-t)) is sufficient to guarantee the exact recovery for all k-sparse signals in the noiseless case via the constrained ℓ1-norm minimization. These bounds are sharp in the sense that for any ϵ>0, δtk<; (t/(4-t)) + ϵ cannot guarantee the exact recovery of some k-sparse signals. Furthermore, it will be shown that similar characterizations also hold for low-rank matrix recovery. Thus, combined with T. Cai and A. Zhang's work, a complete characterization for sharp RIP constants δtkfor all t > 0 is obtained to guarantee the exact recovery of all k-sparse signals and matrices with rank at most k by ℓ1-norm minimization and nuclear norm minimization, respectively. Noisy cases and approximately sparse cases are also considered. To solve the conjecture, we construct a few identities so that RIP of order tk, which is the target of our main results, can be perfectly applied to them.

This paper discusses the reconstruction of signals from few measurements in the situation that signals are sparse or approximately sparse in terms of a general frame via the lq-analysis optimization with 0q-analysis optimization. We then determine how many random Gaussian measurements are needed for the condition to hold with high probability. The resulting sufficient condition is met by fewer measurements for smaller q than when q = 1. The introduced generalized q-RIP is also useful in compressed data separation. In compressed data separation, one considers the problem of reconstruction of signals' distinct subcomponents, which are (approximately) sparse in morphologically different dictionaries, from few measurements. With the notion of generalized q-RIP, we show that under a usual assumption that the dictionaries satisfy a mutual coherence condition, the lqsplit analysis with 0 <; q ≤ 1 can approximately reconstruct the distinct components from fewer random Gaussian measurements with smaller q than when q = 1.

This paper introduces the restricted eigenvalue condition adapted to frame D (D-RE), which is a natural extension to the standard restricted eigenvalue condition. The D-RE condition is a relaxation of the D†-RIP, where D†= (DD*)-1D is the canonical dual frame of D. We establish the D-RE condition for several classes of correlated measurement matrices, when the covariance matrix of row measurements satisfies the D-RE condition. Furthermore, by the D-RE condition, we get the error bounds in the analysis LASSO (ALASSO) and the analysis Dantzig Selector (ADS) under a sparsity scenario. In order to recover non-sparse signals, we consider the robust 12 D-nullspace property of correlated Gaussian matrices. Similarly, we get the error estimations in the ALASSO and the ADS in non-sparse case. The approximation equivalence between the ALASSO and the ADS is also established by calculating prediction loss difference.

Most of the data scientists face today might be classified as multimodal data, i.e., being composed of distinct subcomponents. One common task is to separate such data into appropriate single components for further analysis. In this paper, we consider data separation from fewer, linear, nonadaptive, and noisy measurements. We show that the distinct subcomponents, which are (approximately) sparse in morphologically different (redundant) dictionaries, can be reconstructed by solving the split-analysis algorithm, provided that the dictionaries satisfy a mutual coherence (between the different dictionaries) condition and the measurement matrix satisfies a restricted isometry property adapted to a composed dictionary. These conditions impose no incoherence restriction on the dictionaries themselves, and our main result may be the first of this kind.