Counting faces of randomly-projected polytopes when the projection radically lowers dimension
ArXiv.orgPublished 15 July 2006Open access
David L. Donoho, Jared Tanner
Citations8
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.
Abstract
This paper develops asymptotic methods to count faces of random high-dimensional polytopes. Beyond its intrinsic interest, our conclusions have surprising implications - in statistics, probability, information theory, and signal processing - with potential impacts in practical subjects like medical imaging and digital communications. Three such implications concern: convex hulls of Gaussian point clouds, signal recovery from random projections, and how many gross errors can be efficiently corrected from Gaussian error correcting codes.
Keywords
Computer ScienceEngineering
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 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.
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.
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.
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.
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).
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.