PaperlayerView exact revision on arXiv

Source-linked AI summary

Estimation in high dimensions: a geometric perspective

Roman Vershynin

arXiv:1405.5103v2math.STstat.TH

TL;DR

High-dimensional estimation seeks to recover an unknown from limited observations while respecting constraints that encode known or desired properties. This tutorial develops geometric intuition and connects asymptotic convex geometry to estimation; for rank-r matrix recovery, it reports approximate recovery from a number of random linear observations on the order of r(d1 + d2).

  • Problem

    The chapter concerns estimating an unknown point from a small sample when the point is constrained to a known feasible set.

    Source: §1.1 · p. 2

  • Method

    The tutorial develops geometric intuition about feasible sets and uses results from asymptotic convex geometry to connect their geometry with estimation.

    Source: §1.1 · p. 2

  • Results

    Using convex programming, a rank-r or effective-rank-r matrix can be approximately recovered from m ∼ r(d1 + d2) random linear observations.

    Source: §10.3.2 · p. 39

  • Takeaways & Limitations

    The geometry of the feasible set K is a key to understanding high-dimensional estimation problems.

    Source: §1.1 · p. 2

    General feasible sets lack quantified incoherence results for reconstruction from random Fourier measurements, although sparse-vector cases have restricted-isometry results.

    Source: §14.2 · p. 53

Abstract

from arXiv · show

This tutorial provides an exposition of a flexible geometric framework for high dimensional estimation problems with constraints. The tutorial develops geometric intuition about high dimensional sets, justifies it with some results of asymptotic convex geometry, and demonstrates connections between geometric results and estimation problems. The theory is illustrated with applications to sparse recovery, matrix completion, quantization, linear and logistic regression and generalized linear models.

1. Introduction

The chapter presents a geometric tutorial for constrained high-dimensional estimation, using asymptotic convex geometry to connect the structure of feasible sets with estimation problems. It illustrates the framework across linear and nonlinear observations while aiming for a general approach not tied to a particular feasible set.

1. Introduction

  • The chapter introduces constrained estimation by treating the feasible set K as prior structure that may permit estimation from few observations.It first formulates estimators for linear observations as feasibility and then optimization problems.Source: §1.1 · p. 2, §1.3 · p. 3

1.1. Estimation with constraints.

  • The tutorial develops geometric intuition about high-dimensional sets, explains results that support it, and connects those ideas to estimation problems.It proposes a geometric viewpoint as common mathematical ground for otherwise dissimilar estimation problems.Source: §1.1 · p. 2

1.2. Quick examples.

  • Examples include sparse and structured-sparse recovery, low-rank matrix completion, binary observations, linear regression, logistic regression, and generalized linear models.The chapter’s general approach is not tied to a particular feasible set K.Source: §1.2 · pp. 2–3

1.3. Plan of the chapter.

  • The geometric background emphasizes mean width and the M* bound on the size of high-dimensional sections by a random subspace.The bound depends on mean width, a parameter used to quantify the complexity of K.Source: §1.3 · p. 3
  • For noisy linear observations, the chapter applies the M* bound to sparse recovery and constrained linear regression, then extends the theory to sub-gaussian observations.The sub-gaussian bound follows the Gaussian argument with a comparison theorem [71]. Exact recovery is also treated using Gordon’s “escape through a mesh” theorem [31].Source: §1.3 · p. 3
  • For single-bit observations, estimation is framed through random hyperplane tessellations and feasibility, while later sections address convex optimization and general nonlinear observations.The chapter also outlines extensions to general distributions and localized mean width.Source: §1.3 · p. 4

2. High dimensional estimation problems

The section frames high-dimensional estimation as recovering an unknown vector from independent observations, with a known feasible set encoding properties of that vector. Its central motivation is that low-complexity structure can reduce the observations needed, even when the feasible set has full algebraic dimension.

2. High dimensional estimation problems

  • Estimation seeks an unknown vector from independent observations whose distribution depends on that vector.The vector may represent a signal or a statistical parameter.Source: §2 · p. 4

2.2. Low complexity structures.

  • A known feasible set K can encode prior or desired properties of the unknown, such as sparsity in a regression coefficient vector.Figure 1 depicts sampling as a map from x in K to y and estimation as a map back to an estimate in K, ideally the inverse.Source: §2.2 · p. 5, Figure 1 · p. 5
  • Low-complexity structure may allow estimation with fewer observations, even though useful sets such as s-sparse vectors can have full algebraic dimension.The chapter sets goals to quantify complexity, establish estimation from few observations, and design efficient estimators.Source: §2.2 · pp. 5–6

3. An excursion into high dimensional convex geometry

The chapter develops a bulk-and-outliers picture of high-dimensional geometry and uses results from asymptotic convex geometry to connect that picture to random sections and mean width. It presents mean width as a way to quantify geometric complexity, with links to estimation, stochastic processes, and learning theory.

3. An excursion into high dimensional convex geometry

  • High-dimensional convex bodies are heuristically described as a small-diameter bulk containing most volume and large-diameter outliers containing little; proper scaling makes the bulk roughly Euclidean and the outliers thin tentacles.The chapter motivates this picture by noting that dilation by 2 multiplies volume by 2^n, helping explain why tentacles can contain exponentially less volume than the bulk.Source: §3.1 · p. 6

3.2. Concentration of volume.

  • For isotropic convex bodies, most volume lies near the sphere of radius √n, while outliers have exponentially small volume.Isotropy here means a uniform random point has zero mean and identity covariance; the results include concentration and a thin-shell statement.Source: §3.2 · pp. 7–8

3.3. Low dimensional random sections.

  • With high probability, random sections of dimension d ∼ log n are round under Dvoretzky’s theorem, although bulk concentration alone does not imply a round bulk.The unit cube is identified as the worst convex set in the theorem; the stated version fixes ε and takes d = cε^-2 log n.Source: §3.3 · pp. 8–9

3.5. Mean width.

  • Mean width averages a set’s directional widths; its Gaussian and spherical versions differ by a factor of about √n.Directional width is the smallest slab width between parallel hyperplanes with a given normal; the chapter mostly uses Gaussian mean width.Source: §3.5 · p. 10, §3.5.1 · p. 11

3.5.1. Simple properties of mean width.

  • Mean width is invariant under translation, orthogonal transformations, and convexification, and the chapter illustrates its computation on sparse-vector and low-rank matrix sets.The convex-hull invariance is noted as useful for convex relaxations.Source: §3.5.1 · p. 11, §3.5.2 · pp. 11–12

3.5.3. Computing mean width algorithmically.

  • A single Gaussian sample can estimate mean width with high probability, and computing the resulting estimator is a convex optimization problem.For a polytope, the optimization is often linear.Source: §3.5.3 · p. 12

3.5.4. Computing mean width theoretically.

  • Sudakov’s and Dudley’s inequalities bound mean width using covering numbers, but neither is tight for every set; generic chaining gives a tighter, more complex estimate.The chapter also mentions Gaussian-process comparison inequalities and VC-dimension methods for controlling mean width.Source: §3.5.4 · p. 12

3.5.5. Mean width and Gaussian processes.

  • Mean width measures the size of a Gaussian process and the complexity of function classes; for sets in the unit ball, its square is a robust effective dimension bounded by algebraic dimension.A small perturbation of the set leads to a small change in this effective dimension.Source: §3.5.4 · p. 13, §3.5.5 · p. 13, §3.5.6 · p. 13

3.6. Random sections of small codimension: M∗bound.

The M∗ bound controls the expected diameter of a random section using the set’s mean width and the section’s codimension. Its geometric interpretation is that sections of proportional dimension pass through the bulk and largely miss the outliers.

3.6. Random sections of small codimension: M∗bound.

  • For a random subspace E of fixed codimension m, E diam(K ∩ E) ≤ Cw(K)/√m.The bound applies to any bounded subset K of R^n.Source: §3.6 · p. 13
  • The bound depends on the codimension and mean width, a geometric quantity used to measure the size of the bulk.The chapter identifies mean width as the single geometric parameter of K in this estimate.Source: §3.6 · pp. 13–14
  • When m = Ω(n), the bound limits section size by the spherical mean width, so proportional-dimensional sections pass through the bulk and ignore outliers.As the subspace dimension approaches n and codimension decreases, the section diameter grows.Source: §3.6 · p. 14

4. From geometry to estimation: linear observations

The chapter connects the geometry of a known feasible set K to estimation from fewer Gaussian linear observations than unknown coordinates. Feasibility and gauge-minimization estimators inherit mean-width error guarantees, while convexification and effective dimension explain tractability and observation requirements.

4. From geometry to estimation: linear observations

  • When m < n, estimating x from y = Ax is ill posed without using the known feasible set K.The section studies Gaussian linear observations; when m ≥ n, the linear system is well posed almost surely.Source: §4 · p. 14

4.1. Estimation based on M∗bound.

  • Any estimate in K satisfying Abx = y has a mean-width error bound under Gaussian linear observations.The proof controls the error through the diameter of a random section of K − K.Source: §4.1 · p. 15

4.2. Estimation as an optimization problem.

  • Minimizing K’s Minkowski functional subject to Ax′ = y achieves the same error guarantee when K is star-shaped with nonempty interior.Star-shapedness ensures the touching point in the dilation view remains in K.Source: §4.2 · pp. 16–17

4.3. Algorithmic aspects: convex programming.

  • Replacing a nonconvex K by conv(K) preserves mean width and the estimation guarantee, yielding a convex program when its gauge is computable.The text notes that this computation is possible for many, but not all, feasible sets.Source: §4.3 · p. 17

4.4. Information-theoretic aspects: effective dimension.

  • The squared mean width w(K)^2 acts as an effective dimension: a sufficient observation count is of that order up to a constant factor.The accuracy guarantee is uniform over x ∈ K, and the probability approaches 1 exponentially fast in m.Source: §4.4 · p. 18

5. High dimensional sections: proof of a general M∗bound

The chapter proves a general M∗ bound for Gaussian measurements and uses it to extend geometric control of random sections to deviation-constrained sets. Symmetrization and contraction establish the expectation bound, while Gaussian concentration upgrades it to high probability.

5. High dimensional sections: proof of a general M∗bound

  • The general M∗ bound treats bounded T under Gaussian measurements and a deviation threshold ε, extending the framework toward noisy and non-Gaussian observations.The stated extension to non-Gaussian observations is presented as a further generalization of the result.Source: §5 · p. 18

5.1. Proof of Theorem 5.1.

  • The proof derives the deviation inequality using symmetrization and contraction, then identifies the resulting Gaussian process through rotation invariance.The argument applies the inequalities to the smaller threshold-constrained set Tε.Source: §5 · p. 19, §5.1 · pp. 19–20

5.2. From expectation to overwhelming probability.

  • Gaussian concentration upgrades the expectation deviation bound and the resulting M∗ bound to high-probability versions.The chapter notes that the survey’s expected-value statements can generally be upgraded using concentration of measure.Source: §5.1 · p. 20, §5.2 · pp. 20–21

6. Consequences: estimation from noisy linear observations

The chapter extends constrained estimation from exact to noisy Gaussian linear observations, allowing the noise to be arbitrary and even dependent on the measurement matrix. It provides feasibility and optimization formulations, with the latter also expressible as a convex program.

6. Consequences: estimation from noisy linear observations

  • For noisy observations, the noise may have arbitrary structure and may depend on A, so the setting includes adversarial errors.The feasibility result generalizes the earlier exact-observation estimator to noisy measurements.Source: §6 · p. 21
  • Noisy estimation can also be posed as an optimization program over bounded star-shaped feasible sets with nonempty interior.The program minimizes the feasible-set gauge while allowing a bounded measurement residual.Source: §6 · p. 22
  • The noisy estimation problem can be formulated as a convex program.The text states that the algorithmic remarks for the exact-observation setting also apply here.Source: §6 · p. 22

7. Applications to sparse recovery and regression

The section applies a geometric estimation framework to sparse vectors, including vectors represented in general dictionaries, and to constrained linear regression. It shows how convex recovery, effective sparsity, and solution geometry shape what can be recovered.

7.1. Sparse recovery for general dictionaries.

  • Theorem 7.1 treats sparse recovery with general dictionaries whose vectors satisfy ∥di∥2 ≤ 1, deriving an error bound for recovering x from noisy observations y ∈ R^m.The observation model uses a known m × n Gaussian matrix and unknown noise of arbitrary structure, including noise correlated with A.Source: §7.1 · pp. 23–24

7.2. Remarkable properties of sparse recovery.

  • The dictionary may be linearly dependent, and an arbitrarily small generic perturbation of its elements yields a unique solution almost surely.The theorem's normalization can be relaxed at the cost of increasing the error bound by maxi ∥di∥2.Source: §7.2.1 · p. 24, §7.2.5 · p. 26

7.2.2. Effective sparsity.

  • The recovery guarantee extends to effectively sparse vectors, a notion bounded by exact sparsity and robust to small perturbations.The theorem's sparsity condition can be replaced by effective sparsity.Source: §7.2.2 · p. 25

7.2.3. Linear programming.

  • The convex recovery programs can be reformulated as linear programs by introducing variables to represent absolute values and linearizing the residual constraint.The passage describes replacing the ℓ1 objective and constraint with linear expressions and constraints.Source: §7.2.3 · p. 25

7.2.4. Estimating the coefficients of sparse representation.

  • The recovery program estimates both the vector and its dictionary coefficients, and a unique coefficient solution is m-sparse even with noise or without a sparsity assumption on the target.Uniqueness is not guaranteed for every dictionary; for example, it fails when d1 = d2.Source: §7.2.4 · p. 25, §7.2.5 · pp. 25–26

7.3. Sparse recovery for the canonical dictionary.

  • For the canonical basis, exact recovery is discussed separately: in the noiseless case with exact sparsity, recovery may be exact with high probability under suitable conditions.The section distinguishes this possibility from approximate recovery.Source: §7.3 · pp. 26–27
  • For a general dictionary of size N, linear programming approximately recovers s-sparse or effectively s-sparse vectors from m ∼ s log N random linear observations.The result also allows dictionaries that are linearly dependent.Source: §7.2.1 · p. 24, §7.3 · p. 27

7.4. Application: linear regression with constraints.

  • Constrained linear regression applies the framework by minimizing a feasible-set norm subject to an ℓ1 residual bound.The regression setup treats the design matrix and response as known, while the coefficient vector and noise are unknown.Source: §7.4 · pp. 27–28

8. Extensions from Gaussian to sub-gaussian distributions

This section extends the tutorial's Gaussian measurement results to sub-gaussian observations. Under mean-zero, isotropic, bounded-norm assumptions, it gives a sub-gaussian M∗ bound and applies it to constrained estimation.

8. Extensions from Gaussian to sub-gaussian distributions

  • The section extends the M∗ bound from Gaussian to general sub-gaussian distributions and then uses it to generalize estimation results.The extension modifies the proof of the M∗ bound and transfers its consequences to estimation.Source: §8 · p. 28, §8.2 · p. 29, §8.3 · p. 31

8.1. Sub-gaussian random variables and random vectors.

  • A random vector is sub-gaussian when all its one-dimensional marginals are sub-gaussian, and isotropy means E XX^T = I_n.The text identifies standard Gaussian and uniform-on-the-discrete-cube vectors as isotropic and sub-gaussian examples.Source: §8.1 · pp. 28–29

8.2. M∗bound for sub-gaussian distributions.

  • The general M∗ bound assumes i.i.d., mean-zero, isotropic sub-gaussian rows with sub-gaussian norm at most ψ.The proof adapts Gaussian steps and uses Fernique–Talagrand comparison for the sub-gaussian process.Source: §8.2 · p. 29

8.3. Estimation from sub-gaussian linear observations.

  • For sub-gaussian linear observations, any feasible estimate satisfying the residual bound inherits the estimation guarantee, and the text says other earlier results generalize similarly.The proof uses the sub-gaussian M∗ bound in place of the Gaussian one.Source: §8.3 · pp. 31–32

9. Exact recovery

Exact recovery is characterized geometrically by whether the measurement nullspace intersects the feasible set's descent cone. Gordon's escape-through-a-mesh theorem yields sufficient observation conditions, including a sparse-recovery guarantee.

9.1. Exact recovery condition and the descent cone.

  • Exact recovery occurs when the feasible set and the measurement affine subspace intersect only at the target; locally, this is a tangency condition captured by the descent cone.The global shape of a convex feasible set is irrelevant to this local tangency condition.Source: §9.1 · pp. 32–33

9.2. Escape through a mesh, and implications for exact recovery.

  • Gordon's escape-through-a-mesh theorem gives a high-probability condition for the measurement nullspace to miss the spherical part of the descent cone.The section states that exact recovery is possible when measurements exceed the descent cone's effective dimension, without the absolute constant factors of earlier results.Source: §9.2 · pp. 34–35
  • Under the stated observation condition, minimizing the feasible-set norm subject to Ax′ = y recovers x with high probability.The theorem presents this as an exact version of the earlier estimation procedure.Source: §9.2 · p. 35

9.3. Application: exact sparse recovery.

  • For an s-sparse vector, ℓ1 minimization exactly recovers x when m > C s log n observations are used.This is the section's exact sparse-recovery application.Source: §9.3 · p. 35

10. Low-rank matrix recovery and matrix completion

The section transfers geometric recovery methods from vectors to low-rank matrices and then treats matrix completion from sampled entries. It relates observation counts to rank and matrix dimensions while stating separate assumptions for the two settings.

10.2. Low-rank matrix recovery.

  • The nuclear norm plays the role of the vector ℓ1 norm, and its unit ball's mean width supports the low-rank recovery bound.The proof follows the sparse-recovery argument, with the mean-width calculation using a bound on Gaussian matrix operator norms.Source: §10.1 · p. 36, §10.2 · p. 37
  • With Gaussian linear measurements, convex programming approximately recovers a rank-r matrix from m ∼ r(d1 + d2) random observations.The section states the initial low-rank recovery theorem in a noise-free setting and extends the result to effective rank, noise, and sub-gaussian measurements.Source: §10.2 · p. 37, §10.3.2 · p. 39, §10.3.1 · p. 39

10.3.1. From exact to effective low rank.

  • Effective rank can replace algebraic rank in the recovery result and is robust to small perturbations.The text states that effective rank is bounded by algebraic rank.Source: §10.3.1 · p. 39

10.4. Matrix completion.

  • The matrix-completion setting requires a separate argument because entry sampling is not Gaussian or sub-gaussian in the needed sense.The exposition uses a direct argument and notes that noisy sampling can also be treated when entrywise noise is independent, mean zero, and bounded.Source: §10.4 · pp. 39, 42
  • For matrix completion, the estimate is the best rank-r approximation of the rescaled sampled-entry matrix, and the average error per entry can be made arbitrarily smaller than the matrix's largest entry with m ∼ r(d1 + d2) sampled entries.The sampling setup uses independently selected entries and imposes restrictions intended to ensure representation from every row and column with high probability.Source: §10.4 · p. 40

11. Single-bit observations via hyperplane tessellations

The section recasts single-bit observations as random hyperplane orientations and uses the resulting tessellation to estimate a feasible vector. A bound on cell diameters yields recovery guarantees, with the caveat that single-bit data lose the vector’s magnitude.

11. Single-bit observations via hyperplane tessellations.

  • The section develops this framework for sign observations as an example of estimation with nonlinear observations, then points to a broader treatment of nonlinearities.The later extension is identified as applying to general nonlinearities.Source: §11 · p. 42

11.1. Single-bit observations.

  • Each single-bit observation yi = sign⟨ai, x⟩ records the orientation of x relative to a Gaussian hyperplane, retaining one bit from each linear measurement.The section treats this as an extreme quantization of y = Ax.Source: §11.1 · pp. 42–43

11.2. Hyperplane tessellations.

  • The hyperplanes partition Rn into cells of points with identical orientations, so observing y identifies the cell containing x.Figure 9 highlights the cell containing x.Source: §11.2 · p. 43, Figure 9 · p. 43
  • The estimator uses both known facts about x—membership in K and in the observed cell—and chooses any vector in their intersection.The maximum error is bounded by the diameter of that intersection.Source: §11.2 · p. 43, §11.3 · p. 44

11.3. M∗bound for random tessellations.

  • The M∗bound for random tessellations controls the largest diameter of K intersected with any cell formed by independent uniformly drawn hyperplanes.A high-probability version requires m ≥ Cδ^-6w(K)^2 for a maximum diameter at most δ, with probability at least 1 − 2 exp(−cδ^2m).Source: §11.3 · p. 44, §11.4 · p. 44

11.4. Estimation based on M∗bound for random tessellations.

  • For x on the unit sphere, any feasible vector in the observed tessellation cell estimates its direction, and m ∼ w(K)^2 observations suffice for the stated guarantee.The feasibility program is nonconvex; on the sphere it cannot be convexified, though lifting the sphere restriction is one proposed workaround.Source: §11.4 · pp. 44–45

12. Single-bit observations via optimization, and applications to logistic regression

The section replaces single-bit feasibility with an optimization program that fits linear predictions to observed bits over a feasible set. It then extends the approach to general link functions and constrained logistic regression, without requiring the link to be known.

12. Single-bit observations via optimization, and applications to logistic regression

  • The optimization program maximizes correlation between linear predictions and the single-bit observations while searching over K, and is convex when K is convex.Theorem 12.1 provides an estimation guarantee when the unknown vector has unit norm and lies in K within the unit ball.Source: §12 · p. 45

12.1. Single-bit observations with general non-linearities.

  • The same optimization program applies to general single-bit nonlinearities, including links that need not be continuous or one-to-one.The link’s information parameter must be nonzero for estimation; when it is zero, the nonlinear and linear measurements are uncorrelated and estimation is often impossible.Source: §12.1 · pp. 47–48

12.2. Logistic regression, and beyond.

  • For θ(z) = tanh(z/2), the model is constrained logistic regression, and the estimator does not need to know the link function.The same estimator is used for the tanh link and (virtually) any other nonlinearity.Source: §12.2 · pp. 48–49

13. General non-linear observations via metric projection

The section estimates from general nonlinear observations by first forming a linear estimate and then projecting it onto the feasible set. Under the stated cone setting, the error is controlled by local mean width; examples include noisy linear data, sparse vectors, and low-rank matrices.

13. General non-linear observations via metric projection

  • The general procedure forms a linear estimate and metrically projects it onto K, without specifying the observation’s nonlinearity.The section summarizes estimation from m ∼ w(K)^2 random nonlinear observations, with convex programming available when K is convex.Source: §13 · pp. 49–50
  • For a closed cone K, the two-step estimator has mean λx̄ and expected deviation at most Mw1(K)/√m.Here x̄ is the normalized unknown vector; λ and M determine the estimator’s magnitude and deviation.Source: §13 · p. 50

13.1. Examples of observations.

  • With independent zero-mean noise of variance σ^2 in linear observations, the expected error is bounded by Cw1(K)(∥x∥2 + σ)/√m.The error bound is obtained by applying Theorem 13.1.Source: §13.1 · p. 50

13.2. Examples of feasible cones.

  • For s-sparse vectors, estimation uses m ∼ s log n nonlinear observations and hard-thresholds the linear estimate to its s largest coefficients.The thresholding sets all other coefficients to zero.Source: §13.2 · p. 51
  • For rank-r matrices, estimation uses m ∼ r(d1+d2) nonlinear observations and keeps the leading singular values of the linear estimate.The projection is the best rank-r approximation.Source: §13.2 · p. 51

14. Some extensions

The extensions replace global mean width with a radius-dependent local mean width and discuss settings beyond isotropic Gaussian observations. General feasible sets under random Fourier measurements remain an open case in the account presented here.

14.1. From global to local mean width.

  • Local mean width depends on radius and can replace usual mean width in many survey results, strengthening them through localization.For high-dimensional sections it describes diameter, and related work connects a local-width variant to optimal metric-projection error rates.Source: §14 · p. 52, §14.1 · p. 52

14.2. More general distributions.

  • The survey’s Gaussian estimation results are stated for isotropic vectors for simplicity, while extensions are reported for sub-Gaussian and some anisotropic Gaussian settings.For extremely heavy-tailed measurements, the cited results cover only special feasible sets such as sparse vectors.Source: §14.2 · p. 53
  • The account reports no results for reconstructing a general feasible-set vector from random Fourier measurements, and says the required incoherence has yet to be quantified.For sparse vectors, compressed-sensing results quantify incoherence through the restricted isometry property.Source: §14.2 · p. 53

Related papers

Loading 1405.5103v2…