Convex recovery of a structured signal from independent random linear measurements

Joel A. Tropp

Source-linked AI summary

Convex recovery of a structured signal from independent random linear measurements

Joel A. Tropp

arXiv:1405.1102v3May 5, 2014cs.ITmath.ST

TL;DR

The paper asks how convex programming can recover structured signals from random linear measurements across broad measurement ensembles. It combines Mendelson’s Small Ball Method with conic-duality estimates, obtaining sampling bounds and a Gaussian phase-retrieval guarantee.

Problem
Existing analyses use separate ad hoc arguments for different complexity measures and sampling distributions, leaving a unified approach for broad measurement classes open.
Method
The paper bounds a nonnegative empirical process with Mendelson’s Small Ball Method and completes the estimates using a conic-duality bowling scheme.
Results
With m ≥ Cd independent Gaussian measurements, convex phase retrieval recovers x♮ with probability at least 1−e^−cm.
Takeaways & Limitations
The approach provides convex recovery analyses for a wide class of random measurements and extends the Gaussian-style framework to phase retrieval.
Takeaways & Limitations
The Small Ball Method may require significant improvement for spiky measurement vectors and problems such as matrix completion.

Abstract

from arXiv · show

This chapter develops a theoretical analysis of the convex programming method for recovering a structured signal from independent random linear measurements. This technique delivers bounds for the sampling complexity that are similar with recent results for standard Gaussian measurements, but the argument applies to a much wider class of measurement ensembles. To demonstrate the power of this approach, the paper presents a short analysis of phase retrieval by trace-norm minimization. The key technical tool is a framework, due to Mendelson and coauthors, for bounding a nonnegative empirical process.

1. MOTIVATION

The chapter addresses how many random linear measurements suffice for convex recovery of structured signals. It develops a unified approach for broader measurement ensembles using Mendelson’s Small Ball Method and conic-duality estimates.

Convex recovery uses random linear measurements and structural priors to estimate an unknown signal, with measurement count as the central question.
Gaussian measurements have comprehensive sampling bounds, but general measurement systems lack a simple unified analysis.
The chapter analyzes a wide class of convex recovery problems by lower-bounding a nonnegative empirical process with Mendelson’s Small Ball Method.
A conic-duality technique, called the bowling scheme, supplies the estimates required by the Small Ball Method.
The chapter first reviews Gaussian recovery and then develops analyses for subgaussian and more general random measurements.

2. SIGNAL RECONSTRUCTION FROM LINEAR MEASUREMENTS

This section formulates structured signal recovery from noisy linear measurements as convex optimization and develops its geometric error analysis. The key bound reduces recovery to the minimum conic singular value of the measurement matrix on a descent cone.

Examples: The framework covers convex recovery methods such as ℓ1 minimization for sparse vectors and Schatten 1-norm minimization for low-rank matrices.
Linear acquisition of data: The acquisition model uses a known sampling matrix, an unknown structured signal, and an unknown error vector bounded in Euclidean norm.
Reconstruction via convex optimization: The convex program seeks the most structured signal consistent with the measurements and the specified error bound.
Deterministic error analysis: Every optimizer lies in both the descent cone and the feasible tube, so recovery error is controlled by how far a descent direction can travel before violating the constraint.
Deterministic error analysis: A descent cone collects directions along which a convex complexity function decreases, and the measurement matrix is analyzed on this cone.
Deterministic error analysis: The minimum conic singular value is the relevant restricted measurement quantity, defined over unit vectors in a cone.
Deterministic error analysis: The deterministic error bound is elegant but difficult to apply because computing the minimum conic singular value can be challenging.

3. A UNIVERSAL ERROR BOUND FOR GAUSSIAN MEASUREMENTS

For Gaussian measurement matrices, conic Gaussian width controls the minimum conic singular value and yields sharp, high-probability recovery guarantees for convex optimization.

Geometric parameter: The conic Gaussian width w(K) is the geometric parameter governing Gaussian recovery thresholds.It is also comparable to the statistical dimension through w(K)^2 ≤ δ(K) ≤ w(K)^2+1.
Gaussian measurements: Independent standard Gaussian rows yield sharp bounds on the minimum conic singular value for any cone.The analysis uses Gaussian-process comparison and concentration inequalities.
Scope: The Gaussian argument relies on special Gaussian-process results that do not extend directly to other distributions.The error bound can improve when the noise vector itself follows a Gaussian model.
Phase transition: m ≥ w(K)^2 + Cw(K) ensures λmin(Φ;K) > 0 with high probability.For convex cones, m ≤ w(K)^2 − Cw(K) instead gives λmin(Φ;K)=0 with high probability, producing a phase transition.
Recovery guarantee: Corollary 3.5 converts the conic singular-value estimate into a universal noisy recovery error bound for convex optimization.The guarantee applies to any convex complexity measure under bounded measurement noise.

4. CONTROLLING THE WIDTH OF A DESCENT CONE VIA POLARITY

Polarity provides a general mechanism for estimating descent-cone widths, which then produces measurement bounds for sparse vectors and low-rank matrices.

General mechanism: Polarity and weak duality convert descent-cone width calculations into distances involving the subdifferential.The resulting width bound applies to proper convex functions whose subdifferential is nonempty and excludes the origin.
Sparse vectors: For an s-sparse vector in R^d, m ≳ 2s log(d/s) measurements suffice for approximate recovery.When s ≪ d, the leading term is numerically sharp.
Low-rank matrices: For a rank-r matrix in R^(d1×d2), m ≳ 3r·(d1+d2−r) measurements allow identification under the Gaussian model.A more complicated width formula is sharp when r is proportional to min{d1,d2}.

5. MENDELSON’S SMALL BALL METHOD

The Small Ball Method replaces Gaussian-specific analysis with a general lower-bound framework for the empirical process governing conic singular values.

Motivation: The Gaussian framework is limited because Gordon’s theorem does not directly handle general sampling distributions.The chapter therefore seeks one approach for broad classes of complexity measures and sampling matrices.
Core method: The Small Ball Method lower-bounds the nonnegative empirical process associated with the minimum conic singular value.Its central estimate applies to independent copies of a random measurement vector.
Method components: The bound is obtained by estimating a marginal tail function and a distribution-dependent mean empirical width.These are the two simpler quantities used to control the conic singular value.
Interpretation: The marginal tail function measures how often measurements are close to zero, while the mean empirical width measures the size of the index set.For centered isotropic measurements, the mean empirical width converges to Gaussian width as the sample size grows.
Distributional scope: The framework is sensitive to the measurement distribution: spiky random vectors can make the marginal tail function small.This distributional dependence distinguishes the method from the Gaussian-only analysis.

MENDELSON’S SMALL BALL METHOD

Mendelson’s Small Ball Method bounds a nonnegative empirical process through marginal tail behavior and mean empirical width. Its usefulness is broad but depends on sampling assumptions and distributional conditions, with extensions still needed for some settings.

Scope: The framework applies lower-bound arguments to independent sampling rows, but it does not provide a universal prescription for every measurement ensemble.Its applicability depends on the sampling model and on obtaining suitable bounds for the relevant empirical-process quantities.
Scope: The sampling matrix must have independent, identically distributed rows, excluding examples such as random filtering.This is an explicit structural assumption of the Small Ball Method.
Scope: Heavy-tailed sampling distributions are allowed, but spiky random vectors can prevent a useful lower bound for the marginal tail function.The text identifies this as a barrier for applications such as matrix completion.
Extensions: Blocking measurements into groups is proposed as a possible extension that could reduce difficulties caused by spiky distributions, but it requires additional ideas.Complex-valued random vectors are described as an easier extension.
Core framework: The method combines lower bounds for a marginal tail function with upper bounds for mean empirical width to control a nonnegative empirical process.The proof introduces a directional marginal tail function and uses concentration, soft indicators, symmetrization, and contraction arguments.

6. A UNIVERSAL ERROR BOUND FOR SUBGAUSSIAN MEASUREMENTS

The chapter applies Mendelson’s Small Ball Method to independent subgaussian measurements and derives recovery guarantees under subgaussian, nondegeneracy, and low-eccentricity conditions. The resulting conic singular-value and signal-recovery bounds match Gaussian behavior up to constants and eccentricity dependence.

Setup: The analysis studies convex signal recovery from independent subgaussian measurements as a generalization of standard Gaussian measurements.The sampling matrix has independent copies of a random vector satisfying subgaussian marginal and low-eccentricity conditions.
Main theorem: Theorem 6.3 gives a high-probability lower bound for the minimum conic singular value of an m×d subgaussian matrix over a cone.The failure probability is bounded by e^{-ct^2}, with c and C positive absolute constants.
Comparison with Gaussian measurements: When eccentricity ρ has constant order, the conic singular-value bound matches the Gaussian result.The chapter explicitly states that it does not claim novelty for this comparison.
Signal recovery: Corollary 6.4 converts the conic singular-value estimate into stable recovery for noisy structured signals using the convex optimization problem.The guarantee holds with probability at least 1−e^{-ct^2} when the measurement error satisfies ∥e∥≤η.
Sampling complexity: The required number of subgaussian measurements is correct up to a constant factor and the precise dependence on eccentricity ρ.Standard Gaussian measurements satisfy the assumptions with ρ constant, and the comparison uses the complexity measure f.
Proof strategy: The proof combines the Small Ball Method with generic chaining to lower-bound the marginal tail function and control empirical width by conic Gaussian width.The marginal-tail estimate uses the second moment method, while the width estimate uses subgaussian increments and generic chaining.

7. THE BOWLING SCHEME

The bowling scheme extends convex recovery analysis to independent random measurements by adapting Mendelson’s Small Ball Method to descent cones. Its key step uses conic duality to control the mean empirical width through the structure of the index set.

Motivation: The chapter seeks convex recovery guarantees for sampling ensembles beyond the subgaussian setting.The approach retains the Small Ball framework while replacing the Gaussian-style width estimate with a conic-duality argument.
Mean empirical width: Proposition 7.1 bounds the mean empirical width associated with a proper convex function and its descent cone.The bound applies to independent copies of a random vector together with independent Rademacher variables.
Recovery framework: Convex recovery is analyzed by lower-bounding the minimum conic singular value over the descent cone intersected with the unit sphere.The measurements have the form y=Φx♮+e, and Proposition 2.6 supplies the deterministic recovery connection.
Specialized estimate: The proposed width estimate exploits the structure of the index set E=D(f,x♮)∩S^{d−1}.This specializes Mendelson’s general strategy rather than changing its overall framework.

THE BOWLING SCHEME

The bowling scheme specializes Mendelson’s framework by replacing its generic width step with a conic-duality estimate. It uses primal optimality for the recovery problem and applies duality only when estimating mean empirical width.

Procedure: The bowling scheme applies Proposition 5.1 to bound the minimum conic singular value and Proposition 7.1 to control mean empirical width.The latter is the specialized replacement for Step (3) in Mendelson’s framework.
Relationship to golfing: Unlike the golfing scheme, the bowling scheme is based on the primal optimality condition, with duality entering only to estimate mean empirical width.The comparison identifies the distinct role of duality in the two schemes.
Applicability: The approach has been successful when the conic Gaussian width of the descent cone can be bounded.Its setting does not require the random vector to share Gaussian rotational invariance.

8. EXAMPLE: PHASE RETRIEVAL

The section formulates phase retrieval as a lifted convex recovery problem, replacing magnitude measurements with linear measurements of a rank-one positive-semidefinite matrix. For independent Gaussian sampling vectors, the resulting trace-norm program succeeds with an essentially optimal number of measurements.

Phase retrieval recovers an unknown signal from magnitudes of linear samples by resolving uncertainty about measurement phases or signs.
Lifting converts the apparently nonlinear magnitude samples into linear functions of the rank-one matrix X ♮.The lifted model coincides with the chapter’s general linear measurement framework.
The convex program minimizes the Schatten 1-norm while enforcing positive semidefiniteness of the lifted matrix.
Unique recovery of X ♮ allows reconstruction of the original signal by factorizing the optimization solution.
m ≥ Cd Gaussian measurements recover x♮ with probability at least 1−e−cm, where c and C are positive absolute constants.The sampling vectors are independent standard Gaussian vectors.
The bound m ≥ Cd is qualitatively optimal because dimension counting requires at least m ≥ d nonadaptive linear measurements for a general vector.

The proof’s first step establishes a lower bound for the relevant nonnegative empirical process. It combines a probability estimate with Paley–Zygmund and Gaussian hypercontractivity calculations.

The mean empirical width is introduced as a quantity used in the empirical-process estimate.
Paley–Zygmund provides a lower-bound estimate, with c0 a positive absolute constant.
Gaussian hypercontractivity controls the expectation in the denominator because the measurement expression is a second-order polynomial in the Gaussian entries.
An explicit calculation for U ∈ E completes the remaining expectation bound and yields the target inequality.

8.6. Step 3′: The mean empirical width of the descent cone.

The third step bounds the mean empirical width of the descent cone using a block decomposition and estimates involving the maximum eigenvalue. Combined with the other bounds, this makes the minimum conic singular value positive with exponentially high probability.

Proposition 7.1 is used to bound the mean empirical width of the relevant descent-cone set.
Eτ^2 ≤ C4d, with C1 and C2 positive absolute constants appearing in the preceding estimates.
The matrix H is partitioned conformally with X ♮, and τ is defined as the maximum eigenvalue of its lower-right block.
Subdifferential calculus decomposes the width estimate into terms involving h11−τ, h21, and an eigenvalue-constrained approximation of H22.
The second term is directly calculated, while eigenvalue interlacing and standard net arguments control the remaining terms.
Assuming m ≥ C2d and combining the estimates makes the minimum conic singular value positive with probability at least 1−e−c4m, implying unique recovery.