---
abstract: 'Compressed sensing seeks to recover a sparse vector from a small number of linear and non-adaptive measurements. While most work so far focuses on Gaussian or Bernoulli random measurements we investigate the use of partial random circulant and Toeplitz matrices in connection with recovery by $\ell_1$-minization. In contrast to recent work in this direction we allow the use of an arbitrary subset of rows of a circulant and Toeplitz matrix. Our recovery result predicts that the necessary number of measurements to ensure sparse reconstruction by $\ell_1$-minimization with random partial circulant or Toeplitz matrices scales linearly in the sparsity up to a $\log$-factor in the ambient dimension. This represents a significant improvement over previous recovery results for such matrices. As a main tool for the proofs we use a new version of the non-commutative Khintchine inequality.'
author:
- 
title: Circulant and Toeplitz Matrices in Compressed Sensing
---

Introduction
============

Compressed sensing is a recent concept in signal processing where one seeks to reconstruct efficiently a sparse signal from a minimal number of linear and non-adaptive measurements [@do06-2]. So far various measurement matrices have been investigated, most of them random matrices. Among these are Bernoulli and Gaussian matrices [@badadewa06] (with independent $\pm 1$ or standard normal entries) as well as partial Fourier matrices [@cata06; @ra08-1; @ru06-1]. Recently, Bajwa et al. [@bahanorawr07] (see also [@ro08]) studied Toeplitz type and circulant matrices in the context of compressed sensing where the entries of the vector generating the Toeplitz or circulant matrix are chosen at random according to a suitable probability distribution. Compared to Bernoulli or Gaussian matrices random Toepliz and circulant matrices have the advantage that they require a reduced number of random numbers to be generated. More importantly, there are fast matrix-vector multiplication routines which can be exploited in recovery algorithms. Furthermore, they arise naturally in certain applications such as identifying a linear time-invariant system [@bahanora08].

Basis Pursuit ($\ell_1$-minimization) is one of the major approaches to efficiently recover a sparse vector. This technique is quite well understood by now. Modern optimization algorithms [@bova04] such as LARS [@efhajoti04] (sometimes called homotopy method) are reasonably fast.

Bajwa et al. [@bahanorawr07; @bahanora08] estimated the so-called restricted isometry constants of a random Toeplitz type or circulant matrix which then allows to provide recovery guarantees for $\ell_1$-minimization. However, their bound is very pessimistic compared to related estimates for Bernoulli / Gaussian or partial Fourier matrices. More precisely, the estimated number of measurements grows with the sparsity squared, while one would rather expect a linear scaling. Indeed, this is also suggested by numerical experiments. We close the theoretical gap by providing recovery guarantees for $\ell_1$-minimization in connection with circulant and Toeplitz type matrices where the necessary number of measurements scales linearly with the sparsity. However, we do not make use of the restricted isometry constants and a good estimate of the latter is therefore still open.

Sparse recovery with circulant and Toeplitz matrices
====================================================

For a vector $x\in {{\mathbb{R}}}^N$ we let ${\operatorname{supp}}x = \{j, x_j \neq 0 \}$ denote its support and $\|x\|_0 = |{\operatorname{supp}}x|$ the number of non-zero entries. It is called ${s}$-sparse if $\|x\|_0 \leq {s}$. We aim at recovering $x$ from $y= Ax \in {{\mathbb{R}}}^n$ where $A$ is a suitable $n \times N$ measurement matrix and $n < N$. A natural strategy is to consider $\ell_0$-minimization, $$\label{l0}
\min_x \|x\|_0 \quad \mbox{ subject to } Ax = y. $$ Unfortunately this combinatorial optimization problem is NP hard in general [@avdama97]. Therefore, we solve instead the convex problem $$\label{l1}
\min \|x\|_1 \quad \mbox{ subject to } Ax=y,$$ where the $\ell_p$-norm is defined as usual, $\|x\|_p= (\sum_{j=1}^N |x_j|^p)^{1/p}$. It is by now well understood that the solutions of both minimization problems often coincide and are equal to the original vector $x$, see e.g.  [@carota06; @dota06; @do06-2; @grni03; @ra07]. A by now popular result [@carota06; @ca08; @folaXX] states that indeed (stably) recovers all ${s}$-sparse $x$ from $y = Ax$ provided the restricted isometry constant $\delta_{2{s}} \leq \delta < \sqrt{2}-1$. The latter means that $$(1-\delta) \|x\|_2^2 \leq \|Ax\|_2^2 \leq (1+\delta) \|x\|_2^2$$ for all $2{s}$-sparse vectors $x$. It is known [@badadewa06] that random Gaussian or Bernoulli matrices, i.e. $n\times N$ matrices with independent and normal distributed or Bernoulli distributed entries, satisfy this condition with probability at least $1-\epsilon$ provided ${s}\leq C_1 n \log(N/{s})  + C_2 \log(\epsilon^{-1})$.

We consider the following types of measurement matrices. For $b = (b_0,b_1, \hdots,b_{N-1}) \in {{\mathbb{R}}}^N$ we let its associated circulant matrix $S = S^b \in {{\mathbb{R}}}^{N\times N}$ with entries $S_{i,j} = b_{j-i \mod N}$, where $i,j =1,\hdots,N$. Similarly, for a vector $c = (c_{-N+1},c_{-N+2},\hdots,c_{N-1})$ its associated Toeplitz matrix $T = T ^c \in {{\mathbb{R}}}^{N \times N}$ has entries $T_{i,j} = c_{j-i}$, where $i,j =1,\hdots,N$. Now we choose an arbitrary subset $\Omega \subset \{1,\hdots,N\}$ of cardinality $n<N$ and let the partial circulant matrix $S_\Omega = S_\Omega^b \in {{\mathbb{R}}}^{n \times N}$ be the submatrix of $S$ consisting of the rows indexed by $\Omega$. The partial Toeplitz matrix $T_\Omega=T_\Omega^c \in {{\mathbb{R}}}^{n \times N}$ is defined similarly. In this paper the vectors $b$ and $c$ will always be random vectors with independent Bernoulli $\pm 1$ entries.

Of particular interest is the case $N = n K$ for some $K \in {{\mathbb{N}}}$ and $\Omega = \{ K, 2K, \hdots, nK\}$. Then the application of $S_\Omega^b$ and $T_\Omega^c$ corresponds to (periodic or non-periodic) convolution with the sequence $b$ (or $c$, respectively) followed by a downsampling by a factor of $K$. This setting was studied numerically in [@babadutrwa06] by Tropp et al. (using orthogonal matching pursuit instead of $\ell_1$-minimization). Also of interest is the case $\Omega = \{1,2,\hdots,n\}$ which was investigated in [@bahanorawr07; @bahanora08] by Bajwa et al., who showed that the restricted isometry constant of $T_\Omega^c$ satisfies $\delta_{{s}} \leq \delta$ with high probability (w.h.p.) provided $n \geq C_\delta {s}^2 \log(N/{s})$. As a byproduct of the proof of our main result we give an alternative proof that $\delta_{s}\leq \delta$ holds w.h.p. under the condition $n \geq C \delta^{-2} {s}^2 \log^2(N)$. However, we strongly believe that this bound is not optimal due to the quite pessimistic quadratic scaling in ${s}$. Our main result shows that one can achieve recovery w.h.p. by $\ell_1$-minimization, if $n \geq C {s}\log^2(N)$.

In the following recovery theorem we use a random partial circulant or Toeplitz matrix $A^b_\Omega$ or $T^c_\Omega$ in the sense that the entries of the vector $b$ or $c$ are independent Bernoulli $\pm 1$ random variables. Furthermore, the signs of the non-zero entries of the ${s}$-sparse vector $x$ are chosen at random according to a Bernoulli distribution as well. In contrast to previous work [@bahanorawr07; @babadutrwa06] $\Omega$ is allowed to be an arbitrary subset of $\{1,\hdots,N\}$ of cardinality $n$.

\[thm:main\] Let $\Omega \subset \{1,2,\hdots,N\}$ be an arbitrary (deterministic) set of cardinality $n$. Let $x\in{{\mathbb{R}}}^N$ be ${s}$-sparse such that the signs of its non-zero entries are Bernoulli $\pm 1$ random variables. Choose $b \in {{\mathbb{R}}}^N$ to be a random vector whose entries are $\pm 1$ Bernoulli variables. Let $y = S^b_\Omega x \in {{\mathbb{R}}}^n$. There exists a constant $C > 0$ such that $$n \geq C {s}\log^3(N/\epsilon)$$ implies that with probability at least $1-\epsilon$ the solution of the $\ell_1$-minimization problem coincides with $x$.

The same statement holds with $T^c_\Omega$ in place of $S^b_\Omega$ where $c \in {{\mathbb{R}}}^{2N-1}$ is a random vector with Bernoulli $\pm 1$ entries.

Ignoring the $\log$-factor the necessary number of samples ensuring recovery by $\ell_1$-minimization scales linearly with the sparsity ${s}$. The power $3$ at the $\log$-term can very likely be improved to $1$, and moreover, it seems also possible to remove the randomness assumption on the non-zero coefficients of $x$. We postpone such improvements as well as an investigation of the restricted isometry constants to possible future contributions. The remainder of the paper is concerned with the proof of Theorem \[thm:main\].

Proof of Theorem \[thm:main\]
=============================

An essential ingredient of the proof is the following recovery theorem for $\ell_1$-minimization due to Fuchs [@fu04] and Tropp [@tr05-1]. For a matrix $A$ we denote by $a_\rho$ its columns and by $A_\Lambda$ the submatrix consisting only of the columns index by $\Lambda$.

\[thm:Tropp\] Suppose that $y = A x$ for some $x$ with ${\operatorname{supp}}x = \Lambda$. If $$\label{recovery:cond}
|\langle A_\Lambda^\dagger {{a}}_\rho,  {\operatorname{sgn}}(x_\Lambda) \rangle | < 1 \quad \mbox{ for all } \rho \notin \Lambda\,,$$ then $x$ is the unique solution of the Basis Pursuit problem (\[l1\]). Here, $A_\Lambda^\dagger$ denotes the Moore-Penrose pseudo-inverse of $A_\Lambda$.

A crucial step in applying this theorem is to show that the $\ell_2$-norm of ${{A}}_\Lambda^\dagger {{a}}_\rho$ in is small. To this end one expands $$\label{PseudoInvEst}
\|{{A}}_\Lambda^\dagger {{a}}_\rho\|_2 \,=\, \|({{A}}_\Lambda^* {{A}}_\Lambda)^{-1} {{A}}_\Lambda^* {{a}}_\rho\|_2 \,=\, \|({{A}}_\Lambda^* {{A}}_\Lambda)^{-1}\|_{2\to 2} \|{{A}}_\Lambda^* {{a}}_\rho\|_2,$$ where $\|\cdot\|_{2\to2}$ denotes the operator norm on $\ell_2$. The second term can be estimated in terms of the coherence of ${{A}}$, which is defined to be the largest absolute inner product of different columns of ${{A}}$, $\mu = \max_{\rho \neq \lambda} |\langle {{a}}_\rho, {{a}}_\lambda \rangle|$. Indeed, $$\|{{A}}_\Lambda^* {{a}}_\lambda\|_2 =
\left( \sum_{\lambda \in \Lambda} |\langle {{a}}_{\lambda}, {{a}}_\rho \rangle|^2 \right)^{1/2}
\leq \sqrt{|\Lambda|} \mu.$$ The coherence of a random Toeplitz or circulant matrix can be bounded as follows.

\[prop:coherence\] Let $\mu$ be the coherence of the random partial circulant matrix $\frac{1}{\sqrt{n}} S_\Omega^b \in {{\mathbb{R}}}^{n\times N}$ or Toeplitz matrix $\frac{1}{\sqrt{n}} T_\Omega^c \in {{\mathbb{R}}}^{n\times N}$ where $b$ and $c$ are Rademacher series and $\Omega$ has cardinality $n$. Then with probability at least $1-\epsilon$ the coherence satisfies $$\mu \leq 4 \frac{\log(2N^2/\epsilon)}{\sqrt{n}}.$$

The proof is contained in Section \[sec:proof:coherence\]. This proposition easily implies the following (probably non-optimal) estimate of the restricted isometry constants of $S^b_\Omega$ or $T^c_\Omega$ contained also in [@bahanora08] with a different proof.

\[cor\_RIP\] Let $\frac{1}{\sqrt{n}} S_\Omega^b, \frac{1}{\sqrt{n}} T_\Omega^c \in {{\mathbb{R}}}^{n\times N}$ be the randomly generated normalized partial circulant and Toeplitz matrix generated from Rademacher series and $\delta_{s}$ be their restricted isometry constant. Assume that $$n \geq 16 \delta^{-2} {s}^2 \log^2(2N^2/\epsilon).$$ Then with probability at least $1-\epsilon$ it holds $\delta_{s}\leq \delta$.

Combine the bound $\delta_{s}\leq ({s}-1) \mu$ (which easily follows from Gershgorin’s disk theorem) with the estimate above on the coherence of $A = \frac{1}{\sqrt{n}} S^b_\Omega$ or $A = \frac{1}{\sqrt{n}} T^c_\Omega$.

As suggested by we also need an estimate of the operator norm of the inverse of $A_\Lambda^* A_\Lambda$. To this end we bound the smallest and largest eigenvalue of this matrix.

\[thm:condition\] Let $\Omega,\Lambda \subset \{1,\hdots,N\}$ with $|\Omega| =n$ and $|\Lambda| = {s}$. Let $b \in {{\mathbb{R}}}^N$ and $c \in {{\mathbb{R}}}^{2N-1}$ be Rademacher series. Denote either $A = \frac{1}{\sqrt{n}} S^b_\Omega$ or $A = \frac{1}{\sqrt{n}} T^c_\Omega$. Assume $$\label{cond:conditioning}
n \geq \tilde{C} \delta^{-2} {s}\log^2(4{s}/\epsilon),$$ where $\tilde{C} = 4\pi^2 \approx 39.48$. Then with probability at least $1- \epsilon$ the minimal and maximal eigenvalues $\lambda_{\min}$ and $\lambda_{\max}$ of $A_\Lambda^* A_\Lambda$ satisfy $$1-\delta \leq \lambda_{\min} \leq \lambda_{\max} \leq 1+\delta.$$

Note that the above theorem holds for a fixed subset $\Lambda$ and random coefficients $b$ or $c$. It does not imply that for given $b$ or $c$ the estimate holds uniformly for all subsets $\Lambda$, which would be equivalent to having an estimate for the restricted isometry constants of $\frac{1}{\sqrt{n}} S^b_\Omega$ or $\frac{1}{\sqrt{n}} T^c_\Omega$. (Note that taking a union bound over all subsets $\Lambda$ would yield an estimate essentially worse than Corollary \[cor\_RIP\].)

Now we are ready to complete the proof of Theorem \[thm:main\] on the basis of Proposition \[prop:coherence\] and Theorem \[thm:condition\]. We proceed similarly as in [@tr06-2 Theorem 14]. Hoeffding’s inequality states that $$\label{Bernstein}
{{\mathbb{P}}}\big(|\sum_{j} \epsilon_j a_j|\geq u \|a\|_2\big) \leq 2 e^{- u^2/2}.$$ By our assumption on the random phases $\epsilon_\lambda = {\operatorname{sgn}}(x_\lambda)$, the scalar product on the left hand side of (\[recovery:cond\]) is precisely of the above form with $a = A_\Lambda^\dagger a_\rho = (A_\Lambda^* A_\Lambda)^{-1} A_\Lambda^* a_\rho$. Theorem \[thm:condition\] implies that the smallest eigenvalue of $A_\Lambda^* A_\Lambda$ is bounded from below by $1-\delta$ with probability at least $1-\epsilon$ provided condition holds; hence, $\|(A_\Lambda^* A_\Lambda)^{-1}\|_{2\to 2} \leq \frac{1}{1-\delta}$. Plugging this into yields $$\label{equation:CombineEstimates1}
\|{{A}}_\Lambda^\dagger {{a}}_\rho\|_2 \leq \frac{1}{1-\delta} \sqrt{{s}} \mu.$$ Following Theorem \[thm:Tropp\] the probability that recovery fails can be estimated by $$\begin{aligned}
&{{\mathbb{P}}}\big(|\langle {{A}}_\Lambda^\dagger {{a}}_\rho, R_\Lambda {\operatorname{sgn}}(x) \rangle| \geq 1
\mbox{ for some } \rho \notin \Lambda\big)\notag\\[.2cm]
&\leq {{\mathbb{P}}}\big(\,|\langle {{A}}_\Lambda^\dagger {{a}}_\rho, R_\Lambda {\operatorname{sgn}}(x) \rangle| \geq 1
\mbox{ for some } \rho \notin \Lambda\ \big|
 \mu \leq \frac{\alpha}{\sqrt{n}} \notag\\ 
& \phantom{\leq {{\mathbb{P}}}\big( }
\mbox{\&}\, \lambda_{\min} \geq 1-\delta\,\big) + {{\mathbb{P}}}\big(\mu > \frac{\alpha}{\sqrt{n}}\big) + {{\mathbb{P}}}\big(\lambda_{\min} < 1-\delta\big) \notag\\[.2cm]
&\leq \sum_{\rho \notin \Lambda} {{\mathbb{P}}}\big(\,|\langle {{A}}_\Lambda^\dagger {{a}}_\rho, R_\Lambda {\operatorname{sgn}}(x) \rangle| \geq 1\ \big| \ \mu \leq \frac{\alpha}{\sqrt{n}} \, \mbox{\&}\, \lambda_{\min} \geq 1-\delta\,\big) \notag\\[.2cm]&\qquad+
{{\mathbb{P}}}\big(\mu > \frac{\alpha}{\sqrt{n}}\big) + {{\mathbb{P}}}\big(\lambda_{\min} < 1-\delta\big).\notag\end{aligned}$$ Under the assumption $\mu \leq \frac{\alpha}{\sqrt{n}}$ equation implies that for $u= \frac {(1-\delta)\sqrt n}{\alpha \sqrt{{s}}}$ we have $u\| A_\Lambda^\dagger a_\rho\|_2\leq 1$, so (\[Bernstein\]) gives $$\begin{aligned}
\label{equation:CombineEstimates2}
&{{\mathbb{P}}}\big(\,|\langle {{A}}_\Lambda^\dagger {{a}}_\rho, R_\Lambda {\operatorname{sgn}}(x) \rangle| \geq 1\ \big|\ \mu \leq \frac{\alpha}{\sqrt{n}}\,  \mbox{\&} \, \lambda_{\min} \geq 1-\delta\, \big)\notag\\
&\leq \ 2 \exp\left(-\frac{(1-\delta)^2}{2\alpha^2} \frac{n}{{s}}\right).\end{aligned}$$ Setting $\alpha = 4 \log(2N^2/\epsilon) 
$ Theorem \[prop:coherence\] yields $${{\mathbb{P}}}(\mu \geq \alpha/\sqrt{n}) \leq \epsilon.$$ Now we choose $\delta = 1/2$. Under condition (\[cond:conditioning\]), which reads $$\label{cond2}
n \geq 4\tilde{C} {s}\log^2({s}/\epsilon),$$ we have ${{\mathbb{P}}}(\lambda_{\min} \geq 1-\delta) \leq \epsilon$. Hence, under the above conditions we obtain $$\begin{aligned}
&{{\mathbb{P}}}\big(|\langle {{A}}_\Lambda^\dagger {{a}}_\rho, R_\Lambda {\operatorname{sgn}}(x) \rangle| \geq 1
\mbox{ for some } \rho \notin \Lambda\big) \notag\\
&\leq 2 N \exp\left(- \frac{1}{8\log^2(2N^2/\epsilon)}\frac{n}{{s}}\right) + 2\epsilon.\label{P_estimate1}\end{aligned}$$ The first term is less than $\epsilon$ provided $n \geq 8 {s}\log^2(2N^2/\epsilon)\log(2 N/\epsilon)$, or $$\label{cond1}
n \geq C_1 {s}\log^3(N/\epsilon)$$ for a suitable constant $C_1$. Conditions (\[cond2\]) and (\[cond1\]) are both satisfied if $$n \geq C {s}\log^3(N/\epsilon)$$ for a suitable constant $C$, in which case the probability that recovery by $\ell_1$-minimization is less than $3 \epsilon$. This completes the proof.

Non-commutative Khintchine inequalities
=======================================

Both the proof of Proposition \[prop:coherence\] as well as the proof of Theorem \[thm:condition\] are based on versions of the Khintchine inequality. Let us first state the non-commutative Khintchine inequality due to Lust-Piquard [@lu86-1] and Buchholz [@bu01], see also [@tr06-2]. To this end we introduce Schatten class norms on matrices. Denoting by $\sigma(A)$ the vector of singular values of a matrix $A$, the $S_p$-norm is defined as $$\|A\|_{S_p} := \|\sigma(A)\|_p,$$ where $\|\cdot\|_p$ is the usual $\ell_p$-norm, $1\leq p\leq \infty$.

\[Gauss\_Khintchine\] Let $(A_k)$ be a finite sequence of matrices of the same dimension and let $(g_k)$ be a sequence of independent standard Gaussian random variables. Then for $m \in {{\mathbb{N}}}$, $$\begin{aligned}
&\left[ {{\mathbb{E}}}\left\|\sum_k g_k A_k\right\|_{S_{2m}}^{2m} \right]^{1/2m} \notag\\
&\leq B_m \max \left\{ \left\|\left(\sum_k A_k A_k^*\right)^{1/2}\right\|_{S_{2m}}, \left\| \left(\sum_k A_k^* A_k \right)^{1/2} \right\|_{S_{2m}} \right\},\notag\end{aligned}$$ with optimal constant $$B_m = \left( \frac{(2m)!}{2^m m!}\right)^{\frac{1}{2m}}$$

Using the contraction principle for Bernoulli random variables, see [@leta91 eq. (4.8)], we obtain the non-commutative Khintchine inequality for Bernoulli random variables [@lu86-1].

\[cor\_Kh\] Let $(A_k)$ be a finite sequence of matrices of the same dimension and let $(\epsilon_k)$ be a sequence of independent Bernoulli $\pm 1$ random variables. Then for $m \in {{\mathbb{N}}}$, $$\begin{aligned}
&\left[ {{\mathbb{E}}}\left\|\sum_k \epsilon_k A_k\right\|_{S_{2m}}^{2m} \right]^{1/2m} \notag\\
&\leq C_m \max \left\{ \left\|\left(\sum_k A_k A_k^*\right)^{1/2}\right\|_{S_{2m}}, \left\| \left(\sum_k A_k^* A_k \right)^{1/2} \right\|_{S_{2m}} \right\},\label{Bernoulli_Khintch}\end{aligned}$$ with constant $$C_m = \sqrt{\frac{\pi}{2}} \left( \frac{(2m)!}{2^m m!}\right)^{\frac{1}{2m}}.$$

In the scalar case the factor $\sqrt{\pi/2}$ can be removed. However, it is not clear yet whether this is true also in the non-commutative situation.

The following theorem extends the non-commutative Khintchine inequality to a second order chaos variable. Its proof uses decoupling and Corollary \[cor\_Kh\].

\[Bernoulli\_Khintchine\] Let $A_{j,k} \in {{\mathbb{C}}}^{r \times t}$, $j,k=1,\hdots,N$, be matrices with $A_{j,j} = 0$, $j=1,\hdots,N$. Let $\epsilon_k$, $k=1, \hdots, N$ be independent Bernoulli random variables. Then for $m \in {{\mathbb{N}}}$ it holds $$\begin{aligned}
&\left[ {{\mathbb{E}}}\left\| \sum_{j,k=1}^N \epsilon_j \epsilon_k A_{j,k} \right\|_{S_{2m}}^{2m}\right]^{1/2m} \notag\\
&\leq D_m \max \left\{ \left\|\left(\sum_{j,k=1}^N A_{j,k} A_{j,k}^*\right)^{1/2}\right\|_{S_{2m}},\right.\notag\\
& \phantom{\leq D_m \max \{\{ }
\left. \left\| \left( \sum_{j,k=1}^N A_{j,k}^* A_{j,k}\right)^{1/2}\right\|_{S_{2m}}, \|F\|_{S_{2m}}\right\},   \notag\end{aligned}$$ where $F$ is the block matrix $F = (A_{j,k})_{j,k=1}^N$ and the constant $$D_m \,=\, 2^{1/2m} 2\pi C_m^2 = 2^{1/2m} 2\pi \left(\frac{(2m)!}{2^m m!}\right)^{1/m}.$$

At present it is not clear whether the term $\|F\|_{S_{2m}}$ can be omitted above. At least, there is no a priori inequality between any of the terms in the maximum. The proof of the theorem is based on the following decoupling lemma, see [@botz87 Proposition 1.9] or [@gide99 Theorem 3.1.1].

\[lem\_decouple\] Let $\xi_j$, $j=1,\hdots,N$, be a sequence of independent random variables with ${{\mathbb{E}}}\xi_j = 0$ for all $j=1,\hdots,N$. Let $A_{j,k}$, $j,k=1,\hdots,N$, be a double sequence of elements in a Banach space with norm $\|\cdot\|$, where $A_{j,j} = 0$ for all $j=1,\hdots,N$. Then for $1\leq p < \infty$ $${{\mathbb{E}}}\left\| \sum_{j,k=1}^N \xi_j \xi_k A_{j,k} \right\|^p  
\leq 4^p {{\mathbb{E}}}\left\| \sum_{j,k=1}^N \xi_j \xi'_k A_{j,k} \right\|^p,$$ where $\xi'$ denotes an independent copy of the sequence $\xi = (\xi_j)$.

[Proof of Theorem \[Bernoulli\_Khintchine\]]{}. We apply Lemma \[lem\_decouple\] followed by the non-commutative Khintchine inequality , $$\begin{aligned}
E& := {{\mathbb{E}}}\left\| \sum_{j,k=1}^N \epsilon_j \epsilon_k A_{j,k} \right\|_{S_{2m}}^{2m}\notag\\
&\leq 4^{2m} {{\mathbb{E}}}_{\epsilon} {{\mathbb{E}}}_{\epsilon'} \left\| \sum_{j,k=1}^N \epsilon_j \epsilon_k' A_{j,k} \right\|_{S_{2m}}^{2m}\notag\\
&\leq 4^{2m} C_m^{2m} {{\mathbb{E}}}_{\epsilon} \max\left\{ \left\|\left(\sum_{k=1}^N B_k(\epsilon)^* B_k(\epsilon)\right)^{1/2} \right\|_{S_{2m}}^{2m}, \right.\notag\\
&\phantom{\leq 4^{2m} C_m^{2m} } \left.
\left\| \left(\sum_{k=1}^N B_k(\epsilon) B_k(\epsilon)^*\right)^{1/2}
\right\|_{S_{2m}}^{2m} \right\},\label{MaxEst}\end{aligned}$$ where $B_k(\epsilon) \,:=\, \sum_{j=1}^N \epsilon_j A_{j,k}$. We define $$\begin{aligned}
\widehat{A}_{j,k} = \left(0|\hdots|0|A_{j,k}|0|\hdots|0\right) \in {{\mathbb{C}}}^{r \times tN}\notag\end{aligned}$$ where the non-zero block $A_{j,k}$ is the $k$-th one, and similarly $$\begin{aligned}
\widetilde{A}_{j,k} = \left(0|\hdots|0|A_{j,k}^*|0|\hdots|0\right)^* \in {{\mathbb{C}}}^{rN \times t}.\notag\end{aligned}$$ Then clearly $$\begin{aligned}
\widehat{A}_{j,k} \widehat{A}^*_{j',k'} = \left\{\begin{array}{cc} 0 &  \mbox{ if } k \neq k',\\
A_{j,k} A_{j',k}^* & \mbox{ if } k = k'.
\end{array} \right.,\label{wideAA}\\
\widetilde{A}_{j,k}^* \widetilde{A}_{j',k'} = \left\{\begin{array}{cc} 0 &  \mbox{ if } k \neq k',\\
A_{j,k}^* A_{j',k} & \mbox{ if } k = k'.
\end{array} \right.\notag\end{aligned}$$ The Schatten class norm satisfies $\| A \|_{S_{2m}} = \|(A A^*)^{1/2}\|_{S_{2m}}$. This allows us to verify that $$\begin{aligned}
&\left\|\sum_{j=1}^N \epsilon_j \sum_{k=1}^N \widehat{A}_{j,k} \right\|_{S_{2m}}
\,=\, \left\|\left(\sum_{j,j'} \epsilon_j \epsilon_{j'} \sum_{k,k'} \widehat{A}_{j,k} \widehat{A}_{j',k'}^*\right)^{1/2}\right\|_{S_{2m}}\notag\\
&=\, \left\|\left(\sum_{j,j'} \epsilon_j \epsilon_{j'} \sum_k A_{j,k} A_{j',k}^* \right)^{1/2} \right\|_{S_{2m}}\notag\\
&=\, \left\|\left(\sum_k B_k(\epsilon) B_k(\epsilon)^*\right)^{1/2}\right\|_{S_{2m}}.\notag\end{aligned}$$ Similarly, we also verify that $$\left\|\left(\sum_k B_k(\epsilon)^* B_k(\epsilon)\right)^{1/2}\right\|_{S_{2m}} = \left\|\sum_{j=1}^N \epsilon_j \sum_{k=1}^N \widetilde{A}_{j,k}\right\|_{S_{2m}}.$$ Plugging the above expressions into (\[MaxEst\]) we can further estimate $$\begin{aligned}
E &\leq 4^{2m} C_{2m}^{2m} \left({{\mathbb{E}}}\left\| \sum_{j=1}^N \epsilon_j \sum_{k=1}^N \widehat{A}_{j,k}\right\|_{S_{2m}}^{2m}\right.\notag\\
& \phantom{\leq 4^{2m} C_{2m}^{2m} ((}  
\left. + {{\mathbb{E}}}\left\| \sum_{j=1}^N \epsilon_j \sum_{k=1}^N \widetilde{A}_{j,k}\right\|_{S_{2m}}^{2m}\right).\notag\end{aligned}$$ Using Khintchine’s inequality once more we obtain $$\begin{aligned}
E_1\,&:= 
{{\mathbb{E}}}\left\| \sum_{j=1}^N \epsilon_j \sum_{k=1}^N \widehat{A}_{j,k}\right\|_{S_{2m}}^{2m}\notag\\
&\leq C_m^{2m} 
\max\left\{ \left\| \left( \sum_j \widetilde{B}_j \widetilde{B}_j^*\right)^{1/2} \right\|_{S_{2m}}^{2m},\right.\notag\\
&\phantom{\leq C_m^{2m} \max \{\{} \left.
\left\| \left( \sum_j \widetilde{B}_j^* \widetilde{B}_j\right)^{1/2} \right\|_{S_{2m}}^{2m} \right\}, \notag\end{aligned}$$ where $\widetilde{B}_j \,=\, \sum_{k=1}^N \widehat{A}_{j,k}$. Using (\[wideAA\]) we see that $$\sum_j \widetilde{B}_j \widetilde{B}_j^* = \sum_{k,j} A_{j,k} A_{j,k}^*.$$ Furthermore, with the block matrix $$\begin{aligned}
F = \left(\begin{array}{cc}\widetilde{B}_1\\\widetilde{B}_2\\ \vdots \\
\widetilde{B}_N\end{array}\right) 
\,=\, \left(\begin{array}{cccc}
A_{1,1} & A_{1,2} & \hdots & A_{1,N}\\
A_{2,1} & A_{2,2} & \hdots & A_{2,N}\\
\vdots & \vdots & \vdots & \vdots \\
A_{N,1} & A_{N,2} & \hdots & A_{N,N} \\ 
\end{array}\right) \notag\end{aligned}$$ we have $$\|(\sum_k \widetilde{B}_k^* \widetilde{B}_k)^{1/2}\|_{S_{2m}}^{2m}
\,=\, \|(F^* F)^{1/2} \|_{S_{2m}}^{2m} \,=\, \|F\|_{S_{2m}}^{2m}.$$ Hence, $$E_1 \leq C_m^{2m} \max\left\{ \|(\sum_{j,k=1}^N A_{j,k} A_{j,k}^*)^{1/2}\|_{S_{2m}}^{2m}, \|F\|_{S_{2m}}^{2m}\right\}.$$ As $\widetilde{A}_{j,k}$ differs from $\widehat{A}_{j,k}$ only by interchanging $A_{j,k}$ with $A_{j,k}^*$ we obtain similarly $$\begin{aligned}
&E_2 := {{\mathbb{E}}}\left\| \sum_{j=1}^N \epsilon_j \sum_{k=1}^N \widetilde{A}_{j,k} \right\|_{S_{2m}}^{2m}\notag\\
&\leq \max\left\{\left\|\left(\sum_{j,k=1}^N A_{j,k}^* A_{j,k} \right)^{1/2}\right\|_{S_{2m}}^{2m},\|F\|_{S_{2m}}^{2m} \right\}. \notag\end{aligned}$$ Finally, we obtain $$\begin{aligned}
& E \leq 4^{2m} C_m^{2m} (E_1 + E_2) \notag\\
& \leq 2 \cdot 4^{2m} C_m^{4m} \max\left\{\left\|\left(\sum_{j,k=1}^N A_{j,k}^* A_{j,k} \right)^{1/2}\right\|_{S_{2m}}^{2m},\right.\notag\\
& \phantom{\leq 2 \cdot 4^{2m} C_m^{4m} }
\left.
\left\|\left(\sum_{j,k=1}^N A_{j,k} A_{j,k}^* \right)^{1/2}\right\|_{S_{2m}}^{2m},\|F\|_{S_{2m}}^{2m}\right\}.\notag\end{aligned}$$ This concludes the proof.

Repeating the above proof for the scalar case (which removes the factor $\pi/2$ in the constant) and applying interpolation (see and below) yields the following (compare also [@mcta86 Proposition 2.2]).

\[Scalar\_Khintchine\] Let $a_{j,k} \in {{\mathbb{C}}}$, $j,k=1,\hdots,N$ be numbers with $a_{j,j} = 0$, $j=1,\hdots,N$. Let $\epsilon_k$, $k=1, \hdots, N$ be independent Bernoulli $\pm 1$ random variables. Then for $2 \leq p < \infty$ it holds $$\left[ {{\mathbb{E}}}\left| \sum_{j,k=1}^N \epsilon_j \epsilon_k a_{j,k} \right|^{p}\right]^{1/p} 
\leq d_p \left(\sum_{j,k=1}^N |a_{j,k}|^2\right)^{1/2},$$ where the constant $$d_p \,=\, 4^{1/p} (4/e) p.$$

Proof of the coherence estimate {#sec:proof:coherence}
===============================

Now we are equipped to provide the proof of Proposition \[prop:coherence\]. An inner product of two columns $s_i, s_\ell$ of the normalized matrix $\frac{1}{\sqrt{n}} S^b_\Omega$ has the form $$\langle s_i, s_\ell \rangle \,=\, \frac{1}{n} \sum_{r\in \Omega} b_{i - r \mod N} b_{\ell - r \mod N}
\,=\, \frac{1}{n} \sum_{j,k=1}^N b_{j} b_k a_{j,k}^{i,\ell},$$ where $a_{j,k}^{i,\ell} = 1$ if $(j,k) = (i - r \mod N, \ell-r \mod N)$ for some $r \in \Omega$ and $a_{j,k}^{i,\ell} = 0$ otherwise. Similarly, the inner product of the columns $t_i$ of the normalized matrix $\frac{1}{\sqrt{n}} T^c_\Omega$ can be written as $
\langle t_i, t_\ell \rangle = n^{-1} \sum_{j,k=-N+1}^{N-1} c_{j} c_k \tilde{a}_{j,k}^{i,\ell}
$ with $\tilde{a}_{j,k}^{i,\ell} = 1$ if $(j,k) = (i-r,\ell-r) \in \{1,\hdots,N\}^2$ for some $r \in \Omega$ and $0$ otherwise. Observe that $\sum_{j,k} |a_{j,k}|^2 = \sum_{j,k} |\tilde{a}_{j,k}|^2 = |\Omega| =n$. Now let $b\in {{\mathbb{R}}}^N$ and $c \in {{\mathbb{R}}}^{2N}$ be Rademacher series. Then Corollary \[Scalar\_Khintchine\] yields $$\begin{aligned}
&n\left({{\mathbb{E}}}|\langle s_i, s_j\rangle|^p\right)^{1/p}=  \left({{\mathbb{E}}}|\sum_{j,k} b_j b_k a_{j,k}^{i,\ell}|^p\right)^{1/p}\notag\\ 
&\leq 4^{1/p} (4/e) p  \left(\sum_{j,k} |a_{j,k}|^2 \right)^{1/2}= 4^{1/p} (4/e) p \sqrt{n}\notag\end{aligned}$$ for $p\geq 2$, and the same estimate holds for ${{\mathbb{E}}}|\langle t_i, t_j\rangle|^p$. In order to complete the proof we use the following simple and well-known probability estimate, see e.g. [@leta91; @tr06-2].

\[lem\_moment1\] Suppose $Z$ is a positive random variable satisfying $({{\mathbb{E}}}Z^p)^{1/p} \leq \alpha \beta^{1/p} p^{1/\gamma}$ for all $p_0 \leq p < \infty$ and some $\alpha,\beta,\gamma > 0$. Then for arbitrary $\kappa > 0$, $${{\mathbb{P}}}(Z \geq e^\kappa \alpha u) \leq \beta e^{-\kappa u^\gamma}$$ for all $u \geq p_0$.

By Markov’s inequality we obtain $${{\mathbb{P}}}(Z \geq e^\kappa \alpha u)
\leq \frac{{{\mathbb{E}}}Z^p}{(e^\kappa \alpha u)^p}
\leq  \beta \left(\frac{\alpha p^{1/\gamma}}{e^\kappa \alpha u}\right)^p .$$ Choosing $p=u^\gamma$ yields the statement.

Lemma \[lem\_moment1\] with the optimal choice $\kappa = 1$ yields $${{\mathbb{P}}}(n |\langle s_i,s_\ell \rangle| \geq  4 \sqrt{n} u)
\leq 4 e^{- u}$$ for $u\geq 2$. Taking the union bound over all possible pairs of different columns $s_i, s_\ell$ we obtain $$\begin{aligned}
{{\mathbb{P}}}(\mu \geq  4 n^{-1/2} u) \leq 2 N^2 e^{-u}.\notag\end{aligned}$$ Set the right hand side to $\epsilon$. Then the resulting $u = \log(2N^2/\epsilon) \geq 2$ since we may assume without loss of generality that $N\geq 2$. We obtain $${{\mathbb{P}}}\left(\mu \geq 4 \frac{\log(2N^2/\epsilon)}{\sqrt{n}}\right) \leq \epsilon.$$ The same holds for the coherence of $\frac{1}{\sqrt{n}} T_\Omega^c$.

Proof of Theorem \[thm:condition\]
==================================

We introduce the elementary shift operators on ${{\mathbb{R}}}^N$, $(S_j x)_\ell = x_{\ell - j \mod N}$, $j=1,\hdots,N$, and $$(T_j x)_\ell = \left\{\begin{array}{ll} x_{\ell-j} & \mbox{if } 1 \leq \ell-j \leq N, \\
0 & \mbox{otherwise}, 
\end{array} \right.$$ for $j = -N+1,\hdots,N-1$, $\ell=1,\hdots,N$. Further, denote by $R_\Omega: {{\mathbb{R}}}^N \to {{\mathbb{R}}}^\Omega$ the operator that restricts a vector to the indices in $\Omega$. Then we can write $$\begin{aligned}
S_\Omega^b = R_\Omega \sum_{j=1}^N \epsilon_j S_j \quad \mbox{and} \quad 
T_\Omega^c  = R_\Omega \sum_{j=-N+1}^{N-1} \epsilon_j T_j, \notag\end{aligned}$$ where $(\epsilon_j)$ is a Rademacher sequence. Denote by $A$ either $\frac{1}{\sqrt{n}} S_\Omega^b$ or $\frac{1}{\sqrt{n}} T_\Omega^c$. We need to prove a bound on the operator norm of $X_\Lambda := A_\Lambda^* A_\Lambda - I_\Lambda$ where $I_\Lambda$ denotes the identity on ${{\mathbb{R}}}^\Lambda$. We introduce $R_\Lambda^*: {{\mathbb{R}}}^\Lambda \to {{\mathbb{R}}}^N$ to be the extension operator that fills up a vector in ${{\mathbb{R}}}^\Lambda$ with zeros outside $\Lambda$. Further, we denote by $D_j$ either $S_j$ or $T_j$. Observe that $$\begin{aligned}
&A_\Lambda^* A_\Lambda \, =\, \frac{1}{n} \sum_{j}\epsilon_j R_\Lambda D_j^* R_\Omega^* \sum_{k} \epsilon_{k} R_\Omega D_{k} R_\Lambda^*\notag\\
&=\, \frac{1}{n} \sum_{\substack{j,k\\j\neq k}} \epsilon_j \epsilon_{k} R_\Lambda D_j^* P_\Omega D_{k} R_\Lambda^* + \frac{1}{n} R_\Lambda \left(\sum_{j} D_j^* P_\Omega D_j\right) R_\Lambda^*, \notag\end{aligned}$$ where $P_\Omega = R_\Omega^* R_\Omega$ denotes the projection operator which cancels all components of a vector outside $\Omega$. Here and in the following the sums range either over $\{1,\hdots,N\}$ or over $\{-N+1,\hdots,N-1\}$ depending on whether we consider circulant or Toeplitz matrices. It is straightforward to check that $$\label{sum_Khintch}
\sum_{j} D_j^* P_\Omega D_j = n I_N,$$ where $I_N$ is the identity on ${{\mathbb{R}}}^N$. Since $R_\Lambda R_\Lambda^* = I_\Lambda$ we obtain $$X_\Lambda = \frac{1}{n} \sum_{j\neq k} \epsilon_j \epsilon_i R_\Lambda D_j^* P_\Omega D_k R_\Lambda^* = \frac{1}{n} \sum_{j \neq k} \epsilon_j \epsilon_k A_{j,k}$$ with $A_{j,k} = R_\Lambda D_j^* P_\Omega D_k R_\Lambda^*$. Our goal is to apply Corollary \[Bernoulli\_Khintchine\]. To this end we first observe that by $$\begin{aligned}
\sum_j A_{j,k}^* A_{j,\ell} \, & = \, R_\Lambda D_k^* P_\Omega \left( \sum_j D_j P_\Lambda D_j^*\right) P_\Omega D_\ell R_\Lambda^*\notag\\
&=\, {s}R_\Lambda D_k^* P_\Omega  D_\ell R_\Lambda^*. \notag\end{aligned}$$ Using once more this yields $$\sum_{j,k} A_{j,k}^* A_{j,k} = {s}R_\Lambda \left(\sum_{k} D_k^* P_\Omega D_k\right) R_\Lambda^* = {s}n R_\Lambda R_\Lambda^* = {s}n I_\Lambda.$$ Since the entries of all matrices $A_{j,k}$ are non-negative we get $$\begin{aligned}
& \|(\sum_{j\neq k} A_{j,k}^* A_{j,k})^{1/2}\|_{S_{2m}}^{2m}  = {\operatorname{Tr}}\left( \sum_{j \neq k} A_{j,k}^* A_{j,k}\right)^m \notag\\
&\leq {\operatorname{Tr}}\left(\sum_{j,k}
A_{j,k}^* A_{j,k}\right)^m = {\operatorname{Tr}}\left( {s}n I_\Lambda\right)^m  = {s}^{m+1} n^m,  \notag\end{aligned}$$ where ${\operatorname{Tr}}$ denotes the trace. Furthermore, since $A_{j,k}^* = A_{k,j}$ we have $\sum_{j\neq k} A_{j,k}^* A_{j,k} = 
\sum_{j\neq k} A_{j,k} A_{j,k}^*$. Let $F$ denote the block matrix $F = (\tilde{A}_{j,k})_{j,k}$ where $\tilde{A}_{j,k} = A_{j,k}$ if $j \neq k$ and $\tilde{A}_{j,j} = 0$. Using once again that the entries of all matrices are non-negative we obtain $$\begin{aligned}
& \|F\|_{S_{2m}}^{2m} = {\operatorname{Tr}}\left[(F^*F)^m\right] \notag\\
& = {\operatorname{Tr}}\left[\sum_{\substack{j_1,j_2,\hdots,j_m\\k_1,k_2,\hdots,k_m}} \tilde{A}_{j_1,k_1}^* \tilde{A}_{j_1,k_2} \tilde{A}_{j_2,k_2}^* \tilde{A}_{j_2,k_3} \cdots \tilde{A}^*_{j_m,k_m} \tilde{A}_{j_m,k_1}\right]\notag\\
& \leq {\operatorname{Tr}}\sum_{k_1,\hdots,k_m} \left[\sum_{j_1} A_{j_1,k_1}^* A_{j_1,k_2} \cdots \sum_{j_m} A_{j_m,k_m}^* A_{j_m,k_1}\right]\notag\\
& = {s}^m {\operatorname{Tr}}\sum_{k_1,\hdots,k_m} \left[R_\Lambda D_{k_1}^* P_\Omega D_{k_2} R_\Lambda^* R_\Lambda D_{k_2}^* P_\Omega D_{k_3} R_\Lambda^* \cdots
\right.
\notag\\
& \phantom{=  {s}^m {\operatorname{Tr}}\sum_{k_1,\hdots,k_m} [}\left.
\cdots R_\Lambda D_{k_m}^* P_\Omega D_{k_1} R_\Lambda^*\right],\notag\end{aligned}$$ where we applied also once more. Using the cyclicity of the trace and applying another time, together with the fact that $T_k = T_{-k}^*$ and $S_k = S_{N-k}^*$, gives $$\begin{aligned}
&\|F\|_{S_{2m}}^{2m} \leq {s}^m {\operatorname{Tr}}\left[\sum_{k_1} D_{k_1} P_\Lambda D_{k_1}^* P_\Omega \sum_{k_2} D_{k_2} P_\Lambda D_{k_2}^* P_\Omega \cdots
\right. \notag\\ 
& \phantom{\|F\|_{S_{2m}}^{2m} \leq } 
\left. \cdots \sum_{k_n} D_{k_n} P_\Lambda D_{k_n}^* P_\Omega\right] = {s}^{2m} {\operatorname{Tr}}[ P_\Omega]
= n {s}^{2m}.\notag\end{aligned}$$ Since by assumption (\[cond:conditioning\]) ${s}\leq n$ it follows that $$\begin{aligned}
&\|F\|_{S_{2m}}^{2m} \leq \|(\sum_{j\neq k} A_{j,k}^* A_{j,k})^{1/2}\|_{S_{2m}}^{2m}\notag\\
& = \|(\sum_{j\neq k} A_{j,k} A_{j,k}^*)^{1/2}\|_{S_{2m}}^{2m} \,\leq\, n^m {s}^{m+1}.\notag\end{aligned}$$ Using $\|X_\Lambda\| = \|X_\Lambda\|_{S_\infty} \leq \|X_\Lambda\|_{S_p}$ and applying the Khintchine inequality in Theorem \[Bernoulli\_Khintchine\] we obtain for an integer $m$ $$\begin{aligned}
&{{\mathbb{E}}}\|X_\Lambda\|^{2m} = {{\mathbb{E}}}\|A_\Lambda^* A_\Lambda - I_\Lambda\|^{2m} \leq 
{{\mathbb{E}}}\|A_\Lambda^* A_\Lambda - I_\Lambda\|_{S_{2m}}^{2m}\notag\\
&= \frac{1}{n^{2m}} {{\mathbb{E}}}\|\sum_{j\neq k} \epsilon_j \epsilon_k A_{j,k}\|_{S_{2m}}^{2m}\leq\, 2 (2\pi)^{2m} \left(\frac{(2m)!}{2^m m!}\right)^{2} \frac{{s}^{m+1}}{n^m}\notag.\end{aligned}$$ Stirling’s formula gives $$\label{Stirling1}
\frac{(2m)!}{2^m m!} = \frac{\sqrt{2\pi 2m} (2m/e)^{2m} e^{\lambda_{2m}}}{2^m \sqrt{2\pi m}
(m/e)^m e^{\lambda_m}} 
\leq \sqrt{2}\, (2/e)^m m^m,$$ where $\frac{1}{12m+1} \leq \lambda_m \leq \frac{1}{12m}$. An application of Hölder’s inequality yields for $\theta \in [0,1]$ and an arbitrary random variable $Z$. $$\begin{aligned}
{{\mathbb{E}}}|Z|^{2m+2\theta} & = 
{{\mathbb{E}}}[|Z|^{(1-\theta)2m} |Z|^{\theta (2m+2)}]\notag\\
& \leq ({{\mathbb{E}}}|Z|^{2m})^{1-\theta} ({{\mathbb{E}}}|Z|^{2m+2})^\theta.\label{interpol1}\end{aligned}$$ Combining our estimates above gives $$\begin{aligned}
&{{\mathbb{E}}}\|X_\Lambda\|^{2m+2\theta}
\leq ({{\mathbb{E}}}\|X_\Lambda\|^{2m})^{1-\theta} ({{\mathbb{E}}}\|X_\Lambda\|^{2m+2})^{\theta}\notag\\
&\leq 4 (2\pi)^{2m+2\theta} (2/e)^{2m+2\theta} m^{2m(1-\theta)} (m+1)^{2\theta(m+1)} \frac{{s}^{m+\theta+1}}{n^{m+\theta}}\notag\\
&\leq 4 \left(\frac{4\pi}{e}\right)^{2m+2\theta} (m+\theta)^{2m+2\theta}
 \frac{{s}^{m+\theta+1}}{n^{m+\theta}},\notag\end{aligned}$$ where we used the inequality between the geometric and arithmetic mean in the third step. In other words, for $p\geq 2$, $$\left({{\mathbb{E}}}\|X_\Lambda\|^{p}\right)^{1/p} \leq \frac{2\pi}{e} \sqrt{\frac{{s}}{n}} (4{s})^{1/p} p.$$ An application of Lemma \[lem\_moment1\] with the optimal value $\kappa = 1$ yields $${{\mathbb{P}}}\left(\|X_\Lambda\| \geq 2\pi \sqrt{\frac{{s}}{n}} u\right) 
\leq 4{s}e^{-u}$$ for all $u\geq 2$. Setting the right hand side equal $\epsilon$ shows that $\|X_\Lambda\| \leq \delta$ with probability at least $1-\epsilon$ provided $$n \geq (2\pi)^2 \delta^{-2} s \log^2(4{s}/\epsilon).$$ This completes the proof of Theorem \[thm:condition\].

Acknowledgements {#acknowledgements .unnumbered}
================

This work was supported by the Hausdorff Center for Mathematics, University of Bonn and the WWTF project SPORTS (MA 07-004).

[10]{} \[1\][\#1]{} url@samestyle \[2\][\#2]{} \[2\][[l@\#1=l@\#1\#2]{}]{}

D. L. [D]{}onoho, “[C]{}ompressed sensing,” *[I]{}[E]{}[E]{}[E]{} [T]{}rans. [I]{}nform. [T]{}heory*, vol. 52, no. 4, pp. 1289–1306, 2006.

R. G. [B]{}araniuk, M. [D]{}avenport, R. A. [D]{}e[V]{}ore, and M. [W]{}akin, “[A]{} simple proof of the restricted isometry property for random matrices,” *[C]{}onstr. [A]{}pprox.*, vol. 28, no. 3, pp. 253–263, 2008.

E. J. [C]{}and[è]{}s and T. [T]{}ao, “[N]{}ear optimal signal recovery from random projections: universal encoding strategies?” *[I]{}[E]{}[E]{}[E]{} [T]{}rans. [I]{}nform. [T]{}heory*, vol. 52, no. 12, pp. 5406–5425, 2006.

H. [R]{}auhut, “[S]{}tability results for random sampling of sparse trigonometric polynomials,” *[I]{}[E]{}[E]{}[E]{} [T]{}rans. [I]{}nform. [T]{}heory*, vol. 54, no. 12, pp. 5661–5670, 2008.

M. [R]{}udelson and R. [V]{}ershynin, “[S]{}parse reconstruction by convex relaxation: [F]{}ourier and [G]{}aussian measurements,” in *[P]{}roc. [C]{}[I]{}[S]{}[S]{} 2006 (40th [A]{}nnual [C]{}onference on [I]{}nformation [S]{}ciences and [S]{}ystems)*, 2006.

W. [B]{}ajwa, J. [H]{}aupt, G. [R]{}az, S. [W]{}right, and R. [N]{}owak, “[T]{}oeplitz-structured compressed sensing matrices.” 2007, [I]{}[E]{}[E]{}[E]{} [W]{}orkshop [S]{}[S]{}[P]{},.

J. [R]{}omberg, “[C]{}ompressive sensing by random convolution,” *preprint*, 2008.

W. U. [B]{}ajwa, J. [H]{}aupt, G. [R]{}az, and R. [N]{}owak, “Compressed channel sensing,” in *Proc. CISS’08*, Princeton, 2008.

S. [B]{}oyd and L. [V]{}andenberghe, *[C]{}onvex [O]{}ptimization.*1em plus 0.5em minus 0.4emambridge [U]{}niv. [P]{}ress, 2004.

B. [E]{}fron, T. [H]{}astie, I. [J]{}ohnstone, and R. [T]{}ibshirani, “[L]{}east angle regression,” *[A]{}nn. [S]{}tatist.*, vol. 32, no. 2, pp. 407–499, 2004.

G. [D]{}avis, S. [M]{}allat, and M. [A]{}vellaneda, “[A]{}daptive greedy approximations,” *[C]{}onstr. [A]{}pprox.*, vol. 13, no. 1, pp. 57–98, 1997.

E. J. [C]{}and[è]{}s, [J]{}., T. [T]{}ao, and J. [R]{}omberg, “[R]{}obust uncertainty principles: exact signal reconstruction from highly incomplete frequency information,” *[I]{}[E]{}[E]{}[E]{} [T]{}rans. [I]{}nform. [T]{}heory*, vol. 52, no. 2, pp. 489–509, 2006.

D. L. [D]{}onoho and J. [T]{}anner, “[C]{}ounting faces of randomly-projected polytopes when the projection radically lowers dimension,” *[J]{}. [A]{}mer. [M]{}ath. [S]{}oc.*, vol. 22, no. 1, pp. 1–53, 2009.

R. [G]{}ribonval and M. [N]{}ielsen, “[S]{}parse representations in unions of bases,” *[I]{}[E]{}[E]{}[E]{} [T]{}rans. [I]{}nform. [T]{}heory*, vol. 49, no. 12, pp. 3320–3325, 2003.

H. [R]{}auhut, “[R]{}andom sampling of sparse trigonometric polynomials,” *[A]{}ppl. [C]{}omput. [H]{}armon. [A]{}nal.*, vol. 22, no. 1, pp. 16–42, 2007.

E. J. [C]{}and[è]{}s, “[T]{}he restricted isometry property and its implications for compressed sensing,” *Compte Rendus de l’Academie des Sciences, Paris, Serie I*, vol. 346, pp. 589–592, 2008.

S. [F]{}oucart and M. [L]{}ai, “[S]{}parsest solutions of underdetermined linear systems via $\ell_q$-minimization for $0<q\leq 1$,” *[A]{}ppl. [C]{}omput. [H]{}armon. [A]{}nal.*, to appear.

J. [T]{}ropp, M. [W]{}akin, M. [D]{}uarte, D. [B]{}aron, and R. [B]{}araniuk, “[R]{}andom filters for compressive sampling and reconstruction,” *[P]{}roc. 2006 [I]{}[E]{}[E]{}[E]{} [I]{}nt. [C]{}onf. [A]{}coustics, [S]{}peech, and [S]{}ignal [P]{}rocessing*, vol. 3, pp. 872–875, [M]{}ay 2006.

J. J. [F]{}uchs, “[O]{}n sparse representations in arbitrary redundant bases,” *[I]{}[E]{}[E]{}[E]{} [T]{}rans. [I]{}nform. [T]{}heory*, vol. 50, no. 6, pp. 1341–1344, 2004.

J. A. [T]{}ropp, “[R]{}ecovery of short, complex linear combinations via $l_1$ minimization,” *[I]{}[E]{}[E]{}[E]{} [T]{}rans. [I]{}nform. [T]{}heory*, vol. 51, no. 4, pp. 1568–1570, 2005.

——, “[O]{}n the conditioning of random subdictionaries,” *[A]{}ppl. [C]{}omput. [H]{}armon. [A]{}nal.*, vol. 25, pp. 1–24, 2008.

F. [L]{}ust[-]{}[P]{}iquard, “[I]{}n[é]{}galites de [K]{}hintchine dans ${C}_p (1 < p <
  \infty)$,” *[C]{}. [R]{}. [A]{}cad. [S]{}ci. [P]{}aris [S]{}’er. [I]{} [M]{}ath.*, vol. 303, pp. 289–292, 1986.

A. [B]{}uchholz, “[O]{}perator [K]{}hintchine inequality in non-commutative probability,” *[M]{}ath. [A]{}nn.*, vol. 319, pp. 1–16, 2001.

M. [L]{}edoux and M. [T]{}alagrand, *[P]{}robability in [B]{}anach [S]{}paces. [I]{}soperimetry and [P]{}rocesses.*1em plus 0.5em minus 0.4emerlin, [H]{}eidelberg, [N]{}ew[Y]{}ork: [S]{}pringer-[V]{}erlag, 1991, vol. 23.

J. [B]{}ourgain and L. [T]{}zafriri, “[I]{}nvertibility of ’large’ submatrices with applications to the geometry of [B]{}anach spaces and harmonic analysis,” *[I]{}srael [J]{}. [M]{}ath.*, vol. 57, no. 2, pp. 137–224, 1987.

V. H. de la [P]{}e[ñ]{}a and E. [G]{}in[é]{}, *[D]{}ecoupling, [F]{}rom dependence to independence*, ser. [P]{}robability and its [A]{}pplications ([N]{}ew [Y]{}ork).1em plus 0.5em minus 0.4emew [Y]{}ork: [S]{}pringer-[V]{}erlag, 1999.

T. R. [M]{}c[C]{}onnell and M. S. [T]{}aqqu, “[D]{}ecoupling inequalities for multilinear forms in independent symmetric random variables,” *Annals Prob.*, vol. 11, no. 3, pp. 943–951, 1986.
