Source-linked AI summary
Counting the Faces of Randomly-Projected Hypercubes and Orthants, with Applications
David L. Donoho, Jared Tanner
TL;DR
The paper addresses the missing proportional-dimensional analysis of projected hypercube faces. It develops exact finite-N formulas for hypercube and orthant projections across random-projection settings, from which asymptotic results follow.
Problem
Prior work on the hypercube considered only fixed n with N tending to infinity, where the threshold phenomenon is not visible.
Method
The paper studies random projection ensembles and establishes exact finite-N face-count formulas for projected hypercubes and orthants.
Results
The exact formulas are neither asymptotic nor approximate, and the earlier asymptotic results derive from them.
Takeaways & Limitations
The geometric face-counting results connect to applications in probability theory, information theory, signal processing, inverse problems, and optimization.
Takeaways & Limitations
The results are framed for specified random ensembles, including orthoprojectors, Gaussian, symmetric i.i.d., and sign ensembles, with some reconstruction results assuming a row of ones and positivity constraints.
Abstract
from arXiv · showhide
Let $A$ be an $n$ by $N$ real valued random matrix, and $\h$ denote the $N$-dimensional hypercube. For numerous random matrix ensembles, the expected number of $k$-dimensional faces of the random $n$-dimensional zonotope $A\h$ obeys the formula $E f_k(A\h) /f_k(\h) = 1-P_{N-n,N-k}$, where $P_{N-n,N-k}$ is a fair-coin-tossing probability. The formula applies, for example, where the columns of $A$ are drawn i.i.d. from an absolutely continuous symmetric distribution. The formula exploits Wendel's Theorem\cite{We62}. Let $\po$ denote the positive orthant; the expected number of $k$-faces of the random cone$A \po$ obeys $ {\cal E} f_k(A\po) /f_k(\po) = 1 - P_{N-n,N-k}$. The formula applies to numerous matrix ensembles, including those with iid random columns from an absolutely continuous, centrally symmetric distribution. There is an asymptotically sharp threshold in the behavior of face counts of the projected hypercube; thresholds known for projecting the simplex and the cross-polytope, occur at very different locations. We briefly consider face counts of the projected orthant when $A$ does not have mean zero; these do behave similarly to those for the projected simplex. We consider non-random projectors of the orthant; the 'best possible' $A$ is the one associated with the first $n$ rows of the Fourier matrix. These geometric face-counting results have implications for signal processing, information theory, inverse problems, and optimization. Most of these flow in some way from the fact that face counting is related to conditions for uniqueness of solutions of underdetermined systems of linear equations.
1. Introduction
The paper develops exact and asymptotic face-counting results for randomly projected hypercubes and orthants, extending threshold phenomena known for other regular polytopes. These results apply across broad random-matrix ensembles and connect geometric face counts to applications involving underdetermined linear systems.
- 1.1. Random polytopes.: Random projections of polytopes can undergo abrupt face-lattice changes as dimensions vary, motivating proportional-dimensional threshold analysis.The framework keeps n proportional to N while both grow, with k/n → ρ and n/N → δ.
- 1.2. Random Zonotopes.: The projected hypercube has a sharp weak threshold: its normalized face count tends to 1 below ρW(δ; HN) and 0 above it.The threshold discontinuity is precisely identified for uniformly distributed random orthogonal projections.
- 1.3. More General Notion of Random Projection.: The same hypercube threshold holds whenever the random matrix has an orthant-symmetric, generic nullspace, covering substantially more ensembles than random orthoprojectors.Listed examples include Gaussian, symmetric i.i.d., and sign ensembles.
- 1.4. Random Cone.: The projected positive orthant has the same weak-threshold location as the hypercube under orthant-symmetric generic random subspaces.The paper also notes implications for optimization and signal processing.
- 1.5. Exact equality in the number of faces.: Below a lower strong threshold, the projected polytope retains exactly the original number of faces with overwhelming probability, but the hypercube has no nontrivial regime of this kind.For every relevant k, the projected hypercube has strictly fewer faces than the original hypercube.
- 1.6. Exact Non-Asymptotic Results.: Exact finite-dimensional identities for projected orthants and hypercubes underlie the asymptotic results and are derived using Wendel’s Theorem and symmetry.These identities are neither asymptotic nor approximate.
2. Proof of main results
The proofs reduce face survival to null-space transversality and then use Wendel’s theorem to obtain exact probabilities and asymptotic threshold behavior. The hypercube and orthant analyses are linked through shared feasible-direction cones.
- Proof strategy: The proof strategy begins with an exact non-asymptotic identity and derives threshold theorems by asymptotically analyzing Wendel probabilities.The subsequent hypercube and orthant results follow from this identity and symmetry.
- Symmetry: Under exchangeability, averaging over all k-faces can be replaced by analyzing one fixed k-face.The argument treats faces as statistically equivalent as a calculation device.
- Wendel reduction: Wendel’s theorem applies after representing null-space vectors through a basis matrix and rewriting transversality as the condition that no nonzero vector satisfies N−k homogeneous inequalities.The relevant rows lie in a common half-space exactly when the inequality condition fails.
- Asymptotics: The probability Pm,M equals the probability of at most m−1 heads in M−1 fair-coin tosses, yielding lower-tail, central, and upper-tail regimes.The proportional-dimensional cases correspond to N−n being below, near, or above (N−k)/2.
- Asymptotics: For ρ<ρW(δ; HN), PN−n,N−k tends to 0, while for ρ>ρW(δ; HN), it tends to 1; the projected hypercube shares the corresponding weak threshold and exponent.The complementary binomial symmetry supplies the upper-tail conclusion.
- Face survival: A projected face survives precisely when the matrix null space intersects the corresponding feasible-direction cone only at zero.For the orthant and hypercube, this is expressed through equivalent transversality and survival conditions.
- Hypercube–orthant connection: The hypercube and positive orthant share the relevant face-survival probability because their lower-face and orthant feasible cones coincide at corresponding relative-interior points.This identifies the hypercube calculation with the orthant result.
3. Contrasting the Hypercube with Other Polytopes
The hypercube exhibits face-count behavior unlike the simplex and cross-polytope, while the proved weak-threshold results apply universally across broad random-matrix ensembles.
- Hypercube behavior: Theorem 1.5 identifies a region where a typical random zonotope has nearly as many k-faces as its generating hypercube.When n<N/2, the zonotope has many fewer k-faces than the hypercube for every k.
- Comparison with other polytopes: The simplex and cross-polytope have weak and strong threshold curves governing near-equality and exact equality of projected and generating face counts.Below the weak curves, projected polytopes have nearly as many faces; below the strong curves, they typically have exactly as many.
- Comparison with other polytopes: For every n<N, projected zonotopes have strictly fewer k-faces than their generators, unlike simplex and cross-polytope projections.The latter can retain all k-faces for some k even when n≪N.
- Universality: The hypercube threshold results hold for any random-matrix ensemble with an orthant-symmetric and generic random null space.This is broader than the matrix-family assumptions previously required for simplex and cross-polytope threshold results.
- Universality: Empirical studies suggest that ensembles effective for the hypercube weak threshold may also work for simplex and cross-polytope thresholds.The paper presents this as a possible broader phenomenon, not as a proved result.
- Universality: The weak-threshold phenomenon may extend to some ensembles lacking an orthant-symmetric null space, but this broader scope is not proved.The statement is explicitly presented as a possibility.
4. Contrasting the Cone with the Hypercube
The low-frequency partial Fourier matrix produces face-count behavior dramatically better than random matrices, while adjoining a row of ones shifts orthant thresholds toward those of the simplex.
- 4.1. The Low-Frequency Partial Fourier Matrix.: Its face-count behavior is dramatically different from, and in some sense better than, that of the random matrices considered earlier.
- 4.1. The Low-Frequency Partial Fourier Matrix.: The low-frequency partial Fourier matrix can preserve all k-faces through k ≤ floor(n/2), matching the classical neighborliness of cyclic polytopes.The matrix is associated with the trigonometric moment curve and generates a cyclic polytope.
- 4.1. The Low-Frequency Partial Fourier Matrix.: The strong and weak face-count thresholds for projected simplices and orthants differ substantially, especially when n < N/2.The corresponding threshold curves are displayed in Figures 3.1 and 1.1.
- 4.1. The Low-Frequency Partial Fourier Matrix.: The Fourier matrix’s row of ones gives the positive orthant a distinguished role, and removing that row causes the neighborliness conclusion to fail drastically.
- 4.2. Adjoining a Row of Ones to A.: Adding a row of ones to a random zero-mean matrix causes a drastic shift in strong and weak thresholds, making projected-orthant thresholds coincide with simplex thresholds.
5. Application: Compressed Sensing
The paper reinterprets projected-face survival as uniqueness of constrained solutions to underdetermined linear systems. This yields recovery guarantees for sparse nonnegative vectors and simple box-constrained vectors.
- 5. Application: Compressed Sensing: Face-counting results become statements about when constrained solutions of underdetermined systems are unique.The systems have n < N, so constraints can restore uniqueness despite underdetermination.
- 5.1. Reconstruction Exploiting Positivity Constraints.: Nonnegativity constraints can uniquely recover k-sparse vectors, even when the measurement system is underdetermined.For covered random matrix ensembles, the probability is 1 − P_{N−n,N−k}.
- 5.1. Reconstruction Exploiting Positivity Constraints.: Below the orthant weak threshold, positivity-constrained variational methods recover the vast majority of k-sparse vectors; below the strong threshold, they recover every such vector for sufficiently large n.
- 5.1. Reconstruction Exploiting Positivity Constraints.: The low-frequency partial Fourier matrix recovers every floor(n/2)-sparse vector using any variational method imposing positivity constraints.The augmented matrix with a row of ones is also better than a random zero-mean matrix.
- 5.2. Reconstruction Exploiting Box Constraints.: Box constraints similarly recover k-simple vectors, with weak-threshold guarantees covering at least a fraction (1 − ε) of underdetermined instances.A k-simple vector has all entries at 0 or 1 except at k exceptional locations.
- 5.2. Reconstruction Exploiting Box Constraints.: The weak hypercube threshold is the best known general result for undersampling box-constrained objects, but typical objects should not be undersampled by more than a factor of 2.The paper contrasts this with severe undersampling of very sparse nonnegative objects.
6. Additional Proofs
The proofs establish equivalences between face survival and constrained uniqueness, then analyze Fourier nullspaces and face correspondences to derive the projected-orthant results.
- 5.1. Proofs for Positive Constraints.: For the positive orthant, a projected k-face is equivalent to uniqueness of the associated solution to Ax = b within the orthant.
- 5.1. Proofs for Positive Constraints.: The proof uses feasibility directions and the nullspace: a nonzero feasible nullspace vector would produce a second solution, contradicting uniqueness.
- 5.2. Proofs for Box Constraints.: For the hypercube, face survival is likewise equivalent to uniqueness within the box, with feasibility signs determined by coordinates at lower and upper bounds.
- 5.2. Proofs for Box Constraints.: Orthant symmetry makes the relevant sign event independent of how coordinates are split between positive and negative feasibility directions.
- 6. Additional Proofs: For the partial Fourier matrix, the range is the lowpass sequence space and its nullspace is the highpass sequence space.When n = 2m + 1, every highpass sequence has at least m negative entries.
- 6. Additional Proofs: If m > k, highpass nullspace vectors cannot satisfy the feasibility pattern of a k-sparse orthant face, establishing the required transversality.
- 6. Additional Proofs: A natural bijection links k-faces of the positive orthant with (k−1)-faces of the simplex, allowing corresponding face-survival events to be compared.