Counting the Faces of Randomly-Projected Hypercubes and Orthants, with Applications |
| |
Authors: | David L Donoho Jared Tanner |
| |
Institution: | (1) School of Mathematical Sciences, University of Nottingham, Nottingham, NG7 2RD, UK;(2) School of Mathematical Sciences, Queen Mary, University of London, London, E1 4NS, UK |
| |
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 An,NnA_{n,N_{n}} and of integers k
n
with n/N
n
→δ and k
n
/n→ρ as n→∞. If each matrix An,NnA_{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 An,NnA_{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
).
|
|
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|