Counting the Faces of Randomly-Projected Hypercubes and Orthants, with Applications

Details Counting the Faces of Randomly-Projected Hypercubes and Orthants, with Applications Counting the Faces of Randomly-Projected Hypercubes and Orthants, with Applications

2008-07-23

arxiv.org/abs/0807.3590v1

Mathematics

Metric Geometry

21 pages, 3 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Counting the Faces of Randomly-Projected Hypercubes and Orthants, with Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting the Faces of Randomly-Projected Hypercubes and Orthants, with Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting the Faces of Randomly-Projected Hypercubes and Orthants, with Applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-471