The analysis of ℓ1ℓ1 minimization based on the restricted isometry property (RIP) described in "Signal recovery in noise" allows us to establish a variety of guarantees under different noise settings, but one drawback is that the analysis of how many measurements are actually required for a matrix to satisfy the RIP is relatively loose. An alternative approach to analyzing ℓ1ℓ1 minimization algorithms is to examine them from a more geometric perspective. Towards this end, we define the closed ℓ1ℓ1 ball, also known as the cross-polytope:
C
N
=
x
∈
R
N
:
x
1
≤
1
.
C
N
=
x
∈
R
N
:
x
1
≤
1
.
(1)Note that CNCN is the convex hull of 2N2N points {pi}i=12N{pi}i=12N. Let ΦCN⊆RMΦCN⊆RM denote the convex polytope defined as either the convex hull of {Φpi}i=12N{Φpi}i=12N or equivalently as
Φ
C
N
=
y
∈
R
M
:
y
=
Φ
x
,
x
∈
C
N
.
Φ
C
N
=
y
∈
R
M
:
y
=
Φ
x
,
x
∈
C
N
.
(2)For any x∈ΣK =
x
:
x
0
≤
K
x∈ΣK =
x
:
x
0
≤
K
, we can associate a KK-face of CNCN with the support and sign pattern of xx. One can show that the number of KK-faces of ΦCNΦCN is precisely the number of index sets of size KK for which signals supported on them can be recovered by
x
^
=
argmin
z
z
1
subject to
z
∈
B
(
y
)
.
x
^
=
argmin
z
z
1
subject to
z
∈
B
(
y
)
.
(3)with B(y)={z:Φz=y}B(y)={z:Φz=y}. Thus, ℓ1ℓ1 minimization yields the same solution as ℓ0ℓ0 minimization for all x∈ΣKx∈ΣK if and only if the number of KK-faces of ΦCNΦCN is identical to the number of KK-faces of CNCN. Moreover, by counting the number of KK-faces of ΦCNΦCN, we can quantify exactly what fraction of sparse vectors can be recovered using ℓ1ℓ1 minimization with ΦΦ as our sensing matrix. See [1], [2], [3], [4], [5] for more details and [6] for an overview of the implications of this body of work. Note also that by replacing the cross-polytope with certain other polytopes (the simplex and the hypercube), one can apply the same technique to obtain results concerning the recovery of more limited signal classes, such as sparse signals with nonnegative or bounded entries [6].
Given this result, one can then study random matrix constructions from this perspective to obtain probabilistic bounds on the number of KK-faces of ΦCNΦCN with ΦΦ is generated at random, such as from a Gaussian distribution. Under the assumption that K=ρMK=ρM and M=γNM=γN, one can obtain asymptotic results as N→∞N→∞. This analysis leads to the phase transition phenomenon, where for large problem sizes there are sharp thresholds dictating that the fraction of KK-faces preserved will tend to either one or zero with high probability, depending on ρρ and γγ [6].
These results provide sharp bounds on the minimum number of measurements required in the noiseless setting. In general, these bounds are significantly stronger than the corresponding measurement bounds obtained within the RIP-based framework given in "Noise-free signal recovery", which tend to be extremely loose in terms of the constants involved. However, these sharper bounds also require somewhat more intricate analysis and typically more restrictive assumptions on ΦΦ (such as it being Gaussian). Thus, one of the main strengths of the RIP-based analysis presented in "Noise-free signal recovery" and "Signal recovery in noise" is that it gives results for a broad class of matrices that can also be extended to noisy settings.
-
Donoho, D. (2005, Jan.). Neighborly polytopes and sparse solutions of underdetermined linear equations. (2005-04). Technical report. Stanford Univ., Stat. Dept.
-
Donoho, D. (2006). High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension. Discrete and Comput. Geometry, 35(4), 617–652.
-
Donoho, D. and Tanner, J. (2005). Neighborliness of randomly projected simplices in high dimensions. Proc. Natl. Acad. Sci., 102(27), 9452–9457.
-
Donoho, D. and Tanner, J. (2005). Sparse Nonnegative Solutions of Undetermined Linear Equations by Linear Programming. Proc. Natl. Acad. Sci., 102(27), 9446–9451.
-
Donoho, D. and Tanner, J. (2009). Counting faces of randomly-projected polytopes when the projection radically lowers dimension. J. Amer. Math. Soc., 22(1), 1–53.
-
Donoho, D. and Tanner, J. (2010). Precise undersampling theorems. Proc. IEEE, 98(6), 913–924.
