Counting faces of randomly projected polytopes when the projection radically lowers dimension
Journal of the American Mathematical SocietyPublished 10 July 2008Open access
David L. Donoho, Jared Tanner
Citations462
SJR quartileQ1
SJR score7.03
SNIP4.98
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper develops asymptotic methods to count faces of random high-dimensional polytopes; a seemingly dry and unpromising pursuit that has surprising implications in statistics, probability, information theory, and signal processing with potential impacts in practical subjects like medical imaging and digital communications.
Abstract
Let Q = Q N Q = Q_N denote either the N N -dimensional cross-polytope C N C^N or the N − 1 N-1 -dimensional simplex T N − 1 T^{N-1} . Let A = A n , N A = A_{n,N} denote a random orthogonal projector A : R N ↦ b R n A: \mathbf {R}^{N} \mapsto bR^n . We compare the number of faces f k ( A Q ) f_k(AQ) of the projected polytope A Q AQ to the number of faces of f k ( Q ) f_k(Q) of the original polytope Q Q . We concentrate on the case where n n and
Keywords
MathematicsEngineering
IEEE Transactions on Information TheoryCompressed sensing
23,147 Citations2006David L. Donoho
It is shown that "most" subspaces in Ropfm are near-optimal, and that convex optimization (Basis Pursuit) is a near-optimal way to extract information derived from these near-optimal subspaces.
Compressed sensing
17,129 Citations2004David L. Donoho
IEEE Transactions on Information TheoryRobust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
15,775 Citations2006Emmanuel J. Candès, Justin Romberg +1 more
It is shown how one can reconstruct a piecewise constant object from incomplete frequency samples - provided that the number of jumps (discontinuities) obeys the condition above - by minimizing other convex functionals such as the total variation of f.
IEEE Transactions on Information TheoryDecoding by Linear Programming
7,181 Citations2005Emmanuel J. Candès, Terence Tao
F can be recovered exactly by solving a simple convex optimization problem (which one can recast as a linear program) and numerical experiments suggest that this recovery procedure works unreasonably well; f is recovered exactly even in situations where a significant fraction of the output is corrupted.
IEEE Transactions on Information TheoryNear-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
6,835 Citations2006Emmanuel J. Candès, Terence Tao
If the objects of interest are sparse in a fixed basis or compressible, then it is possible to reconstruct f to within very high accuracy from a small number of random measurements by solving a simple linear program.
Mathematics of ComputationIntroduction to Approximation Theory
2,083 Citations1969T. J. Rivlin, E. W. Cheney
IEEE Transactions on Information TheoryOn the inherent intractability of certain coding problems (Corresp.)
1,471 Citations1978Elwyn R. Berlekamp, Robert J. McEliece +1 more
The fact that the general decoding problem for linear codes and the general problem of finding the weights of a linear code are both NP-complete is shown strongly suggests, but does not rigorously imply, that no algorithm for either of these problems which runs in polynomial time exists.
Graduate texts in mathematicsLectures on Discrete Geometry
1,397 Citations2002Jiřı́ Matoušek
This book is primarily a textbook introduction to various areas of discrete geometry, in which several key results and methods are explained, in an accessible and concrete manner, in each area.
Signal ProcessingExtensions of compressed sensing
934 Citations2005Yaakov Tsaig, David L. Donoho
The results show that, when appropriately deployed in a favorable setting, the CS framework is able to save significantly over traditional sampling, and there are many useful extensions of the basic idea.
Communications on Pure and Applied MathematicsFor most large underdetermined systems of equations, the minimal 𝓁<sub>1</sub>‐norm near‐solution approximates the sparsest near‐solution
645 Citations2006David L. Donoho
It is shown that for most Φ, if the optimally sparse approximation x0,ϵ is sufficiently sparse, then the solution x1, ϵ of the 𝓁1‐minimization problem is a good approximation to x0 ,ϵ.
Proceedings of the National Academy of SciencesSparse nonnegative solution of underdetermined linear equations by linear programming
597 Citations2005David L. Donoho, Jared Tanner
It is shown that outward k-neighborliness is equivalent to the statement that, whenever y = Ax has a non negative solution with at most k nonzeros, it is the nonnegative solution to y =Ax having minimal sum.
Journal of the Royal Statistical Society Series B (Statistical Methodology)Geometric Representation of High Dimension, Low Sample Size Data
502 Citations2005Peter A. Hall, J. S. Marron +1 more
This analysis shows a tendency for the data to lie deterministically at the vertices of a regular simplex, which means all the randomness in the data appears only as a random rotation of this simplex.
Cambridge University Press eBooksAsymptotic Expansions of Integrals
422 Citations2008Isom H. Herron, M. R. Foster
Proceedings of the National Academy of SciencesNeighborliness of randomly projected simplices in high dimensions
373 Citations2005David L. Donoho, Jared Tanner
There is a "phase transition" in the ability of linear programming to find the sparsest nonnegative solution to systems of underdetermined linear equations.
Discrete & Computational GeometryHigh-Dimensional Centrally Symmetric Polytopes with Neighborliness Proportional to Dimension
370 Citations2005David L. Donoho
The face numbers of randomly projected cross polytopes in the proportional-dimensional case where d ∼ δn, where the projector A is chosen uniformly at random from the Grassmann manifold of d-dimensional orthoprojectors of Rn, are studied.
Birkhäuser Boston eBooksHigh Dimensional Probability II
255 Citations2000Evarist Giné, David M. Mason +1 more
Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements
230 Citations2006Mark Rudelson, Roman Vershynin
The first guarantees for universal measurements (i.e. which work for all sparse functions) with reasonable constants are proved, based on the technique of geometric functional analysis and probability in Banach spaces.
International Mathematics Research Notices
170 Citations2005Mark Rudelson, Roman Vershynin
An approach to error-correcting codes from the viewpoint of geometric functional analysis (asymptotic convex geometry) is developed, which belongs to a common ground of coding theory, signal processing, combinatorial geometry, and geometricfunctional analysis.
Discrete & Computational GeometryRandom projections of regular simplices
118 Citations1992Fernando Affentranger, Rolf Schneider
Precise asymptotic formulae are obtained for the expected number ofk-faces of the orthogonal projection of a regularn-simplex inn-space onto a randomly chosen isotropic subspace of fixed dimension or codimension, as the dimensionn tends to infinity.
Archiv der MathematikRandom projections of regular polytopes
56 Citations1999K�roly B�r�czky, Martin Henk
Transactions of the American Mathematical SocietyLimit theorems for the convex hull of random points in higher dimensions
50 Citations1999Irene Hueter
Discrete & Computational GeometryHow Neighborly Can a Centrally Symmetric Polytope Be?
49 Citations2006Nathan Linial, Isabella Novik
It is shown that there exist k-neighborly centrally symmetric d-dimensional polytopes with 2(n + d) vertices, where k(d,n) = Theta(\frac{d}{1+\log ((d+n)/d)}\right).
Birkhäuser Basel eBooksHigh Dimensional Probability III
13 Citations2003J. Hoffmann-Jørgensen, Jon A. Wellner +1 more
IEEE/SP 13th Workshop on Statistical Signal Processing, 2005Signal reconstruction from noisy randomized projections with applications to wireless sensing
8 Citations2005Jarvis Haupt, Robert D. Nowak
This work extends this type of result to show that compressible signals can be accurately recovered from random projections contaminated with noise, in many cases much more accurately than is possible using an equivalent number of conventional point samples.