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

David L. Donoho, Jared Tanner

Research output: Contribution to journalArticlepeer-review

Abstract

Let A be an n x 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 R-+(N). To state results simply, consider a proportional-growth asymptotic, where for fixed delta, rho in (0, 1), we have a sequence of matrices A(n,Nn) and of integers k(n) with n/N-n -> delta and k(n)/(n) -> rho as n -> infinity. If each matrix A(n,Nn) has its columns in general position, then fk(AI(N))/f(k)(I-N) tends to zero or one depending on whether rho > min(0, 2 - delta(-1)) or rho < min(0, 2 - delta(-1)). Also, if each A(n,Nn) is a random draw from a distribution which is invariant under right multiplication by signed permutations, then f(k)(AR(+)(N))/f(k)(R-+(N)) tends almost surely to zero or one depending on whether sigma > min(0, 2 - delta(-1)) or rho < min(0, 2 - delta(-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 x N matrix, n < N, with columns in general position.

Original languageEnglish
Pages (from-to)522-541
Number of pages20
JournalDiscrete & computational geometry
Volume43
Issue number3
DOIs
Publication statusPublished - Apr 2010

Keywords

  • Zonotope
  • Random polytopes
  • Random cones
  • Random matrices
  • Wendel's theorem
  • Winder-Cover theorem
  • Arrangements of hyperplanes
  • Compressed sensing
  • Threshold phenomena
  • Unique solution of underdetermined systems of linear equations
  • LINEAR INEQUALITIES
  • REGULAR SIMPLICES
  • POLYTOPES
  • NEIGHBORLINESS
  • DIMENSION
  • SYSTEMS

Fingerprint

Dive into the research topics of 'Counting the Faces of Randomly-Projected Hypercubes and Orthants, with Applications'. Together they form a unique fingerprint.
  • SMALL

    Davies, M. & Tanner, J.

    EU government bodies

    1/02/0931/07/12

    Project: Research

Cite this