Abstract
Let A be an n×N real-valued matrix with n<N; we count the number of k-faces f k (AQ) when Q is either the standard N-dimensional hypercube I N or else the positive orthant ℝ N+ . To state results simply, consider a proportional-growth asymptotic, where for fixed δ,ρ in (0,1), we have a sequence of matrices \(A_{n,N_{n}}\) and of integers k n with n/N n →δ and k n /n→ρ as n→∞. If each matrix \(A_{n,N_{n}}\) has its columns in general position, then f k (AI N)/f k (I N) tends to zero or one depending on whether ρ>min (0,2−δ −1) or ρ<min (0,2−δ −1). Also, if each \(A_{n,N_{n}}\) is a random draw from a distribution which is invariant under right multiplication by signed permutations, then f k (Aℝ N+ )/f k (ℝ N+ ) tends almost surely to zero or one depending on whether ρ>min (0,2−δ −1) or ρ<min (0,2−δ −1). We make a variety of contrasts to related work on projections of the simplex and/or cross-polytope.
These geometric face-counting results have implications for signal processing, information theory, inverse problems, and optimization. Indeed, face counting is related to conditions for uniqueness of solutions of underdetermined systems of linear equations. Below, let A be a fixed n×N matrix, n<N, with columns in general position.
-
(a)
Call a vector in ℝ N+ k -sparse if it has at most k nonzeros. For such a k-sparse vector x 0, b=Ax 0 generates an underdetermined system b=Ax having k-sparse solution. Among inequality-constrained systems Ax=b, x≥0, having k-sparse solutions, the fraction having a unique nonnegative solution is f k (Aℝ N+ )/f k (ℝ N+ ).
-
(b)
Call a vector in the hypercube I N k-simple if all entries except at most k are at the bounds 0 or 1. For such a k-simple vector x 0, b=Ax 0 generates an underdetermined system b=Ax with k-simple solution. Among inequality-constrained systems Ax=b, x∈I N, having k-simple solutions, the fraction having a unique hypercube-constrained solution is f k (AI N)/f k (I N).
Article PDF
Similar content being viewed by others
References
Adamczak, R., Litvak, A.E., Pajor, A., Tomczak-Jaegermann, N.: Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling. arXiv:0904.4723v1 (2009)
Affentranger, F., Schneider, R.: Random projections of regular simplices. Discrete Comput. Geom. 7(3), 219–226 (1992)
Baryshnikov, Y.M.: Gaussian samplesm, regular simplices, and exchangeability. Discrete Comput. Geom. 17(3), 257–261 (1997)
Björner, A., Las Vergns, M., Sturmfels, B., White, N., Ziegler, G.: Oriented Matroids. Encyclopedia of Mathematics and Its Applications, vol. 46. Cambridge University Press, Cambridge (1999)
Bolker, E.D.: A class of convex bodies. Trans. Am. Math. Soc. 145, 323–345 (1969)
Böröczky, K., Jr., Henk, M.: Random projections of regular polytopes. Arch. Math. (Basel) 73(6), 465–473 (1999)
Bruckstein, A.M., Elad, M., Zibulevsky, M.: On the uniqueness of non-negative sparse and redundant representations. In: ICASSP 2008. Special session on Compressed Sensing, Las Vegas, Nevada (2008)
Buchta, C.: On nonnegative solutions of random systems of linear inequalities. Discrete Comput. Geom. 2(1), 85–95 (1987)
Cover, T.M.: Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE Trans. Electron. Comput. EC-14(3), 326–334 (1965)
Donoho, D.L.: High-dimensional centrally-symmetric polytopes with neighborliness proportional to dimension. Discrete Comput. Geom. 35(4), 617–652 (2006)
Donoho, D.L.: Neighborly polytopes and sparse solutions of underdetermined linear equations. Technical Report, Stanford University (2006)
Donoho, D.L., Tanner, J.: Neighborliness of randomly-projected simplices in high dimensions. Proc. Natl. Acad. Sci. USA 102(27), 9452–9457 (2005)
Donoho, D.L., Tanner, J.: Sparse nonnegative solutions of underdetermined linear equations by linear programming. Proc. Natl. Acad. Sci. USA 102(27), 9446–9451 (2005)
Donoho, D.L., Tanner, J.: Exponential bounds implying construction of neighborly polytopes, error-correcting codes and compressed sensing matrices by random sampling. Preprint (2007)
Donoho, D.L., Tanner, J.: Counting the faces of randomly-projected hypercubes and orthants, with applications. arXiv:0807.3590v1 (2008)
Donoho, D.L., Tanner, J.: Counting faces of randomly-projected polytopes when the projection radically lowers dimension. J. AMS 22(1), 1–53 (2009)
Donoho, D.L., Tanner, J.: Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing. Philos. Trans. A (2009)
Donoho, D.L., Johnstone, I.M., Hoch, J.C., Stern, A.S.: Maximum entropy and the nearly black object. J. R. Stat. Soc., Ser. B (Methodological) 54(1), 41–81 (1992)
Fuchs, J.-J.: On sparse representations in arbitrary redundant bases. IEEE Trans. Inf. Theory 50(6), 1341–1344 (2004)
Goodey, P., Weil, W.: Zonoids and generalisations. In: Handbook of Convex Geometry, vols. A, B, pp. 1297–1326. North-Holland, Amsterdam (1993)
Grünbaum, B.: Convex Polytopes, 2nd edn. Graduate Texts in Mathematics, vol. 221. Springer, New York (2003). Prepared and with a preface by Volker Kaibel, Victor Klee, and Günter M. Ziegler
Schläfli, L.: In: Gesammelte Mathematische Abhandlungen, vol. 1, pp. 209–212. Birkhäuser, Basel (1950)
Schneider, R., Weil, W.: Zonoids and related topics. In: Convexity and Its Applications, pp. 296–317. Birkhäuser, Basel (1983)
Schneider, R., Weil, W.: Stochastic and Integral Geometry. Springer, Berlin (2008)
Vershik, A.M., Sporyshev, P.V.: Asymptotic behavior of the number of faces of random polyhedra and the neighborliness problem. Sel. Math. Sov. 11(2), 181–201 (1992)
Wendel, J.G.: A problem in geometric probability. Math. Scand. 11, 109–111 (1962)
Winder, R.O.: Partitions of n-space by hyperplanes. SIAM J. Appl. Math. 14(4), 811–818 (1966)
Ziegler, G.M.: Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, New York (1995)
Zong, C.: What is known about unit cubes. Bull. AMS 42(2), 181–211 (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
The authors would like to thank the Isaac Newton Mathematical Institute at Cambridge University for hosting the programme “Statistical Challenges of High Dimensional Data” in 2008 and Professor D.M. Titterington for organizing this programme.
D.L. Donoho acknowledges support from NSF DMS 05-05303 and a Rothschild Visiting Professorship at the University of Cambridge.
J. Tanner acknowledges support from the Alfred P. Sloan Foundation and thanks John E. and Marva M. Warnock for their generous support in the form of an endowed chair.
Rights and permissions
About this article
Cite this article
Donoho, D.L., Tanner, J. Counting the Faces of Randomly-Projected Hypercubes and Orthants, with Applications. Discrete Comput Geom 43, 522–541 (2010). https://doi.org/10.1007/s00454-009-9221-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-009-9221-z