Sparse optimization

Compressed sensing reconstructs a sparse vector, or an approximately sparse one, from fewer linear measurements than its ambient dimension. Basis pursuit replaces counting nonzero coordinates by convex ${\ell }^1$ minimization. A null space property characterizes exact uniform recovery, while a robust null space property controls errors from noise and nonsparse tails.

For a matrix with at least two columns of unit Euclidean norm, its mutual coherence is the largest magnitude of an inner product between distinct columns. It measures the strongest pairwise ambiguity of linear measurements. The Cauchy-Schwarz inequality gives $0\le \mu \le 1$. The order-two restricted isometry constant equals the mutual coherence, because every two-column Gram matrix has eigenvalues $1\pm |⟨a_i,a_j⟩|$.

For unit Euclidean norm columns, cumulative coherence measures the largest sum of $k$ correlations with one other column. Its domain is $0\le k\le N-1$, with ${\mu }_1(0)=0$ by the empty-sum convention. It is nondecreasing, ${\mu }_1(1)=\mu$ for $N\ge 2$, and ${\mu }_1(k)\le k\mu$, where $\mu$ is the mutual coherence. Keeping a sum of actual correlations can be substantially sharper than replacing each summand by the largest one.

For normalized columns and $1\le s\le N$, the restricted isometry constant is bounded by the cumulative coherence at $s-1$. A restricted Gram matrix has diagonal one and every off-diagonal row sum at most ${\mu }_1(s-1)$. The Gershgorin circle theorem and the finite-dimensional spectral theorem bound its eigenvalues between $1-{\mu }_1(s-1)$ and $1+{\mu }_1(s-1)$. At $s=1$ the distortion is zero, and at $s=2$ it is exactly the mutual coherence.

A linear map is injective on the class of sparse vectors of order $s$ exactly when its null space contains no nonzero vector with at most $2s$ nonzero entries. Differences of two sparse vectors have at most $2s$ active coordinates. Conversely, splitting the support of a vector of a $2s$-sparse null vector into two parts constructs two distinct $s$-sparse vectors with the same image. The strict null space property implies sparse injectivity by applying it to both parts of such a split.

The restricted isometry property controls $\Vert Ax{\Vert }_2^2/\Vert x{\Vert }_2^2$ uniformly over sparse vectors. It supplies quantitative near-orthogonality of disjoint sparse coordinate combinations, not merely normalization of individual columns.

The order-s restricted isometry constant is the smallest nonnegative $\delta$ satisfying $(1-\delta )\Vert x{\Vert }_2^2\le \Vert Ax{\Vert }_2^2\le (1+\delta )\Vert x{\Vert }_2^2$ for every vector with at most $s$ nonzero coordinates. Equivalently it is ${\max }_{|S|\le s}\Vert A_S^{\ast }{A}_S-I{\Vert }_{2\to 2}$. The sparse-vector quantifier is essential, and the constant can equal zero.

For $s\ge 2$ and $\delta ={\delta }_s(A)<1/3$, noisy basis pursuit has error $\Vert \hat{x}-x_0{\Vert }_2\le C_1\eta +C_2{\sigma }_s(x_0)/\sqrt{s}$, with constants depending only on $\delta$. One admissible pair isThese constants follow from Theorem 3.3 of the sharp restricted-isometry recovery analysis, with the actual noise bounded by the tolerance $\eta$. The restriction $s\ge 2$ is necessary: equal unit columns give ${\delta }_1=0$ without unique recovery. The coefficient of the approximation term cannot universally be one.

Basis pursuit minimizes an ${\ell }^1$ norm subject to exact linear measurements. Basis pursuit with a noise tolerance replaces the equality by $\Vert Ax-y{\Vert }_2\le \eta$. A unique minimizer has linearly independent active columns, and hence at most $\mathrm{rank}A$ nonzero coordinates: a null direction on its support would make the objective locally affine on a feasible line, contradicting minimality or uniqueness.

For a real vector $x$ with support of a vector $S$, this certificate is a vector $h$ whose measurements under the adjoint operator match the active sign function values and lie strictly between minus one and one on the inactive coordinates. If $A_S$ is injective, such a certificate proves that $x$ is the unique basis pursuit minimizer. For a nonzero $v\in \ker A$, injectivity ensures $v_{S^c}\ne 0$, and $0=⟨A^{\ast }h,v⟩$ implies the fixed-sign null space condition. The strict inequality is interpreted coordinatewise if $S^c$ is empty. The condition with the sign function written here is for real variables; complex basis pursuit uses the unit phases of active coordinates instead.

When $A_S$ is injective, this vector solves $A_S^{\ast }{h}_0=\mathrm{sgn}(x_S)$. Any other solution differs by a vector in $\ker A_S^{\ast }$, orthogonal to the range of $A_S$ containing $h_0$. The Pythagorean identity therefore proves that $h_0$ has the smallest Euclidean norm. It is a strict dual certificate for basis pursuit exactly when each inactive coordinate of $A^{\ast }{h}_0$ has magnitude less than one. Failure of that test does not rule out another certificate: a null space component of $A_S^{\ast }$ can alter those inactive coordinates.

The null space property relative to $S$ is $\Vert h_S{\Vert }_1<\Vert h_{S^c}{\Vert }_1$ for every nonzero $h\in \ker A$. It is equivalent to exact basis pursuit recovery of every vector supported in $S$. Sufficiency follows from the triangle inequality; for necessity, compare $-h_S$ and $h_{S^c}$, which have the same image under $A$. Recovery of a single fixed signed vector can hold without this uniform property.

For $0<q\le 1$, this strict inequality for every nonzero $v\in \ker A$ and every $|S|\le s$ is equivalent to unique constrained ${\ell }^q$ recovery of every sparse vector of order $s$. For sufficiency, use $|x_i+v_i{|}^q\ge |x_i{|}^q-|v_i{|}^q$ on the support of a vector. For necessity compare $x=-v_S$ with $v_{S^c}$, which have the same measurements. The statement concerns uniform recovery over the whole sparse class, rather than a single signed vector.

If the Lq null space property holds at $q\le 1$, it holds at every $0<p<q$. Order a nonzero null vector's magnitudes $a_1\ge \cdots \ge a_N$ and put $t=a_s>0$. Since $p-q<0$, the top-$s$ $p$-power sum is at most $t^{p-q}$ times its $q$-power sum, while the tail $p$-power sum is at least that multiple of the tail $q$-power sum. The strict $q$ inequality therefore gives the strict $p$ inequality. The largest $s$ magnitudes are the worst support of a vector, so all other supports satisfy it too.

The displayed property holds for every $h$ and every $|S|\le s$, with $0\le \rho <1$ and $\tau >0$. It converts the cone inequality from basis pursuit minimality and the tube inequality from noisy feasibility into a two-constant bound $\Vert \hat{x}-x_0{\Vert }_2\le C_1\eta +C_2{\sigma }_s(x_0)/\sqrt{s}$. Both constants are needed in general; a fixed coefficient one on the approximation term does not follow.

For a real vector $x_0$ with support $S$, uniqueness in basis pursuit is equivalent to $|⟨\mathrm{sgn}(x_{0,S}),h_S⟩|<\Vert h_{S^c}{\Vert }_1$ for every nonzero $h\in \ker A$. The supporting-line inequality for the absolute value proves sufficiency. Taking small positive and negative multiples of $h$ before any active sign changes proves necessity.

A vector is s-sparse if it has at most $s$ nonzero coordinates. For $x\in {\mathbb{R}}^N$, its best s-term ${\ell }^1$ approximation error is ${\sigma }_s(x)={\min }_{z\text{ s-sparse}}\Vert x-z{\Vert }_1$, equal to the sum of the absolute values of the coordinates outside the largest $s$.

The number of nonzero coordinates of a finite vector is its L0 sparsity count. It vanishes only at zero, but is unchanged under multiplication by a nonzero scalar, so it is not a norm. Minimizing it under linear measurement constraints finds a sparse vector with the smallest possible support of a vector. Sparse injectivity of order $s$ guarantees unique recovery of every sparse vector with at most $s$ nonzero coordinates by this objective.

The support of a finite vector is the set of indices of its nonzero coordinates. It is the support of a function on a finite discrete index set, and its cardinality defines sparsity.

For any field $F$ and vector subspace $W\subseteq F^m$, some $u\in W$ has at least $\dim W$ nonzero coordinates. Choose $u$ with largest support of a vector $S$. Restriction from $W$ to $F^S$ is injective: a nonzero vector in its kernel of a linear map vanishes on $S$, so adding it to $u$ would enlarge $S$. Thus $\dim W\le |S|$. The argument works over finite fields, where assuming a generic vector avoids finitely many hyperplanes would be invalid.