High-Dimensional Centrally Symmetric Polytopes with Neighborliness Proportional to Dimension

By David L. Donoho. Discrete & Computational Geometry, 2006

410 citations recorded by the source corpus.

Subfields: Applied Mathematics, Computational Mechanics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/c80203f0dd27dd5c15726543b01f4c919529d4a8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Mechanics

In Discrete Mathematics and Combinatorics

Citations in the corpus

Analysis versus synthesis in signal priors (2006, result): “In contrast, Donoho has recently presented opposite results [9] for MAP-Synthesis polytopes; as it turns out, for these polytopes the probability of any 2 (non-antipodal) vertices to be neighbors approaches 1 as N → ∞.”
Hypothesis Testing in High-Dimensional Regression Under the Gaussian Random Design Model: Asymptotic Theory (2013, methodology): “This was fruitfully studied in the context of standard linear regression [HKZ11], as well as sparse recovery.”
Living on the edge: phase transitions in convex programs with random data (2013, background): “Donoho [29] analyzed the performance of the convex program (1.”
Compressed Synthetic Aperture Radar (2010, methodology): “This method, however, suffers from the smearing of the image in the cross-range dimension due to the randomness of the PRI.”
Sparse Subspace Clustering: Algorithm, Theory, and Applications (2012, background): “ recovers subspace-sparse representations of data points in independent subspaces. Remark 2: The condition in (22) is closely related to the nullspace property in the sparse recovery literature [36], [48], [49], [50]. The key difference, however, is that we only require the inequality in (22) to hol”
$L_{1/2}$ Regularization: A Thresholding Representation Theory and a Fast Solver (2012, neutral): “(Such a solution is called a point of L1/L0 equivalence in [10], [11].”
Random Projections of Smooth Manifolds (2009, background): “Various other geometric arguments surrounding CS have also been made involving n-widths of lp balls and the properties of randomly projected polytopes [11, 12, 17–21, 25, 35, 38].”
Fast Solution of $\ell _{1}$ -Norm Minimization Problems When the Solution May Be Sparse (2008, background): “In a series of papers [15], [13], [17], Donoho has shown that for problem instances from the suite , the equivalence between solutions of and exhibits a clear phase transition, denoted , that can be computed numerically.”
Bayesian Compressive Sensing Via Belief Propagation (2008, methodology): “Indeed, in a previous paper [39], we used an LDPC-like sparse for the special case of noiseless measurement of strictly sparse signals; similar matrices were also proposed for CS by Berinde and Indyk [40].”
The Convex Geometry of Linear Inverse Problems (2010, result): “For sparse vectors, previous results obtaining 2s log(p/s) were asymptotic [26, 30, 74].”
Secure and Robust Iris Recognition Using Random Projections and Sparse Representations (2011, methodology): “At each point on the grid, we recorded the mean number of coordinates at which original and reconstruction differed by more than 10 (3), averaged over 20 independent realizations (see [42], [43] for more details).”
Iteratively reweighted least squares minimization for sparse recovery (2008, background): “| Moreover, x is unique if and only if we have strict inequality in (2.1) for all η ∈ N which are not identically zero.”
Combining geometry and combinatorics: A unified approach to sparse signal recovery (2008, methodology): “This line is equivalent to a phase transition in the ability of LP decoding to ﬁnd the sparsest solution to Gx ∗ = Gx , and, in eﬀect, is representative of the performance of Gaussian matrices in this framework (see [Don06b] and [DT06] Proof.”