Literature
Display
← All papers

Compressed Sensing

David L. Donoho

· IEEE Transactions on Information Theory 52(4), 1289–1306 ↗

Contents

At a glance

Intuition. Suppose a signal has 1,000 transform coefficients but only ten are important. Measuring all 1,000 coordinates can be wasteful. Carefully chosen mixtures of coordinates can retain enough information to reconstruct that sparse signal. The mixtures must distinguish sparse candidates; simply discarding arbitrary coordinates will not do.

Reading the math. In y = Ax, x is the unknown signal, A specifies the measurements, and y contains their observed values. Fewer measurements mean many possible solutions. Minimizing the sum of absolute coefficients, the ℓ1 norm, favors sparse explanations. Recovery depends on the measurement geometry and sparsity; compressible signals generally incur approximation error.

Compressed sensing acquires fewer nonadaptive linear measurements than the ambient signal dimension, then reconstructs by a nonlinear algorithm. The assumption is compressibility in a known orthonormal basis or frame. This paper uses optimal recovery and geometric widths to characterize attainable worst-case error, exhibits random measurement ensembles with the required structure, and proves near-optimal recovery by convex ℓ1 minimization for coefficient classes with 0<p≤1. Its applications are stylized mathematical models, rather than experimental guarantees for arbitrary natural images.

I · Introduction

Transform compression suggests measuring the information a signal retains after compression instead of first acquiring every pixel. The proposed measurements mix many coefficients and are fixed independently of the unknown signal. Sparse structure makes this underdetermined inverse problem recoverable; without a compressibility assumption, fewer linear measurements cannot recover every ambient vector. Nonlinear reconstruction is essential to the proposed acquisition scheme.

I.A · Transform compression background

The coefficient vector belongs to an ℓp ball of radius R in a specified transform. The best N-term approximation retains its largest coefficients, with ℓ2 error bounded by a p-dependent constant times R(N+1)^(1/2−1/p), for 0<p<2. Smaller p imposes stronger compressibility. Bounded-variation images and bump-algebra spectra motivate scale-dependent coefficient bounds; they are particular function classes, not assumptions verified for every measured object.

Equations I.1–I.2
I.1Original mathematical display, printed page 1289
p.1289Original mathematical display, printed page 1289
p.1290Original mathematical display, printed page 1290
I.2Original mathematical display, printed page 1290

I.B · Optimal recovery and information complexity

An information operator measures n fixed linear functionals; a reconstruction algorithm may be nonlinear. The minimax error takes the worst signal in the specified class and then optimizes jointly over information operators and reconstruction rules. This benchmark distinguishes an existence result for a near-optimal measurement space from an efficient computational procedure using that space.

Equations p.1290–p.1290
p.1290Original mathematical display, printed page 1290
p.1290Original mathematical display, printed page 1290
p.1290Original mathematical display, printed page 1290

I.C · Four surprises and Theorems 1–2

For problem sequences with n tending to infinity and ambient dimension m growing polynomially in n, Theorem 1 gives a compressibility-dependent error scale proportional to R(n/log m)^(1/2−1/p), with constants depending on the growth parameters and p. This matches best-term approximation up to the logarithmic measurement overhead. Theorem 2 bounds the advantage of adaptive linear measurements by a p-dependent constant in this worst-case model. It does not rule out task-specific benefits of adaptivity under other signal classes, noise models, or average-case objectives.

Equations I.3–p.1291
I.3Original mathematical display, printed page 1290
p.1291Original mathematical display, printed page 1291
p.1291Original mathematical display, printed page 1291
p.1291Original mathematical display, printed page 1291

I.D · Geometry and widths

A Gel’fand width asks for a measurement nullspace whose intersection with the signal class has small Euclidean radius. A Kolmogorov width instead measures approximation by a low-dimensional subspace. Theorem 3 connects the former to minimax recovery, exactly in the convex p=1 case and within a p-dependent constant for 0<p<1. Duality and the Kashin–Garnaev–Gluskin result explain the p=1 rate; the paper develops a direct route for the nonconvex coefficient classes.

Equations p.1291–p.1292
p.1291Original mathematical display, printed page 1291
I.4, I.5Original mathematical display, printed page 1291
p.1291Original mathematical display, printed page 1291
I.6Original mathematical display, printed page 1291
p.1291Original mathematical display, printed page 1291
p.1292Original mathematical display, printed page 1292

I.E · Why existence is insufficient

Classical width arguments establish favorable subspaces without identifying a practical sensing matrix and reconstruction method. The abstract central algorithm finds the center of all admissible signals consistent with the measurements. It is minimax-optimal, but the nonconvex feasible set and unknown class parameters make that description computationally unhelpful. The next results provide concrete matrix conditions and an ℓ1 reconstruction rule.

Equations p.1292–p.1292
p.1292Original mathematical display, printed page 1292
p.1292Original mathematical display, printed page 1292
p.1292Original mathematical display, printed page 1292
p.1292Original mathematical display, printed page 1292

I.F · Information and algorithmic results

Conditions CS1–CS3 certify a near-optimal nullspace. Independent uniformly distributed unit-vector columns generate matrices satisfying those conditions with overwhelming probability in the stated asymptotic regime. Measurements combine this matrix with the signal transform. Basis Pursuit minimizes the coefficient ℓ1 norm subject to exact measurement consistency. Theorem 5 combines near-optimal information and near-optimal reconstruction over all 0<p≤1 without requiring the algorithm to know p or R.

Equations p.1292–p.1293
p.1292Original mathematical display, printed page 1292
p.1292Original mathematical display, printed page 1292
p.1292Original mathematical display, printed page 1292
p.1292Original mathematical display, printed page 1292
p.1293Original mathematical display, printed page 1293

I.G · Potential applications

The introduction forecasts large measurement reductions for modeled spectra, bounded-variation images, and cartoon-like images. These comparisons match a target approximation error to that of a classical sampling scheme, keeping logarithmic factors and class-dependent constants. They are asymptotic acquisition bounds for purpose-designed linear measurements, not claims that arbitrary subsampling or a particular physical scanner automatically achieves the same rates.

I.H · Structure of the argument

The paper separates geometric information bounds, abstract recovery algorithms, tractable Basis Pursuit, function-space extensions, stylized applications, and the random-matrix existence proof. Its concluding comparison with partial Fourier sampling links this width-based approach to contemporary sparse-recovery work.

II · Information

After transferring into coefficient coordinates, the analysis can take the transform to be the identity. The width relative to a matrix is the largest ℓ2 norm of a class member in its nullspace. Minimizing that radius over matrices gives the Gel’fand width. The aim is a nullspace radius within a constant factor of optimal, rather than an invertible map on the entire ambient space.

Equations II.1–p.1293
II.1Original mathematical display, printed page 1293
p.1293Original mathematical display, printed page 1293
p.1293Original mathematical display, printed page 1293

II.A · Conditions CS1–CS3

For every sufficiently small column subset J, CS1 lower-bounds its minimum singular value; CS2 compares ℓ1 and ℓ2 norms on its column span; CS3 lower-bounds a quotient norm describing representation using complementary columns. The subset threshold is proportional to n/log m, with fixed positive constants independent of the growing dimensions. Theorem 6 asserts that these properties jointly hold for almost all matrices in the specified unit-column ensemble. Merely choosing dimension-dependent tiny constants would not supply the same result.

Equations p.1293–p.1294
p.1293Original mathematical display, printed page 1293
p.1293Original mathematical display, printed page 1293
p.1293Original mathematical display, printed page 1293
p.1294Original mathematical display, printed page 1294

II.B · Theorem7: near-optimal CS matrices

The proof orders a nullspace vector by decreasing coefficient size and divides it into its largest entries and tail. Compressibility bounds the tail; CS3 converts its representation cost into an ℓ1 bound on the corresponding measurement vector; CS2 converts that to ℓ2; and CS1 controls the leading coefficients. Combining head and tail gives the desired nullspace-width bound. This is a uniform statement over the specified coefficient class after a matrix satisfies all three conditions.

Equations p.1294–p.1294
p.1294Original mathematical display, printed page 1294
p.1294Original mathematical display, printed page 1294
p.1294Original mathematical display, printed page 1294
II.2Original mathematical display, printed page 1294
II.3Original mathematical display, printed page 1294
II.4Original mathematical display, printed page 1294
p.1294Original mathematical display, printed page 1294
p.1294Original mathematical display, printed page 1294
p.1294Original mathematical display, printed page 1294
p.1294Original mathematical display, printed page 1294
p.1294Original mathematical display, printed page 1294
p.1294Original mathematical display, printed page 1294

III · Algorithms

An information bound alone does not provide an efficient reconstruction. This section first uses abstract feasible-point methods to connect widths with minimax error and prove the introductory theorems. SectionIV then replaces those abstract methods with the tractable convex program.

III.A · Feasible-point methods

Lemma 3.1 shows that any signal consistent with the measured data and the known class lies within twice the optimal worst-case error when the information operator is optimal. The central algorithm realizes the radius of each measurement fiber; the triangle inequality bounds the distance from another feasible point. The same argument applies with the operator’s own optimal error when its information is only near-optimal. Minimizing the coefficient ℓp norm avoids knowing R, but remains nonconvex when p<1.

Equations p.1294–p.1295
p.1294Original mathematical display, printed page 1294
III.1Original mathematical display, printed page 1295
p.1295Original mathematical display, printed page 1295
p.1295Original mathematical display, printed page 1295
p.1295Original mathematical display, printed page 1295
p.1295Original mathematical display, printed page 1295
p.1295Original mathematical display, printed page 1295
III.2Original mathematical display, printed page 1295
p.1295Original mathematical display, printed page 1295
p.1295Original mathematical display, printed page 1295

III.B · Proof of Theorem3

For 0<p<1, the p-triangle inequality controls the quasi-norm of a scaled difference of two signals from the same measurement fiber. That difference lies in the nullspace, so the Gel’fand radius bounds it. Comparing the fiber radius with the nullspace radius gives the stated p-dependent bracketing. This is the mechanism extending the convex optimal-recovery relation to the nonconvex ℓp balls.

Equations p.1295–p.1295
p.1295Original mathematical display, printed page 1295
p.1295Original mathematical display, printed page 1295
p.1295Original mathematical display, printed page 1295
p.1295Original mathematical display, printed page 1295
p.1295Original mathematical display, printed page 1295
p.1295Original mathematical display, printed page 1295
p.1295Original mathematical display, printed page 1295
p.1295Original mathematical display, printed page 1295

III.C · Proof of Theorem1

For p<1, entropy-number lower bounds and Carl’s comparison inequality give one side of the minimax rate. The random-matrix construction and the CS-width theorem give the matching upper order; feasible-point recovery transfers it into an algorithmic error bound. Constants and the polynomial dimension-growth regime remain part of this asymptotic comparison.

Equations p.1296–p.1296
p.1296Original mathematical display, printed page 1296
p.1296Original mathematical display, printed page 1296
p.1296Original mathematical display, printed page 1296
p.1296Original mathematical display, printed page 1296
p.1296Original mathematical display, printed page 1296

III.D · Proof of Theorem2

Run an adaptive linear-measurement strategy on the zero signal. All class members in the resulting nullspace produce the same observations along that branch. Their remaining uncertainty lower-bounds the strategy’s minimax error by a Gel’fand width. Comparing with the nonadaptive width bound limits the advantage of adaptivity in this symmetric worst-case setting.

Equation p.1296
p.1296Original mathematical display, printed page 1296

IV · Basis Pursuit

The previous least-ℓp method depends on p and becomes a nonconvex optimization for p<1. Basis Pursuit removes both difficulties by using the same ℓ1 objective across all the compressible classes studied here.

IV.A · The case p=1

Split each real coefficient into positive and negative parts to write ℓ1 minimization as a linear program. For p=1, the feasible-point argument immediately makes this procedure near-optimal with near-optimal information. The source’s relative-error illustration additionally needs a relation between the signal norm and its ℓ1 bound: an absolute bound in terms of R does not alone establish a relative error bound for arbitrarily small signals.

Equations p.1296–p.1296
p.1296Original mathematical display, printed page 1296
IV.1Original mathematical display, printed page 1296
p.1296Original mathematical display, printed page 1296
p.1296Original mathematical display, printed page 1296
p.1296Original mathematical display, printed page 1296
p.1296Original mathematical display, printed page 1296

IV.B · Relation between ℓ1 and ℓ0 minimization

Theorem 8 proves that a sufficiently sparse exact solution is the unique minimizer of both the counting objective and the ℓ1 program when CS1–CS3 hold. Lemma 4.1 bounds how much ℓ1 mass any nullspace vector can concentrate on a small set. If that fraction is below one half on the true support, every nonzero feasible perturbation increases the objective. This nullspace property, rather than sparsity alone, explains exact recovery.

Equations p.1297–p.1297
p.1297Original mathematical display, printed page 1297
p.1297Original mathematical display, printed page 1297
p.1297Original mathematical display, printed page 1297
p.1297Original mathematical display, printed page 1297
p.1297Original mathematical display, printed page 1297
p.1297Original mathematical display, printed page 1297
p.1297Original mathematical display, printed page 1297
p.1297Original mathematical display, printed page 1297
p.1297Original mathematical display, printed page 1297
p.1297Original mathematical display, printed page 1297
p.1297Original mathematical display, printed page 1297

IV.C · Theorem9: near-optimality for 0<p<1

Lemma 4.2 proves an ℓ1 stability estimate when the coefficient tail outside a chosen support is small and nullspace concentration there is below one half. The proof uses optimality of the ℓ1 solution and separates support and complement. Theorem 9 combines that stability estimate with compressibility and the CS-width bound, yielding an ℓ2 approximation rate for nonsparse but compressible vectors. This coefficient-tail stability argument should be distinguished from a complete general theorem for arbitrary measurement noise.

Equations p.1297–p.1298
p.1297Original mathematical display, printed page 1297
p.1298Original mathematical display, printed page 1298
IV.2Original mathematical display, printed page 1298
p.1298Original mathematical display, printed page 1298
p.1298Original mathematical display, printed page 1298
p.1298Original mathematical display, printed page 1298
p.1298Original mathematical display, printed page 1298
p.1298Original mathematical display, printed page 1298
p.1298Original mathematical display, printed page 1298
p.1298Original mathematical display, printed page 1298
p.1298Original mathematical display, printed page 1298
p.1298Original mathematical display, printed page 1298
IV.3Original mathematical display, printed page 1298
p.1298Original mathematical display, printed page 1298
p.1298Original mathematical display, printed page 1298
p.1298Original mathematical display, printed page 1298

V · Immediate extensions

The proof uses structural properties of the transform and coefficient tails that extend beyond a finite orthonormal basis. The two following extensions identify which ingredients must be preserved.

V.A · Tight frames

Parseval tight frames preserve the norm and reconstruction identities required by the width and Basis Pursuit arguments. The paper therefore extends the scheme to redundant coefficient systems such as curvelets. A referee’s observation also permits general frames with constants depending on their frame bounds; redundancy does not remove the need to account for those bounds.

Equations p.1298–p.1298
p.1298Original mathematical display, printed page 1298
p.1298Original mathematical display, printed page 1298

V.B · Weak ℓp balls

A weak-ℓp constraint bounds the decreasing rearrangement of coefficient magnitudes rather than their full ℓp sum. It supplies the same type of best-term tail estimate needed in the proofs, so the recovery arguments extend to these classes. The weak quantity is a quasi-norm in the relevant range, and the constants and admissible p range remain part of the estimates.

Equations p.1298–V.1
p.1298Original mathematical display, printed page 1298
V.1Original mathematical display, printed page 1298

VI · Stylized applications

Each example first proves coefficient compressibility for a specified function class and then balances coarse direct samples against compressed fine-scale measurements. The conclusions compare acquisition complexity at matched approximation error. They are mathematical constructions, not reported sensor trials.

VI.A · Bump algebra

For modeled spectra, smooth-wavelet coefficients decay across scales in ℓ1. Coarse scaling coefficients are measured directly; finer detail coefficients are acquired through a CS matrix and reconstructed by Basis Pursuit. Balancing their errors gives roughly a cube-root reduction in the sample count relative to the classical scheme, up to logarithmic factors. The sensing kernels are linear combinations of wavelets, rather than simply a small subset of point samples.

Equations p.1299–VI.1
p.1299Original mathematical display, printed page 1299
p.1299Original mathematical display, printed page 1299
p.1299Original mathematical display, printed page 1299
p.1299Original mathematical display, printed page 1299
p.1299Original mathematical display, printed page 1299
p.1299Original mathematical display, printed page 1299
VI.1Original mathematical display, printed page 1299

VI.B · Bounded-variation images

The two-dimensional Haar construction uses bounded variation and a bounded signal amplitude to control coefficients. Again a coarse direct component is combined with compressed detail measurements. The resulting error matches the classical sampling order with roughly a square-root number of measurements, retaining the logarithmic factors shown in the source. The image-class assumptions and the chosen multiscale measurement operator are essential.

Equations p.1299–p.1300
p.1299Original mathematical display, printed page 1299
p.1299Original mathematical display, printed page 1299
p.1299Original mathematical display, printed page 1299
p.1299Original mathematical display, printed page 1299
p.1300Original mathematical display, printed page 1300
p.1300Original mathematical display, printed page 1300
p.1300Original mathematical display, printed page 1300

VI.C · Piecewise C² images with C² edges

The cartoon model consists of bounded smooth regions separated by controlled smooth curves. Curvelet tight frames provide weak-ℓ(2/3) coefficient control. Combining that redundancy-aware representation with the weak-space extension leads to roughly a fourth-root sample count at comparable error, with logarithmic factors. It is a specialized regularity model and does not assert the same rate for arbitrary textured imagery.

Equations p.1300–p.1300
p.1300Original mathematical display, printed page 1300
p.1300Original mathematical display, printed page 1300
p.1300Original mathematical display, printed page 1300
p.1300Original mathematical display, printed page 1300
p.1300Original mathematical display, printed page 1300
p.1300Original mathematical display, printed page 1300
p.1300Original mathematical display, printed page 1300
p.1300Original mathematical display, printed page 1300
p.1300Original mathematical display, printed page 1300

VII · Nearly all matrices are CS matrices

Theorem 10 restates the existence result for columns sampled independently and uniformly from the unit sphere, with polynomially growing ambient dimension. The proof separately makes CS1, CS2, and CS3 likely and intersects their events. Failure probabilities decay exponentially for suitable fixed constants and sufficiently large dimensions. This is a probability statement over the prescribed matrix ensemble, not a certificate for every realized matrix.

Equations p.1301–p.1301
p.1301Original mathematical display, printed page 1301
p.1301Original mathematical display, printed page 1301

VII.A · Controlling the minimum eigenvalue

Lemmas7.1–7.3 combine a fixed-subset random-matrix singular-value bound with a counting and union-bound argument over all small subsets. Restricting subset size to order n/log m keeps the combinatorial cost below the exponential probability bound. The resulting simultaneous lower singular-value control supplies CS1.

Equations p.1301–p.1301
p.1301Original mathematical display, printed page 1301
p.1301Original mathematical display, printed page 1301
p.1301Original mathematical display, printed page 1301
p.1301Original mathematical display, printed page 1301
p.1301Original mathematical display, printed page 1301
p.1301Original mathematical display, printed page 1301
p.1301Original mathematical display, printed page 1301
p.1301Original mathematical display, printed page 1301
p.1301Original mathematical display, printed page 1301

VII.B · Spherical sections

The almost-spherical-section phenomenon compares ℓ1 and ℓ2 norms on random low-dimensional spans. Lemma 7.5 gives a fixed-subset estimate with explicit parameter constraints; Lemma 7.3 upgrades it to every admissible column subset. Lemma 7.4 therefore supplies CS2. Concentration and counting must be balanced; a typical individual span alone would not prove the uniform condition.

Equations VII.1–p.1302
VII.1Original mathematical display, printed page 1301
p.1302Original mathematical display, printed page 1302
VII.2Original mathematical display, printed page 1302
VII.3Original mathematical display, printed page 1302
p.1302Original mathematical display, printed page 1302
p.1302Original mathematical display, printed page 1302
p.1302Original mathematical display, printed page 1302

VII.C · Quotient norms and duality

The quotient ℓ1 minimization problem has a dual feasible region defined by correlations with complementary columns. Lemma 7.6 constructs vectors close to scaled sign patterns while controlling those correlations. Pairing such a vector with the target gives a lower bound on the primal representation cost, hence CS3. The individual embedding estimate is upgraded to a uniform one using a bound on the number of realizable sign patterns.

Equations p.1302–p.1303
p.1302Original mathematical display, printed page 1302
VII.4Original mathematical display, printed page 1302
VII.5Original mathematical display, printed page 1302
VII.6Original mathematical display, printed page 1302
VII.7Original mathematical display, printed page 1302
VII.8Original mathematical display, printed page 1302
p.1302Original mathematical display, printed page 1302
p.1302Original mathematical display, printed page 1302
VII.9Original mathematical display, printed page 1302
VII.10Original mathematical display, printed page 1302
VII.11Original mathematical display, printed page 1302
p.1303Original mathematical display, printed page 1303
p.1303Original mathematical display, printed page 1303
p.1303Original mathematical display, printed page 1303
p.1303Original mathematical display, printed page 1303
p.1303Original mathematical display, printed page 1303
p.1303Original mathematical display, printed page 1303

VII.D · Individual sign-pattern embedding

The remaining proof constructs a nearby dual-feasible vector and controls its trajectory. The algorithmic construction, its pathwise bounds, and the large-deviation calculation are separate steps; all three are needed for the uniform quotient-norm argument.

VII.D.1 · An embedding algorithm

Begin from an approximate sign-pattern vector. At each stage identify columns with excessive correlation and project out their span. Thresholds approach the dual feasibility boundary, and the procedure terminates after at most n stages. Termination certifies feasibility; the separate probability analysis is needed to show that the cumulative displacement remains small.

Equations p.1303–p.1303
p.1303Original mathematical display, printed page 1303
p.1303Original mathematical display, printed page 1303
p.1303Original mathematical display, printed page 1303
p.1303Original mathematical display, printed page 1303
p.1303Original mathematical display, printed page 1303

VII.D.2 · Analysis framework

The proof tracks the norms of successive corrections and the number of remaining high-correlation indices. Geometric bounds on these quantities imply a bound on total displacement. A sequence of good trajectory events is arranged so that controlling their conditional failure probabilities yields the individual embedding result.

Equations p.1303–p.1303
p.1303Original mathematical display, printed page 1303
p.1303Original mathematical display, printed page 1303
p.1303Original mathematical display, printed page 1303
p.1303Original mathematical display, printed page 1303
p.1303Original mathematical display, printed page 1303
p.1303Original mathematical display, printed page 1303
VII.12Original mathematical display, printed page 1303
p.1303Original mathematical display, printed page 1303

VII.D.3 · Large deviations

Minimum-eigenvalue control ensures that the required projections remain well conditioned. The analysis reduces trajectory failures to Gaussian tail counts and truncated-square sums. Lemma 7.8 bounds these events exponentially; the chosen thresholds and constants leave a positive exponent. Some supporting distributional arguments are imported from the companion paper, as the source explicitly notes.

Equations p.1303–p.1304
p.1303Original mathematical display, printed page 1303
p.1303Original mathematical display, printed page 1303
p.1303Original mathematical display, printed page 1303
p.1304Original mathematical display, printed page 1304
p.1304Original mathematical display, printed page 1304
p.1304Original mathematical display, printed page 1304
p.1304Original mathematical display, printed page 1304
p.1304Original mathematical display, printed page 1304
p.1304Original mathematical display, printed page 1304
p.1304Original mathematical display, printed page 1304
p.1304Original mathematical display, printed page 1304
p.1304Original mathematical display, printed page 1304
p.1304Original mathematical display, printed page 1304
p.1304Original mathematical display, printed page 1304
p.1304Original mathematical display, printed page 1304
p.1304Original mathematical display, printed page 1304
p.1304Original mathematical display, printed page 1304
p.1304Original mathematical display, printed page 1304
p.1304Original mathematical display, printed page 1304

VIII · Conclusion

The completed scheme joins compressibility, a suitable sensing matrix, and convex reconstruction. The practical promise is reduced acquisition at an error rate close to the optimal-recovery benchmark. Its theorem statements retain their signal-class, matrix, exact-data, and asymptotic assumptions.

VIII.A · Summary

The measurement operator composes the CS matrix with a known coefficient transform; reconstruction minimizes the transformed ℓ1 norm under measurement constraints. The paper derives approximation bounds and motivates imaging and spectroscopy applications. Its broad concluding mention of small measurement errors goes beyond the main exact-consistency statements developed here; those results should not be read as an unrestricted noise-robustness theorem.

Equation p.1304
p.1304Original mathematical display, printed page 1304

VIII.B · Alternative formulation

Theorem 11 shows that CS1–CS3 are sufficient rather than uniquely necessary. A small nullspace-concentration bound on thin coordinate sets and a favorable ℓ1-ball width suffice for the same recovery argument. This formulation separates the geometric properties actually used from one particular probabilistic construction.

Equations VIII.1–p.1305
VIII.1Original mathematical display, printed page 1305
VIII.2Original mathematical display, printed page 1305
p.1305Original mathematical display, printed page 1305

VIII.C · Partial Fourier ensembles

The discussion connects the framework with Candès–Romberg–Tao exact sparse Fourier recovery and Gilbert and collaborators’ near-best Fourier approximation work. It distinguishes uniform and nonuniform row-sampling distributions and the different concentration and width properties obtained from them. These links motivate structured sensing operators, rather than making every partial Fourier matrix satisfy the same guarantee. [13, 12]

Note added in proof

The historical note points to emerging numerical and sensor studies and related data-stream ideas. It records the state of the surrounding work at publication. Those announcements are not additional experiments conducted or quantified in this article.

Acknowledgment

Donoho credits conversations with Emmanuel Candès about undersampled imaging and partial Fourier results, and with Anna Gilbert about nonadaptive Fourier approximation and data streams. These acknowledgments distinguish the present width-based development from related contemporary contributions.

Concept demonstration

Open image ↗