## Phase Transitions of the Regular Polytopes and Cone

Some sparse approximation questions can be modelled exactly through convex polytopes. When this is possible, their analysis can provide Precise Undersampling Theorems (by Donoho and Tanner). These results are cast in terms of the:

Over-sampling ratio: `δ` = `n`/`N`,

Under-sampling ratio: `ρ` = `k`/`n`,

where `k` is the sparsity of the vector, `n` is the number of
measurements and `N` is the length of the vector measured.

This form interpolates the values of the strong and weak phase transitions of the orthant and
three regular polytopes: the simplex, crosspolytope, and hypercube as well as the orthant. For
`ρ` below a strong phase transition, the phenomenon is true for *all*
`k`-sparse vectors, and below a weak phase transition, the phenomenon is true for
*most* `k`-sparse vectors. The crosspolytope models `l`1-regularization,
the simplex models `l`1-regularization with nonnegativity (or other sparsity constraints)
and uniqueness of nonnegative vectors when the average of the signal is also measured, the orthant
models uniqueness of nonnegative vectors from mean-zero measurement matrices, and the hypercube
models bound constrainsts where `k` is the number of entries in the vector which are
*not* at the bounds. The figure below shows these plots for the crosspolytope
(blue, `C`), simplex (black, `T`), orthant (red, `R`_{+})
and hypercube (only weak phase transition, solid red, `R`_{+}).
For further details see Precise Undersampling Theorems
(by Donoho and Tanner). Tabulated values
of these phase transition are available in MATLAB format.