4.4 The cross-polytope and phase transitions

The analysis of ${\ell }_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 ${\ell }_1$ minimization algorithms is to examine them from a more geometric perspective. Towards this end, we define the closed ${\ell }_1$ ball, also known as the cross-polytope :

Note that $C^N$ is the convex hull of $2N$ points ${\left\{p_i\right\}}_{i=1}^{2N}$ . Let $\Phi C^N\subseteq {\mathbb{R}}^M$ denote the convex polytope defined as either the convex hull of ${\left\{\Phi p_i\right\}}_{i=1}^{2N}$ or equivalently as

For any $x\in {\Sigma }_K=\left\{x,:,{∥x∥}_0,\le ,K\right\}$ , we can associate a $K$ -face of $C^N$ with the support and sign pattern of $x$ . One can show that the number of $K$ -faces of $\Phi C^N$ is precisely the number of index sets of size $K$ for which signals supported on them can be recovered by

with $\mathcal{B}\left(y\right)=\{z:\Phi z=y\}$ . Thus, ${\ell }_1$ minimization yields the same solution as ${\ell }_0$ minimization for all $x\in {\Sigma }_K$ if and only if the number of $K$ -faces of $\Phi C^N$ is identical to the number of $K$ -faces of $C^N$ . Moreover, by counting the number of $K$ -faces of $\Phi C^N$ , we can quantify exactly what fraction of sparse vectors can be recovered using ${\ell }_1$ minimization with $\Phi$ as our sensing matrix. See  [link] , [link] , [link] , [link] , [link] for more details and  [link] 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  [link] .

Given this result, one can then study random matrix constructions from this perspective to obtain probabilistic bounds on the number of $K$ -faces of $\Phi C^N$ with $\Phi$ is generated at random, such as from a Gaussian distribution. Under the assumption that $K=\rho M$ and $M=\gamma N$ , one can obtain asymptotic results as $N\to \infty$ . This analysis leads to the phase transition phenomenon, where for large problem sizes there are sharp thresholds dictating that the fraction of $K$ -faces preserved will tend to either one or zero with high probability, depending on $\rho$ and $\gamma$   [link] .

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 $\Phi$ (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.