0
$\begingroup$

Suppose $\mathbf{A}_{k\times n}$ ($k<n$) is a matrix whose entries are generated i.i.d. from Gaussian distribution and $\mathbf{s}_{n\times 1}$ is a sparse vector with $m$ sparsity (i.e., $\|\mathbf{s}\|_0=m$). Then what is the probability that the sparse solution of $\mathbf{A}\mathbf{s}=\mathbf{b}$ can be obtained by solving the following optimization problem (as a function of $k\geq 2m$)? \begin{align} \mathbf{s}^\ast=\quad&\text{arg}\min\quad \|\mathbf{s}\|_0\\ &\text{s.t.}\quad \mathbf{A}\mathbf{s}=\mathbf{b}. \end{align} In other words, if $\mathbf{s}_t$ is the correct answer, what is the following probability for different $k$'s? \begin{align} \mathbb{P}_k[\mathbf{s}^\ast=\mathbf{s}_t]. \end{align} How about the following relaxed optimization problem? \begin{align} \mathbf{s}^\ast=\quad&\text{arg}\min\quad \|\mathbf{s}\|_1\\ &\text{s.t.}\quad \mathbf{A}\mathbf{s}=\mathbf{b}. \end{align}

$\endgroup$

1 Answer 1

1
$\begingroup$

A good starting point is "Mathematics of sparsity (and a few other things)" by E. Candes, or a book on compressed sensing such as "A Mathematical Introduction to Compressive Sensing" by Foucart and Rauhut.

Let me change the notation slightly as your choice of variable name is atypical. Let $N$ be the sample size, $d$ the dimension and $s$ the sparsity, so that $A\in R^{N\times d}$. If $x^*$ is $s$-sparse and $$ \hat x = \text{argmin}_{x\in R^d: Ax=Ax^*} \|x\|_0 $$ breaking ties uniformly at random if there are finitely many solutions, then $$ P[\hat x = x^*] = \begin{cases} 1 &\text{ if } s \le N-1,\\ \binom{d}{N}^{-1} & \text{ if } s= N <d, \\ 0 & \text{ if } s \ge N+1 \end{cases} $$ For $s\le N-1$, this follows because for any subspace $V$ of dimension $s$, the augmented subspace $W=V\oplus \text{span}(x^*)$ has dimension at most $n$ and the map $W\to R^N$ defined as $u\mapsto Au$ is injective (has nullspace $\{0\}$) with probability 1 when the dimension of $W$ is smaller or equal to $N$ (see, e.g., https://math.stackexchange.com/questions/1920302/the-lebesgue-measure-of-zero-set-of-a-polynomial-function-is-zero).

For $s\ge N+1$, when looking at any submatrix of $A$ with $N$ columns, we can find $\hat x$ with $\|\hat x\|_0=N$ such that $A\hat x = A x^*$ because a matrix of size $N\times N$ with iid $N(0,1)$ entries is invertible with probability one by the same argument as in the previous case.

For $s=N$, for each possible subspace of dimension $N$ we can find some $\hat x$ supported on this subspace such that $A\hat x = A x^*$. If when breaking ties uniformly at random we were so lucky as to have chosen the solution with the same support as $x^*$, then $\hat x=x^*$ (with probability $\binom{d}{N}^{-1}$) and otherwise $\hat x = x^*$ with probability $1-\binom{d}{N}^{-1}$.

Basis pursuit

Next you ask about L1 minimization. The sharp threshold for the success of Basis Pursuit (the linear program mentioned in the question) is sometimes referred to the Donoho-Tanner phase trasition. A reference that implies the transition is Theorem II of "Living on the edge: Phase transitions in convex programs with random data" by Amelunxen, Lotz, B. McCoy and Tropp. The case of the L1 norm is discussed at length in that paper with many references.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.