Answers are grounded in this paper and cite their sources.
It is known that a high-dimensional sparse vector x* in TV can be recovered from low-dimensional measurements y = Ax* where A m×n (m <; n) is the measurement matrix. In this paper, with A being a random Gaussian matrix, we investigate the recovering ability of ℓ p -minimization (0 ≤ p ≤ 1) as p varies, where ℓ p -minimization returns a vector with the least ℓ p quasi norm among all the vectors x satisfying Ax = y. Besides analyzing the performance of strong recovery where ℓ p -minimization is re quired to recover all the sparse vectors up to certain sparsity, we also for the first time analyze the performance of "weak" recovery of ℓ p -minimization (0 ≤ p <; 1) where the aim is to recover all the sparse vectors on one support with a fixed sign pattern. When α(:= m / n ) → 1, we provide sharp thresholds of the sparsity ratio (i.e., percentage of nonzero entries of a vector) that differentiates the success and failure via ℓ p -minimization. For strong recovery, the threshold strictly decreases from 0.5 to 0.239 as p increases from 0 to 1. Surprisingly, for weak recovery, the threshold is 2/3 for all p in [0, 1), while the threshold is 1 for ℓ 1 -minimization. We also explicitly demonstrate that ℓ p -minimization (p <; 1) can re turn a denser solution than ℓ p -minimization. For any a G (0.1), we provide bounds of the sparsity ratio for strong recovery and weak recovery, respectively, below which ℓ p -minimization succeeds. Our bound of strong recovery improves on the existing bounds when a is large. In particular, regarding the recovery threshold, this paper argues that ℓ p -minimization has a higher threshold with smaller p for strong recovery; the threshold is the same for all p for sectional recovery; and ℓ p -minimization can outperform ℓ p -minimization for weak recovery. These are in contrast to traditional wisdom that ℓ p -minimization, though computationally more expensive, always has better sparse recovery ability than ℓ 0 -minimization since it is closer to ℓ 1 -minimization. Finally, we provide an intuitive explanation to our findings. Numerical examples are also used to un ambiguously confirm and illustrate the theoretical predictions.
No takes yet. Share an insight, caveat, or question.
Wang et al. (2011) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: