Discrete uncertainty principles and sparse signal processing (Q667658)

The main result provides multiplicative and additive estimates for numerical sparsity for unitary matrices. The multiplicative result states that for $U$ an $n\times n$ unitary matrix and $x\in \mathbb{C}^n\setminus\{0\}$, $\|x\|_1^2\|Ux\|_1^2\|U\|_{1\to\infty} \geq \|x\|_2^4$ and is a simple consequence of Hölder's inequality. Defining numerical sparsity as $\text{ns}(x)=\|x\|_1^2/\|x\|_2\|^2$, the multiplicative result is $\mathrm{ns}(x)\mathrm{ns}(Ux)\|U\|_{1\to\infty}\geq 1$. The additive result is not straightforward. It states that, with probability $1-e^{-\Omega (n)}$, for all $x$, $\mathrm{ns}(x)+\mathrm{ns}(Ux)\geq c(1-o(1))n$, where $U$ is drawn randomly from $U(n)$. Here $\Omega(n)\geq Cn$ where $c,C>0$ are fixed. \par This main theorem in turn follows from Theorem 8, whose proof is the technical heart of this work. It gives a bound with corresponding probabilities on the condition that for $U$ drawn uniformly from $U(n)$, $[I,U]$ satisfies a restricted isometry property (RIP). The RIP is shown to be enough to guarantee the additive numerical sparsity bound. In the case of the discrete Fourier transform $F$, the term numerical sparsity is justified by Theorem 10, which states that $\mathrm{ns}(x) \mathrm{ns}(Fx)=n$ if and only if $\|x\|_0 \|Fx\|_0=n$ where $\|\cdot\|_0$ is the number of nonzero coordinates. It is also proved (Theorem 11) that discrete Gaussians $g$, which satisfy $Fg=g$, form a family of near optimizers of the multiplicative inequality: $\mathrm{ns(g)}\mathrm{ns}(Fg)\leq (2+o(1))n$. Several applications of the main theorem are discussed, including sparse signal demixing, compressed sensing with partial Fourier operators, and fast detection of sparse signals.