---
abstract: 'Compressed sensing provided a data-acquisition paradigm for sparse signals. Remarkably, it has been shown that practical algorithms provide robust recovery from noisy linear measurements acquired at a near optimal sampling rate. In many real-world applications, a signal of interest is typically sparse not in the canonical basis but in a certain transform domain, such as wavelets or the finite difference. The theory of compressed sensing was extended to the analysis sparsity model but known extensions are limited to specific choices of sensing matrix and sparsifying transform. In this paper, we propose a unified theory for robust recovery of sparse signals in a general transform domain by convex programming. In particular, our results apply to general acquisition and sparsity models and show how the number of measurements for recovery depends on properties of measurement and sparsifying transforms. Moreover, we also provide extensions of our results to the scenarios where the atoms in the transform has varying incoherence parameters and the unknown signal exhibits a structured sparsity pattern. In particular, for the partial Fourier recovery of sparse signals over a circulant transform, our main results suggest a uniformly random sampling. Numerical results demonstrate that the variable density random sampling by our main results provides superior recovery performance over known sampling strategies.'
author:
- |
    Kiryung Lee, Yanjun Li , Kyong Hwan Jin,\
    and Jong Chul Ye,  [^1]
title: |
    Unified Theory for Recovery of Sparse Signals\
    in a General Transform Domain
---

Compressed sensing, analysis sparsity model, sparsifying transform, total variation, incoherence, variable density sampling.

Introduction {#sec:intro}
============

The theory of compressed sensing (CS) [@donoho2006compressed; @candes2006robust] provided a new data-acquisition paradigm for sparse signals. Remarkably, it has been shown that practical algorithms are guaranteed to reconstruct the unknown sparse signal from the linear measurements taken at a provably near optimal rate. Reconstruction algorithms with performance guarantees include modern optimization algorithms for $\ell_1$-norm-based convex optimization formulations (e.g., [@beck2009fast; @boyd2011distributed]) and iterative greedy algorithms (e.g., [@needell2009cosamp; @dai2009subspace; @blumensath2009iterative; @foucart2011hard]).

The canonical sparsity model in CS assumes that the unknown signal $f \in \cz^d$ is $s$-sparse in the standard coordinate basis. In other words, $\norm{f}_0 \leq s$, where $\norm{\cdot}_0$ counts the number of nonzero elements. The acquisition process in CS is linear and represented by a sensing matrix $A \in \cz^{m \times d}$ so that the $m$ linear measurements in $b \in \cz^m$ is given by $$b = A f + w,$$ where $w \in \cz^m$ denotes additive noise to the measurements and satisfies $\norm{w}_2 \leq \epsilon$. For certain random sensing matrices, it was shown that an estimate $\hat{f}$ given by $$\label{eq:bpdn}
\hat{f} = \argmin_{\tilde{f} \in \cz^d} \norm{\tilde{f}}_1 \quad \mathrm{subject~to} \quad \norm{b - A \tilde{f}}_2 \leq \epsilon$$ satisfies $\norm{\hat{f} - f}_2 \leq c_1 \epsilon$ with high probability, provided that $m \geq C s \log^\alpha d$ for some $\alpha \in \mathbb{N}$ and numerical constants $C$ and $c_1$. In particular, in the noiseless case ($\epsilon = 0$), the estimate $\hat{f}$ coincides with the ground truth signal $f$. For example, Candes and Tao [@candes2005decoding] showed that the above guarantees hold for a Gaussian sensing matrix $A$ whose entries are i.i.d. following $\mathcal{N}(0,1/m)$ via the restricted isometry property (RIP). Recent results with a sharper sample complexity of $m \geq 2 s \log(d/s)$ were derived using the Gaussian width of a tangent cone [@chandrasekaran2012convex; @amelunxen2014living].

In fact, the original idea of compressed sensing [@bresler1999image] was motivated by a need to accelerate various imaging modalities. The sensing matrix $A$ in these applications takes observations in a measurement transform domain, i.e. $$\label{eq:structred_sensing_mtx}
A = \sqrt{\frac{n}{m}} S_\Omega \Psi,$$ where $\Psi \in \cz^{n \times d}$ is the matrix representation of the measurement transform and the sampling operator $S_\Omega: \cz^n \to \cz^m$ takes the $m$ elements indexed by $\Omega = \{\omega_1,\omega_2,\ldots,\omega_m\}$. For example, when $\Psi$ is a discrete Fourier transform (DFT) matrix, $A$ is a partial Fourier matrix. The aforementioned near optimal performance guarantees were shown for a partial Fourier sensing matrix $A$ obtained using a random set $\Omega$ [@candes2006robust; @candes2006near; @rudelson2008sparse; @candes2011probabilistic] and generalized for the case where the rows of $\Psi \in \cz^{n \times d}$ correspond to an incoherent tight frame for $\cz^d$ [@rauhut2010compressive].

However, in numerous imaging applications, a signal of interest is not sparse in the standard coordinate basis. The theory of compressed sensing was accordingly extended to the so-called synthesis and analysis sparsity models [@candes2011compressed; @nam2013cosparse; @giryes2014greedy]. The synthesis sparsity model assumes that $f \in \cz^d$ is represented as a linear combination of few atoms in a dictionary $D \in \cz^{d \times N}$. Equivalently, $f$ is represented as $f = D u$ with an $s$-sparse coefficient vector $u \in \cz^N$. Compressed sensing with the synthesis sparsity model can be interpreted as conventional compressed sensing of $u$ using a sensing matrix $A D$ where $u$ is $s$-sparse in the standard basis. In particular when $A$ is a Gaussian matrix and $D$ is an orthogonal matrix, conventional performance guarantees carry over to the synthesis sparsity model. On the other hand, the analysis sparsity model, which is motivated from sparse representation in harmonic analysis [@mallat2008wavelet], assumes that the transform $\Phi f \in \cz^N$ of $f$ via $\Phi \in \cz^{N \times d}$ is $s$-sparse. In fact, a signal of interest in practical applications often follows the analysis sparsity model via various transforms including finite difference and wavelet [@mallat2008wavelet], contourlet [@do2005contourlet], curvelet [@starck2002curvelet], and Gabor transforms. Thus, the analysis sparsity model has been used as an effective regularizer for classical inverse problems in signal processing (e.g., denoising and deconvolution) and compressed sensing imaging (e.g., [@lustig2008compressed]).

Unlike the previous results with the canonical sparsity model, the theory of compressed sensing with the analysis model has been relatively less explored and known results are limited to specific cases. Candes et al. [@candes2011compressed] considered the recovery of $f \in \cz^d$ such that $\Phi f$ is $s$-sparse for a transform $\Phi \in \cz^{N \times d}$ satisfying $\Phi^* \Phi = I_d$, i.e. the columns of $\Phi^*$ correspond to a tight frame for $\cz^d$. They showed that $$\label{eq:bpdn_tfm}
\hat{f} = \argmin_{\tilde{f} \in \cz^d} \norm{\Phi \tilde{f}}_1 \quad \mathrm{subject~to} \quad \norm{A \tilde{f} - b}_2 \leq \epsilon$$ has the error bound given by $\norm{\hat{f} - f}_2 \leq c_1 \epsilon$, provided that the sensing matrix $A \Phi^*$ satisfies the RIP. In particular for a Gaussian sensing matrix $A$, their performance guarantee holds with high probability for $m = O(s \log(d/s))$ for any $\Phi$ satisfying $\Phi^* \Phi = I_d$. Indeed the performance guarantee by Candes et al. [@candes2011compressed] applies beyond the case of a Gaussian sensing matrix $A$. Krahmer and Ward [@krahmer2011new] showed that if $A \in \cz^{m \times d}$ and $D \in \cz^{d \times N}$ satisfy the RIP and $\varepsilon \in \mathbb{R}^d$ is a Rademacher sequence with random $\pm 1$ entries, then $A \diag(\varepsilon) D$ satisfies the RIP, where $\diag(\varepsilon) \in \cz^{d \times d}$ denotes the diagonal matrix whose diagonal entries are $\varepsilon$. However, applying a random sign before the acquisition might not be feasible in certain applications. In another line of research, it was shown [@nam2013cosparse; @giryes2014greedy] that greedy algorithms for the analysis sparsity model provide performance guarantees if the sensing matrix $A$ is a near isometry when acting on all transform-sparse $f$ such that $\Phi f$ is sparse. Again for $\Phi$ satisfying $\Phi^* \Phi = I_d$, this condition on $A$ is less demanding than the RIP of $A \Phi^*$ since the latter implies the former. However, it has not been studied how such a relaxation translates into less-demanding sample complexity.

A special analysis sparsity model associated with the finite difference transform $\Phi$ has been of particular interest in signal processing and imaging applications. The corresponding convex surrogate $\norm{\Phi f}_1$, known as the total variation (TV), has been popularly used as an effective regularizer for solving inverse problems. Needell and Ward [@needell2013stable] provided performance guarantees for TV minimization with a partial Fourier sensing matrix $A$ in terms of the RIP of $A D$ with a Haar wavelet dictionary $D$. Their result was further refined by Krahmer and Ward [@krahmer2014stable] with a clever idea of variable density sampling adopting the local incoherence parameters. Remarkably, Krahmer and Ward [@krahmer2014stable] provided performance guarantees at the sample complexity of $m = O(s \log^3 s \log^2 d)$. However, these results on TV minimization rely on a special embedding theorem that relates the Haar transform to the finite difference transform, which holds only for signals of dimension two or higher. Therefore, the results by Needell and Ward [@needell2013stable] and by Krahmer and Ward [@krahmer2014stable] do not apply to the 1D case and more importantly do not generalize to other sparsifying transforms.

Recently, inspired by analogous results for the canonical sparsity model [@chandrasekaran2012convex; @amelunxen2014living], Kabanava et al. [@kabanava2015robust] derived a performance guarantee of TV minimization with a Gaussian sensing matrix $A$ at the sample complexity of $m > d \,[1 - \{ 1-(s+1)/d \}^2/\pi]$. Cai and Xu [@cai2015guarantees] showed a similar result with $m \geq C \sqrt{s d} \log d$. Compared to the previous result by Krahmer and Ward [@krahmer2014stable], the above results [@kabanava2015robust; @cai2015guarantees] apply to the 1D case but at a significantly suboptimal sample complexity. More importantly, the use of a Gaussian sensing matrix might not be relevant to practical applications. Along a similar analysis strategy, Kabanava and Rauhut [@kabanava2015analysis] showed performance guarantees for with a Gaussian sensing matrix $A \in \mathbb{R}^{m \times d}$ and a frame analysis operator $\Phi \in \mathbb{R}^{N \times d}$ roughly at the sample complexity of $m \geq 2 \kappa s \log (2N/s)$, where $\kappa$ denotes the ratio of upper and lower frame bounds, i.e. $\kappa$ is the condition number of the frame operator $\Phi^* \Phi$. The sample complexity of this result for a tight frame is near optimal. However, their analysis is restricted to a Gaussian sensing matrix $A$ and does not generalize to other sensing matrices.

Contributions
-------------

Our main contribution is to derive performance guarantees for compressed sensing of analysis-sparse vectors by for general classes of sensing matrix $A$ given in the form of with measurement transform $\Psi$ and (redundant) analysis transform $\Phi$. Unlike the previous works, performance guarantees in this paper apply without being restricted to a particular choice of $\Phi$ and $\Psi$[^2]. The number of measurements implying these guarantees depends on certain properties of $(\Phi,\Psi)$ and this result identifies a class of measurement and sparsity models allowing recovery at a near optimal sampling rate. Moreover, when $\Psi$ and $\Phi$ have a few strongly correlated atoms, adopting the idea by Krahmer and Ward [@krahmer2014stable], we propose to acquire linear measurements using random sampling with respect to a variable density designed with the correlations between $\Psi$ and $\Phi$. This modified acquisition enables recovery at a lower sampling rate. We also extend the results to group sparsity models. This extension applies to various popular regularized recovery methods including the isotropic-total-variation minimization. In special cases where $\Psi$ is Fourier and $\Phi$ is a circulant matrix, our theory suggests a uniformly random sampling or its variation. For example, for the total variation minimization, unlike the common belief in practice, a sampling strategy that combines the acquisition of the lowest frequency and uniformly random sampling on the other frequencies provides better reconstruction than known variable density random sampling strategies.

Our main idea is inspired by a previous work on structured matrix completion by Chen and Chi [@chen2014robust]. They showed that a structured low-rank matrix (e.g., a low-rank Hankel matrix) is successfully recovered from partially observed entries by minimizing the nuclear norm. Indeed, their structured low-rank matrix completion can be interpreted as follows. The unknown structured matrix $M$ is given as the image $T x$ of the generator $x$ via a linear map $T$. Then the completion of the structured matrix $M$ with the low-rankness prior is equivalent to the completion of the generator $x$ with low-rankness in the transform domain via $T$. Similarly, compressed sensing with the analysis sparsity model is equivalent to the recovery of $x \in \cz^n$ with the prior that $T x \in \cz^N$ is $s$-sparse where the transform $T$ is given as $T = \Phi \Psi^\dagger$. Therefore the two problems are analogous to each other in the sense that their priors correspond to atomic sparsity [@chandrasekaran2012convex] in their respective transform domains. Moreover, in both the structured low-rank matrix model and the transform-domain sparsity model, $T$ is not necessarily surjective, which implies that $T T^*$ may be rank-deficient. This violates an important technical condition known as the *isotropy* property and many crucial steps in the proofs of existing performance guarantees for CS break down. To overcome this difficulty, we adopt the clever idea by Chen and Chi [@chen2014robust] through the aforementioned analogy and derive near optimal performance guarantees for the recovery of sparse signals in a transform domain without resorting to the isotropy property. However, besides this similarity, our results are significantly different from the analogous results [@chen2014robust] in the following sense. Chen and Chi [@chen2014robust] assumed that $T$ is restricted to a set of special linear operators that generate structured matrices and their analysis indeed relies critically on strong properties satisfied by such linear operators (e.g., $T$ needs to satisfy $T^* T = I_n$). Contrarily, we only assume a mild condition that $T$ is injective and the resulting performance guarantees apply to more general cases. For example, in compressed sensing with the analysis sparsity model, $T = \Phi \Psi^\dagger$ is non-unitary if the measurement transform $\Psi$ is non-unitary (e.g., the Radon transform) or the sparsifying transform $\Phi$ is non-unitary (e.g., biorthogonal wavelet and data-adaptive transforms).

We illustrate our theory through extensive Monte Carlo simulations. The variable density sampling in this paper provides an improved recovery performance over the previously suggested sampling strategies. For example, when $\Phi$ and $\Psi$ have atoms showing high correlation (e.g. Fourier and wavelet), our theory suggests to sample more densely in the lower frequencies, which enables successful recovery from fewer observations. Rather surprisingly, when $\Phi$ and $\Psi$ respectively correspond to the finite difference and the Fourier transforms, our theory suggests a special sampling density that always takes the lowest frequency and chooses the other frequency components randomly using the uniform density. This is contrary to the common belief in compressed sensing but the proposed sampling strategy turns out be more successful than previous works not only in theory but also empirically. These numerical results strongly support out new theory.

Organization
------------

The rest of this paper is organized as follows. The main results are presented in Sections \[sec:main\_result\] and \[sec:main\_result\_vd\], where the proofs are deferred to Sections \[sec:pf\_main\_result\_noiseless\] and \[sec:pf\_main\_result\_noisy\]. We extend the theory to the group sparsity models in Section \[sec:main\_result\_gs\] and study a special case of circulant transforms in Section \[sec:circulant\]. After demonstrating empirical observations in Section \[sec:numres\], which supports our main results, we conclude the paper with some final remarks in Section \[sec:concl\].

Notations
---------

For a positive integer $N$, we will use a shorthand notation $[N]$ for the set $\{1,\ldots,N\}$. For a vector $z \in \cz^N$, let $z[k]$ denote the $k$th element of $z$ for $k \in [N]$, i.e. $z = [z[1], z[2], \ldots, z[N]]^\transpose$. The Hadamard product of two vectors $x,y \in \cz^n$ is denoted by $x \odot y$. The circular convolution of two vectors $x,y \in \cz^n$ is denoted by $x \circledast y$. The Kronecker product of two matrices $A$ and $B$ is denoted by $A\otimes B$. The operator norm from $\ell_p^n$ to $\ell_q^N$ will be denoted by $\norm{\cdot}_{p \to q}$. For brevity, the spectral norm $\norm{\cdot}_{2 \to 2}$ will be written without subscript as $\norm{\cdot}$. For a matrix $A$, its Hermitian transpose and its Moore-Penrose pseudo inverse are respectively written as $A^*$ and $A^\dagger$.

For $J \subset [N]$, the coordinate projection with respect to $J$, denoted by $\Pi_J$, is defined as $$(\Pi_J z)[k] :=
\begin{dcases}
z[k] & k \in J, \\
0 & \mathrm{otherwise}.
\end{dcases}$$ The complex signum function, denoted by $\mbox{sgn}(\cdot): \cz^N \to \cz^N$, is defined as $$\label{eq:sgn}
(\mbox{sgn}(z))[k] :=
\begin{dcases}
\frac{z[k]}{|z[k]|} & z[k] \neq 0, \\
0 & \mathrm{otherwise}.
\end{dcases}$$ Let $e_1,\ldots,e_n$ denote the standard basis vectors for $\cz^n$. In other words, $e_k$ is the $k$th column of the $n$-by-$n$ identity matrix.

Recovery of Sparse Signals in a General Transform Domain {#sec:main_result}
========================================================

Let $T: \cz^n \to \cz^N$ be a linear map that we call a “transform” in this paper. Let $\Omega = \{\omega_1,\omega_2,\ldots,\omega_m\}$ denote the multi-set of $m$ sampling indices out of $[n] := \{1,\ldots,n\}$ with possible repetition of elements. Given $\Omega$, the sampling operator $S_\Omega: \cz^n \to \cz^m$ is defined so that the $j$th element of $S_\Omega x \in \cz^m$ is the $\omega_j$th element of $x \in \cz^n$ for $j = 1,\ldots,m$. We are interested in recovering an unknown signal $x \in \cz^n$ from its partial entries at $\Omega$ when the transform $T x$ is known $s$-sparse a priori, i.e. $\norm{T x}_0 \leq s$. Compressed sensing with the analysis sparsity model is an instance of this problem formulation as shown in the following. Recall that $\Psi$ is of full column rank. Let $T: \cz^n \to \cz^N$ be defined by $T = \Phi \Psi^\dagger$ where $\Psi^\dagger$ denotes the Moore-Penrose pseudo inverse of $\Psi$. Let $x \in \cz^n$ denote the vector containing fully sampled measurements, i.e. $x = \Psi f$. Since $f = \Psi^\dagger x$, we have $\Phi f = \Phi \Psi^\dagger x = T x$. Thus the recovery of $f$ from $b = \sqrt{n/m} S_\Omega \Psi f$ with the prior that $\Phi f$ is $s$-sparse is equivalent to the recovery of $x$ from $b = \sqrt{n/m} S_\Omega x$ with the prior that $T x$ is $s$-sparse.

In the noise-free scenario where partial entries of $x$ are observed exactly, we propose to estimate $x$ as the minimizer to the following optimization problem: $$\label{eq:ell1min}
\minimize_{g \in \cz^n} \, \norm{T g}_1 \quad \mathrm{subject~to} \quad S_\Omega g = S_\Omega x.$$ We provide a sufficient condition for recovering $x$ exactly by in the following theorem.

\[thm:uniqueness\] Suppose $T: \cz^n \to \cz^N$ is injective. Let $\gamma$ be defined by $$\label{eq:defgamma}
\gamma := \argmin_{\tilde{\gamma} > 0} \norm{\tilde{\gamma} T^* T - I_n},$$ where $\widetilde{T} = (T^\dagger)^*$. Let $\mu$ be given by $$\label{eq:incoherence}
\mu = \max_{k \in [n]} \max\left\{ n \norm{\gamma^{1/2} T e_k}_\infty^2, n \norm{\gamma^{-1/2} \widetilde{T} e_k}_\infty^2 \right\}.$$

Let $\Omega = \{\omega_1,\ldots,\omega_m\}$ be a multi-set of random indices where $\omega_k$s are i.i.d. following the uniform distribution on $[n]$. Suppose $T x$ is $s$-sparse. Then with probability $1 - e^{-\beta} - 3/n$, $x$ is the unique minimizer to provided $$m \geq \frac{C(1+\beta) \mu s}{1 - \norm{\gamma T^* T - I_n}} \left[ \log N
+ \log \left( \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} \right) \right].$$

See Section \[sec:pf\_main\_result\_noiseless\].

All the results in this section including Theorem \[thm:uniqueness\] as well as other similar results [@candes2011probabilistic; @gross2011recovering; @chen2014robust], all derived using the golfing scheme, provide an *instance* recovery guarantee that applies to a single arbitrary instance of $x$, which is a weaker result than the *uniform* recovery guarantee that applies to the set of all transform-sparse signals. In compressed sensing with the canonical sparsity model, an instance guarantee is given from a fewer measurements than the uniform guarantee [@candes2011probabilistic] by a poly-log factor. For matrix completion problems, the RIP do not hold and known results [@gross2011recovering; @chen2014robust] only provide an instance guarantee. We suspect that this is the case with the recovery problem in this paper.

Note that $\norm{T}_{1 \to 2}$ denotes the largest $\ell_2$-norm among all columns of $T$. Similarly, $\norm{T^\dagger}_{2 \to \infty} = \norm{\widetilde{T}}_{1 \to 2}$ denotes the largest $\ell_2$-norm among all columns of $\widetilde{T}$. In a special case when $T^* T = I_n$, we have $T^\dagger = T^*$. Thus $\norm{T}_{1 \to 2} = \norm{T^\dagger}_{2 \to \infty} = 1$. In general, if $\norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} = O(N^{\alpha_1})$ for some $\alpha_1 \in \mathbb{N}$ and $$\frac{1}{1 - \norm{\gamma T^* T  - I_n}} = O(\log^{\alpha_2} N)$$ for some $\alpha_2 \in \mathbb{N}$, then we get a performance guarantee at a near optimal scaling of sample complexity of $m = O(\mu s \log^\alpha N)$, where $\alpha = \alpha_1 + \alpha_2$. These are mild conditions and easily satisfied by transforms that arise in practical applications.

In the noisy scenario where partial entries of $x$ are observed with additive noise, we propose to estimate $x$ by solving the following optimization problem: $$\label{eq:ell1min_noisy}
\minimize_{g \in \cz^n} \, \norm{T g}_1
\quad \mathrm{subject~to} \quad \norm{S_{\Omega'} g - S_{\Omega'} x^\sharp}_2 \leq \epsilon,$$ where $x^\sharp$ denotes a noisy version of $x$, $\Omega'$ denotes the set of all unique elements in $\Omega$, and $S_{\Omega'}^*$ is the adjoint of the sampling operator $S_{\Omega'}$ that fills missing entries at outside $\Omega'$ with 0.

\[thm:stability1\] Suppose the hypotheses of Theorem \[thm:uniqueness\] hold. Let $\hat{x}$ be the minimizer to with $x^\sharp$ satisfying $$\label{eq:xharp_fid}
\norm{S_{\Omega'} (x - x^\sharp)}_2 \leq \epsilon.$$ Then $$\norm{\hat{x} - x}_2 \leq
\frac{\sigma_{\max}(T)}{\sigma_{\min}(T)}
\cdot
\left\{ 2 + 28 \sqrt{N} \left( 3 n \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} + 1 \right) \right\} \epsilon,$$

See Section \[subsec:pf:thm:stability1\].

We can tighten the upper bound on the estimation error in Theorem \[thm:stability1\] when $T^* T$ is well conditioned. To this end, we will use the following theorem, which is obtained by modifying [@lee2013oblique Theorem 3.1].

\[thm:rboplike\] Suppose $T: \cz^n \to \cz^N$ and $\widetilde{T} = (T^\dagger)^*$ satisfy with parameters $\mu$ and $\gamma$. Let $\Omega = \{\omega_1,\ldots,\omega_m\}$ be a multi-set of random indices where $\omega_k$s are i.i.d. following the uniform distribution on $[n]$. Then with probability $1-\xi$, we have $$\label{eq:rboplike}
\max_{|\widetilde{J}| \leq s} \left\| \Pi_{\widetilde{J}} \left(\frac{n}{m} T S_\Omega^* S_\Omega T^\dagger - T T^\dagger \right) \Pi_{\widetilde{J}} \right\| \leq \delta,
%\max_{|\widetilde{J}| \leq s} \left\| \Pi_{\widetilde{J}} \left(\frac{n}{m} B_\Omega - B\right) \Pi_{\widetilde{J}} \right\| \leq \delta,$$ provided $$\begin{aligned}
\label{eq:rboplike:cond1}
m {} & \geq \frac{C_1 \delta^{-2} \mu s \log^2 s \log N \log m}{1 - \norm{\gamma T^* T  - I_n}},
\intertext{and}
\label{eq:rboplike:cond2}
m {} & \geq C_2 \delta^{-2} \mu s \log (\xi^{-1}).\end{aligned}$$

See Appendix \[sec:pf:thm:rboplike\].

Using Theorem \[thm:rboplike\], we provide another sufficient condition for stable recovery of sparse signals in a transform domain, which has a smaller noise amplification factor.

\[thm:stability2\] Suppose $T: \cz^n \to \cz^N$ is injective. Suppose $T$ and $\widetilde{T} = (T^\dagger)^*$ satisfy with parameters $\mu$ and $\gamma$. Let $\Omega = \{\omega_1,\ldots,\omega_m\}$ be a multi-set of random indices where $\omega_k$s are i.i.d. following the uniform distribution on $[n]$. Let $\hat{x}$ be the minimizer to with $x^\sharp$ satisfying . Then there exist numerical constants $C, c > 0$ for which the following holds. With probability $1 - N^{-4}$, we have $$\norm{\hat{x} - x}_2 \leq
\frac{\sigma_{\max}(T)}{\sigma_{\min}(T)}
\cdot
\left[ 14\sqrt{N} + \frac{n}{m} \left\{ \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} (|\Omega|-|\Omega'|) +1 \right\} \right] \epsilon,$$ provided $$\label{eq:noisy_samp_comp}
m \geq \frac{C \mu s \log^4 N}{1 - \norm{\gamma T^* T - I_n}}.$$ Furthermore, if $T^* T = I_n$, then with probability $1 - N^{-4}$, $$\norm{\hat{x} - x}_2 \leq
\frac{\sigma_{\max}(T)}{\sigma_{\min}(T)}
\cdot
\left( 14\sqrt{N} + \frac{n}{m} R \right) \epsilon,$$ where $R$ is the count of the most repeated elements in $\Omega$.

See Section \[subsec:pf:thm:stability2\].

By the definition of $\Omega'$, we have $|\Omega|-|\Omega'| \leq m-1$. Suppose that $\norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} = O(1)$. The resulting noise amplification factor by Theorem \[thm:stability2\] is $O(\sqrt{N} + n)$, which is already smaller than $O(\sqrt{N} n)$ by Theorem \[thm:stability1\]. In fact, the distribution of $|\Omega'|$ is explicitly given by $$\mathbb{P}\left( |\Omega'| = \ell \right) = \frac{\stirling{m}{\ell} n!}{n^m (n-\ell)!},$$ where $\stirling{m}{\ell}$ denotes the Stirling number of the second kind defined by $$\stirling{m}{\ell} := \frac{1}{\ell!} \sum_{j=0}^\ell(-1)^{\ell-j} {\ell \choose j} j^m.$$ It would be possible to compute a more tight probabilistic upper bound on $|\Omega|-|\Omega'|$ with its distribution. However, because of the other factor $\sqrt{N}$, regardless of $|\Omega|-|\Omega'|$, the noise amplification factor by Theorem \[thm:stability2\] cannot be improved to $O(1)$ as shown for compressed sensing with the canonical sparsity model [@candes2011probabilistic] or with a special analysis model [@krahmer2014stable]. We admit that this suboptimality in noise amplification is a limitation of our analysis. It will be interesting to see whether one can obtain near optimal noise amplification for a general transform $T$.

Incoherence-Dependent Variable Density Sampling {#sec:main_result_vd}
===============================================

In the results of the previous section, the number of measurements is proportional to the incoherence parameter $\mu$ in , which is the worst case $\ell_\infty$-norm among $\{T e_k\}_{k=1}^n$ and $\{\widetilde{T} e_k\}_{k=1}^n$. In certain scenarios, these $\ell_\infty$-norms are unevenly distributed. For example, in compressed sensing with the analysis sparsity model, $T$ is given by $T = \Phi \Psi^\dagger$ with the sensing transform $\Psi \in \cz^{n \times d}$ and the sparsifying transform $\Phi \in \cz^{N \times d}$. If $\Psi$ and $\Phi$ correspond to the DFT and DWT (discrete wavelet transform), respectively, low-frequency atoms have larger correlations. Thus there are a few $T e_k$s that dominate the others with large $\ell_\infty$-norms. Krahmer and Ward [@krahmer2014stable] proposed a clever idea of sampling measurements with respect to a variable density adapted to the local incoherence parameters, which are $\{\norm{T e_k}_\infty\}_{k=1}^n$ and $\{\norm{\widetilde{T} e_k}_\infty\}_{k=1}^n$.[^3] Then the sample complexity depends on not the worst case incoherence parameter but the average of the local incoherence parameters. In this section, adopting the idea by Krahmer and Ward [@krahmer2014stable], we extend the results in Section \[sec:main\_result\] to the case where the local incoherence parameters are unevenly distributed. The following theorem is analogous to Theorem \[thm:uniqueness\] and provides a sufficient condition for recovery of sparse signals in a transform domain when measurements are sampled according to a variable density.

\[thm:uniqueness\_vd\] Suppose $T: \cz^n \to \cz^N$ is injective. Let $\mu_k$ and $\tilde{\mu}_k$ be defined by $$\label{eq:loc_incoherenceT}
\mu_k = n \norm{\gamma^{1/2} T e_k}_\infty^2
\quad \mathrm{and} \quad
\tilde{\mu}_k = n \norm{\gamma^{-1/2} \widetilde{T} e_k}_\infty^2$$ for all $k \in [n]$, where $\gamma$ is defined in from $T$ and $\widetilde{T} = (T^\dagger)^*$. Let $\Omega = \{\omega_1, \ldots, \omega_m\}$ be a multi-set of random indices where $\omega_k$s are independent copies of a random variable $\omega$ with the following distribution: $$\label{eq:variable_density}
\mathbb{P}(\omega = k) = \frac{\sqrt{\mu_k \tilde{\mu}_k}}{\sum_{j=1}^n {\sqrt{\mu_j \tilde{\mu}_j}}}, \quad \forall k \in [n].$$ Suppose $T x$ is $s$-sparse. Then with probability $1 - e^{-\beta} - 3/n$, $x$ is the unique minimizer to provided $$m \geq \frac{C(1+\beta) \bar{\mu} s}{1 - \norm{\gamma T^* T - I_n}} \left[ \log N
+ \log \left( \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} \right) \right],$$ where $\bar{\mu}$ is defined as $$\label{eq:defbarmu}
\bar{\mu} := \frac{1}{n} \sum_{k=1}^n \sqrt{\mu_k \tilde{\mu}_k}
%\bar{\mu} := \left( \frac{1}{n} \sum_{k=1}^n \mu_k \tilde{\mu}_k \right)^{1/2}.$$

Compared to Theorem \[thm:uniqueness\], Theorem \[thm:uniqueness\_vd\] provides a performance guarantee at a smaller sample complexity, where the worst-case incoherence parameter is replaced by the average incoherence parameter $\bar{\mu}$. Note that $\bar{\mu}$ is always no greater than the worst-case incoherence parameter $(\max_k \mu_k)^{1/2} (\max_k \tilde{\mu}_k)^{1/2}$. In particular when there exist dominant $\mu_k$s or $\tilde{\mu}_k$s compared to other incoherence parameters, the sample complexity of Theorem \[thm:uniqueness\_vd\] is much smaller than that of Theorem \[thm:uniqueness\].

Define $$\label{eq:defnu}
\nu := [\sqrt{\mu_1}, \ldots, \sqrt{\mu_n}]^\transpose
\quad \mathrm{and} \quad
\tilde{\nu} := [\sqrt{\tilde{\mu}_1}, \ldots, \sqrt{\tilde{\mu}_n}]^\transpose.$$ Without loss of generality, we may assume that $\mu_k$s and $\tilde{\mu}_k$s are strictly positive. Then all entries of $\nu$ and $\tilde{\nu}$ are nonzero.

Using $\nu$ and $\tilde{\nu}$, we construct a pair of weighted transforms $W$ and $\widetilde{W}$ as $$\label{eq:defW}
W = \sqrt{\bar{\mu}} T [\mbox{diag}(\nu)]^{-1}
\quad \mathrm{and} \quad
\widetilde{W} = \sqrt{\bar{\mu}} \widetilde{T} [\mbox{diag}(\tilde{\nu})]^{-1}.$$ Then, $W$ and $\widetilde{W}$ satisfy $$\label{eq:incoW}
\max_{k \in [n]} \norm{\gamma^{1/2} W e_k}_\infty \leq \sqrt{\frac{\bar{\mu}}{n}}
\quad \mathrm{and} \quad
\max_{k \in [n]} \norm{\gamma^{-1/2} \widetilde{W} e_k}_\infty \leq \sqrt{\frac{\bar{\mu}}{n}}.$$ Furthermore, we have $$\label{eq:isoW}
\begin{aligned}
\mathbb{E} \left( \frac{n}{m} \sum_{j=1}^m W S_\Omega^* S_\Omega \widetilde{W}^* \right)
{} & = \mathbb{E} \left( \frac{n}{m} \sum_{j=1}^m W e_{\omega_j} e_{\omega_j}^* \widetilde{W}^* \right) \\
{} & = \mathbb{E} \left( \frac{n}{m} \sum_{j=1}^m \bar{\mu} T [\mbox{diag}(\nu)]^{-1} e_{\omega_j} e_{\omega_j}^* [\mbox{diag}(\tilde{\nu})]^{-1} (\widetilde{T})^* \right) \\
{} & = \mathbb{E} \left( \frac{n}{m} \sum_{j=1}^m \frac{\bar{\mu}}{\sqrt{\mu_{\omega_j} \tilde{\mu}_{\omega_j}}} T e_{\omega_j} e_{\omega_j}^* T^\dagger \right) \\
{} & = \frac{1}{m} \sum_{j=1}^m T \widetilde{T}^\dagger = T T^\dagger.
\end{aligned}$$ Since $\mbox{diag}(\tilde{\nu})$ is an invertible matrix, $T$ and $W$ span the same subspace and $T T^\dagger$ is an orthogonal projection onto the span of $W$. Furthermore, $$\langle W e_{k'}, \widetilde{W} e_k \rangle = 0, \quad \forall k \neq k'.$$

Let $g = \sqrt{\bar{\mu}} [\mbox{diag}(\nu)]^{-1} g'$. Then $T g = W g'$. Thus is equivalent to $$\label{eq:ell1min_vd}
\minimize_{g' \in \cz^n} \, \norm{W g'}_1
\quad \mathrm{subject~to} \quad S_\Omega g' = \bar{\mu}^{-1/2} S_\Omega [\mbox{diag}(\nu)] x.$$

Applying Theorem \[thm:uniqueness\] to with incoherence parameter $\bar{\mu}$ completes the proof.

In the case when we are given sampled measurements corrupted with additive noise, Theorems \[thm:stability1\] and \[thm:stability2\] are modified according to the change of the distribution for choosing random sample indices.

\[thm:stability1\_vd\] Suppose the hypotheses of Theorem \[thm:uniqueness\_vd\] hold. Let $x^\sharp$ be a noisy version of $x$ that satisfies . Let $\hat{x}$ be the minimizer to $$\label{eq:ell1min_noisy_vd}
\minimize_{g \in \cz^n} \, \norm{T g}_1
\quad \mathrm{subject~to} \quad \norm{S_{\Omega'} [\rho \odot (g - x^\sharp)]}_2 \leq \epsilon,$$ where $\rho := \bar{\mu}^{-1/2} [\sqrt{\mu_1}, \dots, \sqrt{\mu_n}]^\transpose$. Then $$\norm{\hat{x} - x}_2 \leq
\frac{\sigma_{\max}(T)}{\sigma_{\min}(T)}
\cdot
\frac{\bar{\mu}}{\min_{k \in [n]} \tilde{\mu}_k}
\cdot
\left[ 2 + 28 \sqrt{N} \left( \frac{\max_{k \in [n]} \mu_k}{\min_{k \in [n]} \tilde{\mu}_k} \cdot 3 n \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} + 1 \right) \right] \epsilon.$$

Like Theorem \[thm:uniqueness\_vd\], Theorem \[thm:stability1\_vd\] provides a performance guarantee at a lower sample complexity (in order) when compared to Theorem \[thm:stability1\]. On the other hand, the noise amplification factor of Theorem \[thm:stability1\_vd\] is larger than that of Theorem \[thm:stability1\] by a factor that depends on the distribution of the local incoherence parameters $\{(\mu_k,\tilde{\mu}_k)\}_{k=1}^n$.

Let $W$ and $\widetilde{W}$ be defined in . Let $\nu$ and $\tilde{\nu}$ be defined in . Define $$\label{eq:defLambda}
\Lambda := \sqrt{\bar{\mu}} [\mbox{diag}(\nu)]^{-1}
\quad \mathrm{and} \quad
\widetilde{\Lambda} = \sqrt{\bar{\mu}} [\mbox{diag}(\tilde{\nu})]^{-1}.$$ Then $W = T \Lambda$ and is equivalent to $$\label{eq:ell1min_noisy_vd2}
\minimize_{g' \in \cz^n} \, \norm{W g'}_1
\quad \mathrm{subject~to} \quad \norm{S_{\Omega'} g' - S_{\Omega'} \Lambda^{-1} x^\sharp}_2 \leq \epsilon.$$

Let $\breve{x}$ denote the minimizer to . Then, the minimizer $\hat{x}$ to is represented as $\hat{x} = \Lambda \breve{x}$, i.e. $\breve{x} = \Lambda^{-1} \hat{x}$. By applying Theorem \[thm:stability1\] to , we obtain $$\label{eq:pf_thm_stability1_vd:bnd}
\begin{aligned}
\norm{T \hat{x} - T x}_2
{} & = \norm{W \breve{x} - W \Lambda^{-1} x}_2 \\
{} & \leq \left\{ 2 + 28 \sqrt{N} \left( 3 n \norm{T \Lambda}_{1 \to 2} \norm{\widetilde{\Lambda}^{-1} T^\dagger}_{2 \to \infty} + 1 \right) \right\} \epsilon \norm{W}.
\end{aligned}$$

The proof completes by applying the following inequalities to : $$\norm{\widetilde{\Lambda}^{-1} T^\dagger}_{2 \to \infty} \leq \norm{\widetilde{\Lambda}^{-1}} \norm{T^\dagger}_{2 \to \infty}
= \frac{\bar{\mu} \norm{T^\dagger}_{2 \to \infty}}{\min_{k \in [n]} \tilde{\mu}_k}$$ and $$\norm{T \Lambda}_{1 \to 2} \leq \norm{T}_{1 \to 2} \norm{\Lambda}
= \frac{\max_{k \in [n]} \mu_k \norm{T^\dagger}_{2 \to \infty}}{\bar{\mu}}.$$

\[thm:stability2\_vd\] Suppose $T: \cz^n \to \cz^N$ is injective. Suppose that $T$ and $\widetilde{T} = (T^\dagger)^*$ satisfy with parameters $\{\mu_k\}_{k=1}^n$, $\{\tilde{\mu}_k\}_{k=1}^n$, and $\gamma$. Let $\bar{\mu}$ be defined in . Let $\Omega = \{\omega_1, \ldots, \omega_m\}$ be a multi-set of random indices where $\omega_k$s are i.i.d. copies of a random variable $\omega$ with the distribution in . Let $\hat{x}$ be the minimizer to with $x^\sharp$ satisfying . Then there exist numerical constants $C, c > 0$ for which the following holds. With probability $1 - N^{-4}$, we have $$\norm{\hat{x} - x}_2 \leq
\frac{\sigma_{\max}(T)}{\sigma_{\min}(T)}
\cdot
\frac{\bar{\mu}}{\min_{k \in [n]} \tilde{\mu}_k}
\cdot
\left[ 14\sqrt{N} + \frac{n}{m} \left\{ \frac{\max_{k \in [n]} \mu_k}{\min_{k \in [n]} \tilde{\mu}_k} \cdot \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} (|\Omega|-|\Omega'|) +1 \right\} \right] \epsilon,$$ provided $$m \geq \frac{C \bar{\mu} s \log^4 N}{1 - \norm{\gamma T^* T - I_n}}.$$ Furthermore, if $T^* T = I_n$, then with probability $1 - N^{-4}$, $$\norm{\hat{x} - x}_2 \leq
\frac{\sigma_{\max}(T)}{\sigma_{\min}(T)}
\cdot
\frac{\bar{\mu}}{\min_{k \in [n]} \tilde{\mu}_k}
\cdot
\left( 14\sqrt{N} + \frac{n}{m} \cdot \frac{\max_{k \in [n]} \mu_k}{\min_{k \in [n]} \tilde{\mu}_k} \cdot R \right) \epsilon,$$ where $R$ is the count of the most repeated elements in $\Omega$.

Let $W$ and $\widetilde{W}$ be defined in . Let $\nu$ and $\tilde{\nu}$ be defined in . Let $\Lambda$ and $\widetilde{\Lambda}$ be defined in . In the proof of Theorem \[thm:stability1\_vd\], we have shown that is equivalent to . In the proof of Theorem \[thm:uniqueness\_vd\], we have shown that $W$ and $\widetilde{W}$ satisfy \[eq:incoW,eq:isoW\]. Therefore, applying Theorem \[thm:stability2\] to with incoherence parameter $\bar{\mu}$ completes the proof.

Extension to Group Sparsity Models {#sec:main_result_gs}
==================================

In Sections \[sec:main\_result\] and \[sec:main\_result\_vd\], we considered the sparsity model in a transform domain. In applications, the transform $T x$ exhibits additional structures – group sparsity. For example, in compressed sensing of 2D signals, the sparsifying transform $\Phi = [\Phi_1^\top, \Phi_2^\top]^\top$ can be the concatenation of the horizontal and vertical finite difference operators $\Phi_1$ and $\Phi_2$. Anisotropic total variation encourages the sparsity of $\Phi f$ [@krahmer2014stable]. On the other hand, one can choose isotropic total variation, assuming that $\Phi_1 f$ and $\Phi_2 f$ are jointly sparse (see the experiments section). For another example, in compressed sensing of color images or hyperspectral images, the sparse codes acquired from applying the analysis operator to different channels are usually assumed to be jointly sparse. To exploit such structures, we extend the results in the previous sections to group sparsity models in a transform domain. More specifically, we assume that the transform $T x$ of unknown signal $x$ via $T: \cz^n \to \cz^L$ is $(s,t)$ strongly group sparse in the following sense.

Let $\calG = \{\calG_1, \ldots, \calG_N\}$ be a partition of $[L]$, i.e. $\bigcup_{j \in [N]} \calG_j = [L]$ and $\calG_j \bigcap \calG_{j'} = \emptyset$ for $j \neq j'$. A vector $z \in \cz^L$ is $(s,t)$ strongly group sparse with respect to $\calG$ if there exists $J \subset [N]$ such that $$\supp{z} \subset \calG_J,
\quad
|\calG_J| \leq t,
\quad \mathrm{and} \quad
|J| \leq s,$$ where $\calG_J$ is defined by $$\calG_J := \bigcup_{j \in J} \calG_j.$$

An atomic norm for this group sparsity model is given by $$\tnorm{z}_{\calG,1} := \sum_{j \in [N]} \norm{\Pi_{\calG_j} z}_2.$$ The dual norm of $\tnorm{\cdot}_{\calG,1}$ is defined by $$\tnorm{z}_{\calG,\infty} := \sup_{\zeta \in \cz^L: \tnorm{\zeta}_{\calG,1} \leq 1} |\langle \zeta, z \rangle|,$$ which is equivalently rewritten as $$\tnorm{z}_{\calG,\infty} = \max_{j \in [N]} \norm{\Pi_{\calG_j} z}_2.$$

A subgradient $\tilde{z}$ of $\tnorm{\cdot}_{\calG,1}$ at $z$ is given by $$\label{eq:subgrad_mixed}
\Pi_{\calG_j} \tilde{z}
=
\begin{dcases}
\frac{\Pi_{\calG_j} z}{\norm{\Pi_{\calG_j} z}_2}, & \Pi_{\calG_j} z \neq 0, \\
0, & \mathrm{otherwise},
\end{dcases}
\qquad \forall j \in [N].$$

In a special case where $\calG_j = \{j\}$ for all $j \in [N]$, the strong group sparsity level reduces to the conventional sparsity model. The analogy between the two models is summarized in Table \[tab:replace\_notation\]. All the results in the previous section generalize to the strong group sparsity model according to this analogy. In the below, we state the extended results as Theorems, the proofs of which are obtained in a straightforward way by modifying the proofs of analogous theorems and lemmas for the usual sparsity model according to Table \[tab:replace\_notation\]. Thus, we do not repeat the proofs in this section. (The only exception is Lemma \[lemma:E3\] and we provide an analogous Lemma \[lemma:E3’\] in Section \[subsec:riplike\_lemmas\].)

[&gt;p[20ex]{}|C|C]{} & Sparsity Model & Group Sparsity Model\
$\mbox{dim}(R(T))$ & $N$ & $L = \sum_{j=1}^N |\calG_j|$\
& & $\gsupp{z} = \{ j :~ \Pi_{\calG_j} z \neq 0 \}$\
& & $\supp{z} = \bigcup_{j \in \gsupp{z}} \calG_j$\
group sparsity level & $\norm{z}_0 = |\supp{z}|$ & $\tnorm{z}_{\calG,0} = |\gsupp{z}|$\
total sparsity level & $\norm{z}_0 = |\supp{z}|$ & $\norm{z}_0 = |\supp{z}|$\
atomic norm & $\norm{z}_1 = \sum_{j=1}^N |\Pi_{\{j\}} z|$ & $\tnorm{\cdot}_{\calG,1} = \sum_{j=1}^N \norm{\Pi_{\calG_j} z}_2$\
dual norm & $\norm{\cdot}_\infty = \max_{j \in [N]} |\Pi_{\{j\}} z|$ & $\tnorm{\cdot}_{\calG,\infty} = \max_{j \in [N]} \norm{\Pi_{\calG_j} z}_2$\
subgradient & &\
of atomic norm & &\
incoherence & &\
parameter & &\
local incoherence & &\
parameters & &\

When $T x$ is strongly group sparse, we propose to estimate $T x$ by solving the following optimization problem, which generalizes : $$\label{eq:mixedmin}
\minimize_{g \in \cz^n} \, \tnorm{T g}_{\calG,1}
\quad \mathrm{subject~to} \quad S_\Omega g = S_\Omega x.$$ Then the following theorem, which is analogous to Theorem \[thm:uniqueness\], provides a performance guarantee for .

\[thm:uniqueness\_gs\] Let $\calG = \{\calG_1, \ldots, \calG_N\}$ be a partition of $[L]$. Suppose $T: \cz^n \to \cz^L$ is injective. Let $\mu_\calG$ be given by $$\label{eq:incoherence_gs}
\mu_\calG = \max_{k \in [n]} \max_{j \in [N]}
\max\left\{
n \norm{\gamma^{1/2} \Pi_{\calG_j} T e_k}_2^2,
n \norm{\gamma^{-1/2} \Pi_{\calG_j} \widetilde{T} e_k}_2^2
\right\},$$ where $\gamma$ is defined in from $T$ and $\widetilde{T} = (T^\dagger)^*$. Let $\Omega = \{\omega_1,\ldots,\omega_m\}$ be a multi-set of random indices where $\omega_k$s are i.i.d. following the uniform distribution on $[n]$. Suppose $T x$ is $(s,t)$ strongly group sparse with respect $\calG$. Then with probability $1 - e^{-\beta} - 3/n$, $x$ is the unique minimizer to provided $$\label{eq:samprate_gs}
m \geq \frac{C(1+\beta) \mu_\calG s}{1 - \norm{\gamma T^* T - I_n}} \left[ \log N
+ \log \left( \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} \right) \right].$$

Suppose that $\mu$ and $\mu_\calG$ are the smallest constants satisfying corresponding incoherence conditions. If $t = \ell s$ and $|\calG_j| = \ell$ for all $j \in [N]$, then $$\norm{\Pi_{\calG_j} T e_k}_2 \leq \sqrt{|\calG_j|} \norm{T e_k}_\infty, \quad \forall j \in [N], ~ \forall k \in [n].$$ Thus, we have $\mu_\calG \leq \ell \mu$ and a sufficient condition for is given by $$m \geq \frac{C(1+\beta) \mu t}{1 - \norm{\gamma T^* T - I_n}} \left[ \log N
+ \log \left( \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} \right) \right].$$ In other words, the sample complexity is proportional to the total sparsity level $t$ and there is no gain from the group structure. This inequality is tight if each $\Pi_{\calG_j} T e_k$ have nonzero elements of the same magnitude. Contrarily, if nonzero elements of each $\Pi_{\calG_j} T e_k$ vary a lot in their magnitudes, $\mu_\calG$ is smaller than $\ell \mu$ and there is gain from the group sparsity structure.

In the presence of noise to measurements, we generalize the optimization formulation for recovery in as follows: $$\label{eq:mixedmin_noisy}
\minimize_{g \in \cz^n} \, \tnorm{T g}_{\calG,1}
\quad \mathrm{subject~to} \quad \norm{S_{\Omega'} g - S_{\Omega'} x^\sharp}_2 \leq \epsilon.$$

The following theorem, analogous to Theorem \[thm:stability1\], provides a performance guarantee for .

\[thm:stability1\_gs\] Suppose the hypotheses of Theorem \[thm:uniqueness\_gs\] hold. Let $\hat{x}$ be the minimizer to with $x^\sharp$ satisfying $$\norm{S_{\Omega'} (x - x^\sharp)}_2 \leq \epsilon.$$ Then $$\norm{\hat{x} - x}_2 \leq
\frac{\sigma_{\max}(T)}{\sigma_{\min}(T)}
\cdot
\left\{ 2 + 28 \sqrt{N} \left( 3 n \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} + 1 \right) \right\} \epsilon.$$

The results for recovery using a variable density sampling designed from local incoherence parameters generalize in a similar way. We state the results in the following theorems.

\[thm:uniqueness\_vd\_gs\] Let $\calG = \{\calG_1, \ldots, \calG_N\}$ be a partition of $[L]$. Suppose $T: \cz^n \to \cz^N$ is injective. Let $\mu_{\calG,k}$ and $\tilde{\mu}_{\calG,k}$ be given by $$\label{eq:loc_incoherenceT_gs}
\mu_{\calG,k} = \max_{j \in [N]} n \norm{\gamma^{1/2} \Pi_{\calG_j} T e_k}_2^2
\quad \mathrm{and} \quad
\tilde{\mu}_{\calG,k} = \max_{j \in [N]} n \norm{\gamma^{-1/2} \Pi_{\calG_j} \widetilde{T} e_k}_2^2,$$ where $\gamma$ is defined in from $T$ and $\widetilde{T} = (T^\dagger)^*$. Let $\Omega = \{\omega_1, \ldots, \omega_m\}$ be a multi-set of random indices where $\omega_k$s are independent copies of a random variable $\omega$ with the following distribution: $$\label{eq:variable_density_gs}
\mathbb{P}(\omega = k) = \frac{\sqrt{\mu_{\calG,k} \tilde{\mu}_{\calG,k}}}{\sum_{j=1}^n \sqrt{\mu_{\calG,j} \tilde{\mu}_{\calG,j}}}, \quad \forall k \in [n].$$ Suppose $T x$ is $(s,t)$ strongly group sparse with respect $\calG$. Then with probability $1 - e^{-\beta} - 3/n$, $x$ is the unique minimizer to provided $$m \geq \frac{C(1+\beta) \bar{\mu}_\calG s}{1 - \norm{\gamma T^* T - I_n}} \left[ \log N
+ \log \left( \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} \right) \right],$$ where $\bar{\mu}$ is defined as $$\bar{\mu}_\calG := \frac{1}{n} \sum_{k=1}^n \sqrt{\mu_{\calG,k} \tilde{\mu}_{\calG,k}}.$$

\[thm:stability1\_vd\_gs\] Suppose the hypotheses of Theorem \[thm:uniqueness\_vd\_gs\] hold. Let $\hat{x}$ be the minimizer to with $x^\sharp$ satisfying $$\label{eq:xharp_fid_gs}
\norm{S_{\Omega'} x - S_{\Omega'} x^\sharp}_2 \leq \epsilon.$$ Then $$\norm{\hat{x} - x}_2 \leq
\frac{\sigma_{\max}(T)}{\sigma_{\min}(T)}
\cdot
\frac{\bar{\mu}_\calG}{\min_{k \in [n]} \tilde{\mu}_{\calG,k}}
\cdot
\left[ 2 + 28 \sqrt{N} \left( \frac{\max_{k \in [n]} \mu_{\calG,k}}{\min_{k \in [n]} \tilde{\mu}_{\calG,k}} \cdot 3 n \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} + 1 \right) \right] \epsilon.$$

Circulant Transforms {#sec:circulant}
====================

Many sparsifying transforms fall into the category of circulant transforms, including the identity transform. A block transform (e.g., block DCT), when applied to all overlapping patches of a signal (sliding window with stride $1$, including the wrap-around patches at the edges), is a union of circulant transforms applied to the signal [@pfister2015learning]. In this section, we consider only the case when the measurement matrix $\Psi\in\cz^{n\times n}$ is the DFT matrix, and compute the variable density sampling distribution for sparsity with respect to a circulant transform, and distribution for joint sparsity with respect to a union of circulant transforms. We show that, if the circulant transforms are injective, the distributions and correspond to the uniform distribution on $[n]$. On the other hand, some circulant transforms are not injective (e.g., the finite difference operator for 1D total variation or 2D isotropic total variation). Even in this case, we show that the “variable” density sampling distributions are a variation of the uniform distribution.

Injective Circulant Transforms
------------------------------

We say $\Phi\in \cz^{n\times n}$ is a circulant transform (circulant matrix), if $\Phi f = \phi \circledast f$ is the circular convolution of $f$ with some vector $\phi \in \cz^n$, i.e. the matrix representation of $\Phi$ is given by $$\label{eq:circulant}
\Phi = \begin{bmatrix}
\phi[1] & \phi[n] & \phi[n-1] & \cdots & \phi[2] \\
\phi[2] & \phi[1] & \phi[n] & \cdots & \phi[3] \\
\phi[3] & \phi[2] & \phi[1] & \cdots & \phi[4] \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
\phi[n] & \phi[n-1] & \phi[n-2] & \cdots & \phi[1] \\
\end{bmatrix}$$ The identity transform is a circulant transform with $\phi=e_1$.

By linearity and shift invariance of circular convolution, a circulant transform $\Phi$ can always be diagonalized by the DFT matrix $\Psi$: $$\label{eq:diagonalize}
\Phi = \Psi^* \diag(\lambda) \Psi.$$ where $\lambda = \sqrt{n}\Psi \phi$ is the (unnormalized) DFT of $\phi$. The same argument also applies to a 2D circulant transform (circulant block circulant matrix) and the 2D DFT matrix. To avoid verbosity, we use circulant transform $\Phi$ and DFT matrix $\Psi$ to denote both 1D and 2D transforms.

\[thm:circulant1\] For the DFT matrix $\Psi\in\cz^{n\times n}$ and an invertible circulant transform $\Phi\in\cz^{n\times n}$, the sampling density distribution is the uniform distribution on $[n]$.

By the diagonalization in , we have $$\begin{aligned}
& T = \Phi \Psi^\dagger = \Psi^* \diag(\lambda),\\
& \widetilde{T} = (T^\dagger)^* = \Psi^* \diag(\tilde{\lambda}),\end{aligned}$$ where $\tilde{\lambda}$ is the complex conjugate of the element-wise inverse of $\lambda$, i.e. $\tilde{\lambda}[k]=(\lambda[k]^*)^{-1}$. Then, the following choice of parameters $\mu_k$ and $\tilde{\mu}_k$ satisfy : $$\begin{aligned}
& \mu_k = n\gamma \norm{Te_k}_\infty^2 = n\gamma |\lambda[k]|^2 \norm{\Psi^*e_k}_\infty^2 = \gamma |\lambda[k]|^2,\\
& \tilde{\mu}_k = n\gamma^{-1} \norm{\widetilde{T}e_k}_\infty^2 = n\gamma^{-1} |\tilde{\lambda}[k]|^2 \norm{\Psi^*e_k}_\infty^2 = \gamma^{-1} |\lambda[k]|^{-2},\end{aligned}$$ where $\Psi^*e_k$ is the $k$th column of the discrete Fourier basis and has infinity norm $1/\sqrt{n}$. Therefore, $\mu_k\tilde{\mu}_k = 1$ for all $k\in [n]$, and the distribution in is $\mathbb{P}(\omega = k) = 1/n$, i.e. the uniform distribution on $[n]$.

Applying a sparsifying circulant transform to a signal is equivalent to passing the signal through a sparsifying filter. One may also pass the signal through a bank of sparsifying filters. The filter bank is equivalent to a union of circulant transforms, concatenated as $$\label{eq:concatenation}
\Phi = [\Phi_1^\transpose, \Phi_2^\transpose,\dots, \Phi_\ell^\transpose]^\transpose \in\cz^{L\times n},$$ where $L=\ell n$. For example, the patch transform sparsity model [@pfister2015learning] corresponds to this case. The 2D isotropic total variation model (see Section \[sec:TV\]), as another example, has an additional joint sparsity structure. For the latter example, let us consider a particular partition $\calG = \{\calG_1, \ldots, \calG_n\}$ given by $$\label{eq:partition}
\calG_k = \{(j-1)n+k\}_{j=1}^\ell, \qquad \forall k\in [n].$$ For group sparsity on this union of circulant transforms, we have a result similar to Theorem \[thm:circulant1\].

\[thm:circulant2\] For the DFT matrix $\Psi\in\cz^{n\times n}$, an injective transform $\Phi\in\cz^{L\times n}$ defined in , and the partition defined in , the sampling density distribution is the uniform distribution on $[n]$.

Similar to , we have the following factorization for the concatenated transform: $$\label{eq:diagonalize2}
\Phi = (I_\ell \otimes \Psi^*) [\diag(\lambda_1),\diag(\lambda_2),\dots, \diag(\lambda_\ell)]^\top \Psi,$$ where $\lambda_j$ is the (unnormalized) DFT of $\phi_j$, the convolution kernel of the $j$th cirulant transform $\Phi_j$. Hence $T$ and $\widetilde{T}$ are $$\begin{aligned}
& T = \Phi \Psi^\dagger = (I_\ell \otimes \Psi^*)[\diag(\lambda_1),\diag(\lambda_2),\dots, \diag(\lambda_\ell)]^\top,\\
& \widetilde{T} = (T^\dagger)^* = T(T^*T)^{-1} =  (I_\ell \otimes \Psi^*) [\diag(\tilde{\lambda}_1),\diag(\tilde{\lambda}_2),\dots, \diag(\tilde{\lambda}_\ell)]^\top,\end{aligned}$$ where $\tilde{\lambda}_j[k] = \lambda_j[k]/\bigl(\sum_{j'=1}^{\ell} |\lambda_{j'}[k]|^2\bigr)$. Then, $\mu_{\calG,k}$ and $\tilde{\mu}_{\calG,k}$ in are given respectively by $$\begin{aligned}
\mu_{\calG,k} & = n\gamma \max_{k'\in[n]}\norm{\Pi_{\calG_{k'}}Te_k}_2^2 \\
& = n\gamma \max_{k'\in[n]} \norm{\Pi_{\calG_{k'}}\bigl\{\bigl[\lambda_1[k],\lambda_2[k],\dots,\lambda_\ell[k]\bigr]^\transpose \otimes (\Psi^*e_k) \bigl\} }_2^2 \\
& = n\gamma \max_{k'\in[n]} |e_{k'}^\transpose \Psi^*e_k| \norm{\bigl[\lambda_1[k],\lambda_2[k],\dots,\lambda_\ell[k]\bigr]^\transpose}_2^2
= \gamma \bigl(\sum_{j=1}^{\ell} |\lambda_{j}[k]|^2\bigr)\end{aligned}$$ and $$\begin{aligned}
\tilde{\mu}_{\calG,k} & = n\gamma^{-1} \max_{k'\in[n]}\norm{\Pi_{\calG_{k'}}\widetilde{T}e_k}_2^2 \\
& = n\gamma^{-1} \max_{k'\in[n]} \norm{\Pi_{\calG_{k'}}\bigl\{\bigl[\tilde{\lambda}_1[k],\tilde{\lambda}_2[k],\dots,\tilde{\lambda}_\ell[k]\bigr]^\transpose \otimes (\Psi^*e_k) \bigl\} }_2^2 \\
& = \gamma^{-1} \bigl(\sum_{j=1}^{\ell} |\tilde{\lambda}_{j}[k]|^2\bigr)
= \gamma^{-1}  \bigl(\sum_{j=1}^{\ell} |\lambda_{j}[k]|^2\bigr)^{-1}.\end{aligned}$$ Therefore, $\mu_{\calG,k}\tilde{\mu}_{\calG,k} = 1$ for all $k\in [n]$, and the distribution in is $\mathbb{P}(\omega = k) = 1/n$, i.e. the uniform distribution on $[n]$.

Non-injective Circulant Transforms {#sec:TV}
----------------------------------

In this section, we consider non-injective circulant transforms, such as the finite difference operator for 1D total variation, or the union of vertical and horizontal finite difference operators for 2D isotropic total variation. Since the spectral responses of these transforms are zero at certain frequencies, they are invariant to changes in the corresponding frequency components. Therefore, unless these frequency components are sampled in the measurement, they cannot be recovered from $\ell_1$-norm minimization or mixed norm minimization . Assuming without loss of generality that the null frequencies are the first $n_0$ columns in $\Psi^*$ ($n_0<\min\{n,m\}$), we adopt the following two-step sampling scheme:

1.  Always sample indices $\omega_k = k$ for $k\in [n_0]$.

2.  Generate a multi-set of $m-n_0$ indices $\{\omega_{n_0+1},\omega_{n_0+2},\dots,\omega_m\}$, which are i.i.d. following a distribution on $\{n_0+1,n_0+2,\dots,n\}$.

We can compute the sampling density on $\{n_0+1,n_0+2,\dots,n\}$ based on and (or and ) by removing the zero columns in $T=\Phi\Psi^*$ (replacing $T$ with $T[e_{n_0+1},e_{n_0+2},\dots,e_{n}]$). Next, we state variations of Theorems \[thm:circulant1\] and \[thm:circulant2\] in these cases.

\[cor:circulant1\] Suppose circulant transform $\Phi$ in satisfies $\lambda[k] = 0$ for $k\in[n_0]$. Then the sampling density in Step 2), for $\ell_1$-norm minimization based on , is the uniform distribution on $\{n_0+1,n_0+2,\dots,n\}$.

\[cor:circulant2\] Suppose concatenated transform $\Phi$ in satisfies $\lambda_j[k] = 0$ for all $j\in[\ell]$ and $k\in[n_0]$. Then the sampling density in Step 2), for mixed norm minimization based on , is the uniform distribution on $\{n_0+1,n_0+2,\dots,n\}$.

These results are direct consequences of Theorems \[thm:circulant1\] and \[thm:circulant2\], whose proofs translate with no changes other than removing the zero columns in $T$ (the columns indexed by $[n_0]$).

Next, we specialize these results to total variation minimization. We define the 1D finite difference operator $\Phi_{\mathrm{TV},n}$ by , where $$\phi[k] = \begin{cases}
1 & k = 1\\
-1 & k = 2\\
0 & k\in\{3,4,\dots, n\}.
\end{cases}$$ Then $\norm{f}_{\mathrm{TV}} = \norm{\Phi_{\mathrm{TV},n} f}_1$ is the 1D total variation of $f$. Clearly, the circulant transform $\Phi_{\mathrm{TV},n}$ is not injective, since its null space contains the direct current (DC) component – $\Psi^*e_1$. By Corollary \[cor:circulant1\], we adopt the following sampling scheme for total variation minimization:

1.  Always sample index $\omega_1 = 1$.

2.  Generate a multi-set of $m-1$ indices $\{\omega_2,\omega_3,\dots,\omega_m\}$, which are i.i.d. following the uniform distribution on $\{2,3,\dots,n\}$.

Total variation is more commonly used for 2D signals (e.g., images). For a 2D signal $f$ of size $n_1\times n_2$, the finite difference operator is a concatenation of the vertical and horizontal finite difference operators: $$\Phi_{\mathrm{TV},n_1,n_2} = \begin{bmatrix}
I_{n_2} \otimes \Phi_{\mathrm{TV},n_1} \\
\Phi_{\mathrm{TV},n_2} \otimes I_{n_1}
\end{bmatrix}.$$ The anisotropic and isotropic total variations of $f$ are defined by $$\begin{aligned}
& \norm{f}_{\mathrm{TV, aniso}} = \norm{\Phi_{\mathrm{TV},n_1,n_2} f}_1,\\
& \norm{f}_{\mathrm{TV, iso}} = \tnorm{\Phi_{\mathrm{TV},n_1,n_2} f}_{\calG,1},\end{aligned}$$ where the partion $\calG=\{\calG_1,\dots,\calG_n\}$ is defined by for $\ell=2$ and $n=n_1n_2$. Let the measurement operator $\Psi$ be the 2D DFT on signals of size $n_1\times n_2$. Similar to the 1D case, the DC component $\Psi^* e_1$ belongs to the null space of $\Phi_{\mathrm{TV},n_1,n_2}$. By Corollary \[cor:circulant2\], we use the same two-step sampling scheme as in the 1D case.

Proof of Theorem \[thm:uniqueness\] {#sec:pf_main_result_noiseless}
===================================

In this section, we prove Theorem \[thm:uniqueness\], which provides a sufficient condition for exact recovery of sparse signals in a transform domain from noiseless observations. The proof of Theorem \[thm:uniqueness\] is based on the golfing scheme [@gross2011recovering], which was originally proposed for matrix completion [@gross2011recovering] and later adopted to compressed sensing [@candes2011probabilistic] and to structured matrix completion [@chen2014robust].

The golfing scheme constructs an inexact dual certificate. The notion of a dual certificate was originally proposed for compressed sensing (cf. [@candes2006near]). To reconstruct an $s$-sparse $f \in \cz^d$ from $b = A f$, it was proposed to estimate $f$ as the solution to $$\minimize_{\tilde{f} \in \cz^d} \, \norm{\tilde{f}}_1 \quad \mathrm{subject~to} \quad b = A \tilde{f}.$$ A dual certificate is a subgradient $v \in \cz^d$ of $\norm{\cdot}_1$ at $f$ such that $f$ is orthogonal to all null vectors of the sensing matrix $A$. In matrix completion, the objective function is replaced from the $\ell_1$-norm to the nuclear norm and the sensing matrix is replaced by a pointwise sampling operator. Gross [@gross2011recovering] proposed the clever golfing scheme that constructs an inexact dual certificate, which is close to the exact dual certificate, and showed a low-rank matrix is exactly reconstructed from partial entries sampled at a near optimal rate. Candes and Plan [@candes2011probabilistic] adopted the golfing scheme back to compressed sensing and showed that exact recovery is guaranteed from $m = O(s \log d)$ incoherent measurements, which improves on the previous performance guarantee with $m = O(s \log^4 d)$.

Chen and Chi [@chen2014robust] adopted the golfing scheme to structured matrix completion. Let $T: \cz^n \to \cz^{n_1 \times n_1}$ be a linear operator that maps a vector $x \in \cz^n$ to a structured matrix $T x \in \cz^{n_1 \times n_2}$ (e.g., a Hankel matrix). Chen and Chi [@chen2014robust] proposed to estimate $x$ by $$\minimize_{g \in \cz^n} \, \norm{T g}_* \quad \mathrm{subject~to} \quad S_\Omega g = S_\Omega x.$$ This can be interpreted as recovery of low-rank matrices in a special transform domain, where $T$ maps the standard basis vectors $\{e_1,\ldots,e_n\}$ to unit-norm matrices with disjoint supports. Unlike compressed sensing or matrix completion, in structured matrix completion, the dimension of the vector space where the unknown signal is rearranged as a structured low-rank matrix is larger than the dimension of the vector space where measurements are sampled. In other words, $T$ is a tall matrix and is not surjective. With this nontrivial difference, the conventional approaches [@gross2011recovering; @candes2011probabilistic] do not apply directly to structured matrix completion. Chen and Chi [@chen2014robust] cleverly modified the definition of an inexact dual certificate and the golfing scheme accordingly and provided performance guarantee at a near optimal sample complexity. We adopt their approach to recovery of sparse signals in a transform domain, where the nuclear norm is replaced by the $\ell_1$-norm[^4]. Notably, we extend the theory to the case where $T$ is not necessarily a unitary transform (e.g., $T^* T = I_n$), which is the case in various practical applications.

We first present the following lemma that extends the notion of an inexact dual certificate for recovery of sparse signals in a transform domain where the transform $T$ is not necessarily unitary.

\[lemma:uniqueness\] Suppose that $T: \cz^n \to \cz^N$ is injective. Let $J \subset [N]$ denote the support of $T x$, i.e. the elements of $J$ correspond to the locations of the nonzero elements in $T x$. Let $\Omega$ be a multi-set that consists of elements in $[n]$ with possible repetitions. Let $\Omega'$ denote the set of all distinct elements in $\Omega$. Suppose that $$\label{eq:local_isometry_rank_deficient}
\left\|
\frac{n}{m} \Pi_J T S_\Omega^* S_\Omega T^\dagger \Pi_J
- \Pi_J T T^\dagger \Pi_J
\right\|
\leq \frac{1}{2}.$$ If there exists a vector $v \in \cz^N$ satisfying $$\label{eq:dualcert_vanish}
(T T^\dagger - T S_{\Omega'}^* S_{\Omega'} T^\dagger)^* v = 0,$$ $$\label{eq:dualcert_sgn}
\norm{\Pi_J (v - \mbox{\upshape sgn}(T x))}_2 \leq \frac{1}{7 n \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty}},$$ and $$\label{eq:dualcert_bnd}
\norm{(I_N - \Pi_J) v}_\infty \leq \frac{1}{2},$$ then $x$ is the unique minimizer to (\[eq:ell1min\]).

See Section \[subsec:pf:lemma:uniqueness\].

The next lemma shows that such an inexact dual certificate exists with hight probability under the hypothesis of Theorem \[thm:uniqueness\].

\[lemma:existence\] Suppose the hypotheses of Theorem \[thm:uniqueness\] hold. Then, with probability $1 - e^{-\beta} - 1/n$, there exists a vector $v \in \cz^N$ satisfying \[eq:dualcert\_vanish,eq:dualcert\_sgn,eq:dualcert\_bnd\].

See Section \[subsec:pf:lemma:existence\].

Lemma \[lemma:existence\] together with Lemma \[lemma:uniqueness\] implies Theorem \[thm:uniqueness\]. Indeed, we only need to verify . By Lemma \[lemma:E1\], holds with probability at least $1 - 2/n$ provided that $m \geq 32 \mu s \max\{1/(1-\norm{T^* T - I_n}), 1/6\} \log n$. This completes the proof of Theorem \[thm:uniqueness\].

In the next section, we will introduce fundamental estimates that will be used in the proofs of Lemmas \[lemma:uniqueness\] and \[lemma:existence\].

Lemmas on fundamental estimates {#subsec:riplike_lemmas}
-------------------------------

The following lemmas provides estimates on various functions of the random matrix $T S_\Omega^* S_\Omega T^\dagger$, which are analogous to the corresponding estimates for RIPless compressed sensing [@candes2011probabilistic].

Similarly to RIPless compressed sensing, we also employ the notion of incoherence. In fact, our incoherence assumption in is analogous to a generalized version for anisotropic compressed sensing [@rudelson2013reconstruction; @lee2013oblique; @kueng2014ripless].

One important distinction from compressed sensing is that the *isotropy* property is not satisfied. Indeed, since the random indices in $\Omega$ are i.i.d. following the uniform distribution on $[n]$, the random matrix $T S_\Omega^* S_\Omega T^\dagger$ satisfies $$\frac{n}{m} \mathbb{E} T S_\Omega^* S_\Omega T^\dagger = T T^\dagger.$$ While $T T^\dagger$ is an orthogonal projection (idempotent and self-adjoint), it is not necessarily an identity operator. The rank-deficiency of $T T^\dagger$ requires new analysis in Lemmas \[lemma:uniqueness\] and \[lemma:existence\] compared to the previous results for compressed sensing with the canonical sparsity model [@candes2011probabilistic]. However, the fundamental estimates measure the deviations of functions of $T S_\Omega^* S_\Omega T^\dagger$ from their expectations and do not require the isotropy property ($T^* T = I_n$). We present the following lemmas for the fundamental estimates, whose proofs are deferred to the appendix.

\[lemma:E1\] Suppose $T: \cz^n \to \cz^N$ and $\widetilde{T} = (T^\dagger)^*$ satisfy with parameter $\mu$. Let $\gamma$ be defined in . Let $J$ be a fixed subset of $[N]$ satisfying $|J| = s$. Let $\Omega = \{\omega_1,\ldots,\omega_m\}$ where $\omega_j$s are i.i.d. following the uniform distribution on $[n]$. Then for $\delta > 0$, $$\mathbb{P}\left(\left\| \Pi_J \left(\frac{n}{m} T S_\Omega^* S_\Omega T^\dagger - T T^\dagger \right) \Pi_J \right\| \geq \delta\right)
\leq 2s \exp\left( -\frac{m}{s\mu} \cdot \frac{\delta^2/2}{1/(1-\norm{\gamma T^* T - I_n})+\delta/3} \right).$$

See Appendix \[sec:pf:lemma:E1\].

\[lemma:E2\] Suppose $T: \cz^n \to \cz^N$ and $\widetilde{T} = (T^\dagger)^*$ satisfy with parameter $\mu$. Let $\gamma$ be defined in . Let $q \in \cz^N$ be a fixed vector. Let $J$ be a fixed subset of $[N]$ satisfying $|J| = s$. Let $\Omega = \{\omega_1,\ldots,\omega_m\}$ where $\omega_j$s are i.i.d. following the uniform distribution on $[n]$. Then for each $t \leq 1/2$, $$\mathbb{P}\left(\left\|\Pi_J \left(\frac{n}{m} T S_\Omega^* S_\Omega T^\dagger - T T^\dagger \right) \Pi_J q\right\|_2 \geq t \norm{\Pi_J q}_2\right)
\leq \exp\left\{ -\frac{1}{4} \left( t \sqrt{\frac{m(1-\norm{\gamma T^* T - I_n})}{s\mu}} - 1 \right)^2 \right\}.$$

See Appendix \[sec:pf:lemma:E2\].

\[lemma:E3\] Suppose $T: \cz^n \to \cz^N$ and $\widetilde{T} = (T^\dagger)^*$ satisfy with parameter $\mu$. Let $\gamma$ be defined in . Let $q \in \cz^N$ be a fixed vector. Let $J$ be a fixed subset of $[N]$ satisfying $|J| = s$. Let $\Omega = \{\omega_1,\ldots,\omega_m\}$ where $\omega_j$s are i.i.d. following the uniform distribution on $[n]$. Then for each $t > 0$, $$\begin{aligned}
{} & \mathbb{P}\left(\left\|\Pi_{[N] \setminus J} \left( \frac{n}{m} \widetilde{T} S_\Omega^* S_\Omega T^* - \widetilde{T} T^* \right) \Pi_J q\right\|_\infty \geq t \norm{\Pi_J q}_2\right) \\
{} & \quad \leq 2N \exp\left( - \frac{m}{2\mu} \cdot \frac{t^2}{1/(1-\norm{\gamma T^* T - I_n}) + \sqrt{s}t/3} \right).\end{aligned}$$

See Appendix \[sec:pf:lemma:E3\].

\[lemma:E3’\] Suppose $T: \cz^n \to \cz^L$ and $\widetilde{T} = (T^\dagger)^*$ satisfy with parameter $\mu$. Let $\gamma$ be defined in . Let $q \in \cz^L$ be a fixed vector. Let $\calG = \{\calG_1, \ldots, \calG_N\}$ be a partition of $[L]$. Let $J$ be a fixed subset of $[N]$ satisfying $|J| = s$. Let $\calG_J = \bigcup_{j \in J} \calG_j$. Let $\Omega = \{\omega_1,\ldots,\omega_m\}$ where $\omega_j$s are i.i.d. following the uniform distribution on $[n]$. Then for each $t > 0$, $$\begin{aligned}
{} & \mathbb{P}\left( \left\|\Pi_{[L] \setminus \calG_J} \left( \frac{n}{m} \widetilde{T} S_\Omega^* S_\Omega T^* - \widetilde{T} T^* \right) \Pi_{\calG_J} q\right\|_{\calG,\infty} \geq t \norm{\Pi_{\calG_J} q}_2\right) \\
{} & \quad \leq 2 \max_{j \in [N]} |\calG_j| N \exp\left( - \frac{m}{2\mu} \cdot \frac{t^2}{1/(1-\norm{\gamma T^* T - I_n}) + \sqrt{s}t/3} \right).\end{aligned}$$

See Appendix \[sec:pf:lemma:E3’\].

Proof of Lemma \[lemma:uniqueness\] {#subsec:pf:lemma:uniqueness}
-----------------------------------

Our proof essentially adapts the arguments of Chen and Chi [@chen2014robust Appendix B] for the structured low-rank matrix completion problem. There are two key differences in the two proofs. First, the $\ell_1$-norm replaces the nuclear norm. Second, $T$ is a general injective transform, which is not necessarily unitary. These differences require nontrivial modifications of crucial steps in the proof. Furthermore, the upper bound on the deviation of $v$ from $\mbox{sgn}(T x)$ in is sharpened by optimizing parameters. This improvement also applies to the previous work [@chen2014robust].

Let $\hat{x} = x + h$ be the minimizer to (\[eq:ell1min\]). We show that $T h = 0$ in two complementary cases. Then by the injectivity of $T$, $h = 0$, or equivalently, $\hat{x} = x$.

**Case 1:** We first consider the case when $h$ satisfies $$\label{eq:case1}
\norm{\Pi_J T h}_2 \leq 3 n \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} \norm{\Pi_{[N] \setminus J} T h}_2.$$

Since $\mbox{sgn}(\Pi_{[N] \setminus J} T h)$ and $\mbox{sgn}(T x)$ have disjoint supports, it follows that $\mbox{sgn}(T x) + \mbox{sgn}(\Pi_{[N] \setminus J} T h)$ and $\mbox{sgn}(T x)$ coincide on $J$. Furthermore, $\norm{\mbox{sgn}(T x) + \mbox{sgn}(\Pi_{[N] \setminus J} T h)}_\infty \leq 1$. Therefore, $\mbox{sgn}(T x) + \mbox{sgn}(\Pi_{[N] \setminus J} T h)$ is a valid sub-gradient of the $\ell_1$-norm at $T x$. Then it follows that $$\label{eq:pf_lemma_uniqueness:ineq1}
\begin{aligned}
\norm{T x + T h}_1
{} & \geq \norm{T x}_1 + \langle \mbox{sgn}(T x) + \mbox{sgn}(\Pi_{[N] \setminus J} T h), ~ Th \rangle \\
{} & = \norm{T x}_1
+ \langle v, T h \rangle
+ \langle \mbox{sgn}(\Pi_{[N] \setminus J} T h), ~ Th \rangle
- \langle v - \mbox{sgn}(T x), Th \rangle.
\end{aligned}$$

In fact, $\langle v, T h \rangle  = 0$ as shown below. The inner product of $T h$ and $v$ is decomposed as $$\label{eq:pf_lemma_uniqueness:ip}
\langle v, Th \rangle
= \langle v, (I_N - T T^\dagger) Th) \rangle
+ \langle v, (T T^\dagger - T S_{\Omega'}^* S_{\Omega'} T^\dagger) Th \rangle
+ \langle v, T S_{\Omega'}^* S_{\Omega'} T^\dagger Th \rangle.$$ Indeed, all three terms in the right-hand side of are 0. Since $T T^\dagger$ is the orthogonal projection onto the range space of $T$, the first term is 0. The second term is 0 by the assumption on $v$ in . Since $\hat{x}$ is feasible for , $S_\Omega \hat{x} = S_\Omega x$. Thus $S_\Omega h = S_\Omega (\hat{x} - x) = 0$, i.e. $e_\omega^* h = 0$ for all $\omega \in \Omega$, which also implies $S_{\Omega'} h = 0$. Then it follows that $S_{\Omega'} T^\dagger T h = S_{\Omega'} h = 0$. Thus the third term of the right-hand side of is 0.

Since the $\mbox{sgn}(\cdot)$ operator commutes with $\Pi_{[N] \setminus J}$ and $\Pi_{[N] \setminus J}$ is idempotent, we get $$\begin{aligned}
\langle \mbox{sgn}(\Pi_{[N] \setminus J} T h), ~ T h \rangle
{} & = \langle \Pi_{[N] \setminus J} \mbox{sgn}(\Pi_{[N] \setminus J} T h), ~ T h \rangle \\
{} & = \langle \mbox{sgn}(\Pi_{[N] \setminus J} T h), ~ \Pi_{[N] \setminus J} T h \rangle \\
{} & = \norm{\Pi_{[N] \setminus J} T h}_1.\end{aligned}$$

Then implies $$\label{eq:pf_lemma_uniqueness:ineq2}
\norm{T x + T h}_1 \geq \norm{T x}_1 + \norm{\Pi_{[N] \setminus J} T h}_1 - \langle v - \mbox{sgn}(T x), Th \rangle.$$

We derive an upper bound on the magnitude of the last term in the right-hand side of given by

\[eq:pf\_lemma\_uniqueness:ineq3\] $$\begin{aligned}
| \langle v - \mbox{sgn}(T x), Th \rangle |
{} & = | \langle \Pi_J (v - \mbox{sgn}(T x)), Th \rangle + \langle \Pi_{[N] \setminus J} (v - \mbox{sgn}(T x)), Th \rangle | \nonumber \\
{} & \leq | \langle \Pi_J (v - \mbox{sgn}(T x)), Th \rangle | + | \langle \Pi_{[N] \setminus J} v, Th \rangle | \label{eq:pf_lemma_uniqueness:ineq3a} \\
{} & \leq \norm{\Pi_J (v - \mbox{sgn}(T x))}_2 \norm{\Pi_J Th}_2
+ \norm{\Pi_{[N] \setminus J} v}_\infty \norm{\Pi_{[N] \setminus J} T h}_1 \label{eq:pf_lemma_uniqueness:ineq3b} \\
{} & \leq \frac{1}{7 n \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty}} \norm{\Pi_J Th}_2 + \frac{1}{2} \norm{\Pi_{[N] \setminus J} T h}_1, \label{eq:pf_lemma_uniqueness:ineq3c}\end{aligned}$$

where holds by the triangle inequality and the fact that $T x$ is supported on $J$; by Hölder’s inequality; by the assumptions on $v$ in and .

We continue by applying to and get $$\begin{aligned}
\norm{T x + T h}_1
{} & \geq \norm{T x}_1 - \frac{1}{7 n \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty}} \norm{\Pi_J Th}_2 + \frac{1}{2} \norm{\Pi_{[N] \setminus J} T h}_1 \\
{} & \geq \norm{T x}_1 - \frac{3}{7} \norm{\Pi_{[N] \setminus J} T h}_2 + \frac{1}{2} \norm{\Pi_{[N] \setminus J} T h}_2 \\
{} & = \norm{T x}_1 + \frac{1}{14} \norm{\Pi_{[N] \setminus J} T h}_2,\end{aligned}$$ where the second step follows from .

Then, $\norm{T \hat{x}}_1 \geq \norm{T x}_1 \geq \norm{T \hat{x}}_1$, which implies $\Pi_{[N] \setminus J} T h = 0$. By (\[eq:case1\]), we also have $\Pi_J T h = 0$. Therefore, it follows that $T h = 0$.

**Case 2:** Next, we consider the complementary case when $h$ satisfies $$\label{eq:case2}
\norm{\Pi_J T h}_2 > 3 n \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} \norm{\Pi_{[N] \setminus J} T h}_2.$$

In the previous case, we have shown that $S_\Omega h = 0$. Thus $S_\Omega T^\dagger T h = 0$. Then together with $(I_N - T T^\dagger) T = 0$, we get $$\begin{aligned}
\left( \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger + I_N - T T^\dagger \right) T h = 0,\end{aligned}$$ which implies $$\label{eq:pf_lemma_uniqueness:ineq4}
\begin{aligned}
0 {} & \geq \left\langle \Pi_J T h, \left( \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger + I_N - T T^\dagger \right) T h \right\rangle \\
{} & = \left\langle \Pi_J T h, \left( \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger + I_N - T T^\dagger \right) \Pi_J T h \right\rangle \\
{} & \quad + \left\langle \Pi_J T h, \left( \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger + I_N - T T^\dagger \right) \Pi_{[N] \setminus J} T h \right\rangle.
\end{aligned}$$

The magnitude of the first term in the right-hand side of is lower-bounded by $$\label{eq:pf_lemma_uniqueness:lb}
\begin{aligned}
{} & \left| \left\langle \Pi_J T h, \left( \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger + I_N - T T^\dagger \right) \Pi_J T h \right\rangle \right| \\
{} & = \left| \langle \Pi_J T h, \Pi_J T h \rangle \right|
- \left| \left\langle \Pi_J T h, \left( T T^\dagger - \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger \right) \Pi_J T h \right\rangle \right| \\
{} & \geq \norm{\Pi_J T h}_2^2 - \left\|\Pi_J T T^\dagger \Pi_J - \frac{n}{m} \Pi_J T S_\Omega^* S_\Omega T^\dagger \Pi_J\right\| \norm{\Pi_J T h}_2^2 \\
{} & \geq \frac{1}{2} \norm{\Pi_J T h}_2^2,
\end{aligned}$$ where the last step follows from the assumption in .

Next, we derive an upper bound on the second term in the right-hand side of . To this end, we first computes the operator norm of $T e_k e_k^* T^\dagger$ for $k \in [n]$. In fact, $\norm{T e_k e_k^* T^\dagger} = \norm{T e_k}_2 \norm{\widetilde{T} e_k}_2$, where $\widetilde{T}$ is the adjoint of $T^\dagger$. Therefore, we only need to compute $\norm{T e_k}_2$ and $\norm{\widetilde{T} e_k}_2$. First, $\norm{T e_k}_2$ is upper-bounded by $$\begin{aligned}
\max_{k \in [n]} \norm{T e_k}_2 = \norm{T}_{1 \to 2}.\end{aligned}$$ On the other hand, $\norm{\widetilde{T} e_k}_2$ is upper-bounded by $$\begin{aligned}
\max_{k \in [n]} \norm{\widetilde{T} e_k}_2
= \norm{\widetilde{T}}_{1 \to 2} = \norm{T^\dagger}_{2 \to \infty},\end{aligned}$$ where the last step holds since $\widetilde{T}$ is the adjoint operator of $T^\dagger$ and $\ell_\infty^n$ is the dual space of $\ell_1^n$. By the above upper bounds on $\norm{T e_k}_2$ and $\norm{\widetilde{T} e_k}_2$, we get $$\begin{aligned}
\norm{T e_k e_k^* T^\dagger} \leq \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty}.\end{aligned}$$ Then the operator norm of $ \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger + I_N - T T^\dagger $ is upper-bounded by $$\label{eq:pf_lemma_uniqueness:ineq5}
\begin{aligned}
\left\|  \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger + I_N - T T^\dagger  \right\|
{} & \leq \frac{n}{m} \left( \norm{T e_{\omega_1} e_{\omega_1}^* T^\dagger + I_N - T T^\dagger} + \sum_{j=2}^m \norm{T e_{\omega_j} e_{\omega_j}^* T^\dagger}_2 \right) \\
{} & \leq \frac{n}{m} \left( \max(\norm{T e_{\omega_1} e_{\omega_1}^* T^\dagger}, \norm{I_N - T T^\dagger}) + \sum_{j=2}^m \norm{T e_{\omega_j} e_{\omega_j}^* T^\dagger}_2 \right) \\
{} & \leq n \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty},
\end{aligned}$$ where the second step follows since $(T e_{\omega_1} e_{\omega_1}^* T^\dagger)^*(I_N - T T^\dagger) = 0$ and $(I_N - T T^\dagger) (T e_{\omega_1} e_{\omega_1}^* T^\dagger)^* = 0$. The second term in the right-hand side of is then upper-bounded by $$\label{eq:pf_lemma_uniqueness:ub}
\begin{aligned}
{} & \left| \left\langle \Pi_J T h, \left( \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger + I_N - T T^\dagger \right) \Pi_{[N] \setminus J} T h \right\rangle \right| \\
{} & \leq \left\|  \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger + I_N - T T^\dagger  \right\| \norm{\Pi_J T h}_2 \norm{\Pi_{[N] \setminus J} T h}_2 \\
{} & \leq n \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} \norm{\Pi_J T h}_2 \norm{\Pi_{[N] \setminus J} T h}_2,
\end{aligned}$$ where the last step follows from .

Applying and to provides $$\begin{aligned}
0 {} & \geq \left| \left\langle \Pi_J T h, \left( \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger + I_N - T T^\dagger \right) \Pi_J T h \right\rangle \right| \\
{} & \quad - \left| \left\langle \Pi_J T h, \left( \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger + I_N - T T^\dagger \right) \Pi_{[N] \setminus J} T h \right\rangle \right| \\
{} & \geq \frac{1}{2} \norm{\Pi_J T h}_2^2 - n \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} \norm{\Pi_J T h}_2 \norm{\Pi_{[N] \setminus J} T h}_2 \\
{} & \geq \frac{1}{2} \norm{\Pi_J T h}_2^2 - \frac{1}{3} \norm{\Pi_J T h}_2^2 \\
{} & = \frac{1}{6} \norm{\Pi_J T h}_2^2 \geq 0,\end{aligned}$$ where the second inequality follows from . Then it is implied that $\Pi_J T h = 0$. By (\[eq:case2\]), we also have $\Pi_{[N] \setminus J} T h = 0$. Therefore, $T h = 0$, which completes the proof.

Proof of Lemma \[lemma:existence\] {#subsec:pf:lemma:existence}
----------------------------------

We construct a dual certificate $v$ using a golfing scheme. Since the isotropy is not satisfied, the original golfing scheme needs to be modified accordingly. We adopt the version for structured matrix completion [@chen2014robust].

Recall that the elements of $\Omega = \{\omega_1, \ldots, \omega_m\}$ are i.i.d. following the uniform distribution on $[n]$. We partition the multi-set $\Omega$ into $\ell$ multi-sets so that $\Omega_1$ consists of the first $m_1$ elements of $\Omega$, $\Omega_2$ consists of the next $m_2$ elements of $\Omega$, and so on, where $\sum_{i=1}^\ell m_i = m$. Then, $\Omega_i$s are mutually independent and each $\Omega_i$ consists of i.i.d. random indices.

The version of the golfing scheme in this paper generates a dual certificate $v \in \cz^N$ from intermediate vectors $q_i \in \cz^N$ for $i=0,\ldots,\ell-1$ by $$v = \sum_{i=1}^\ell \left(\frac{n}{m_i} \widetilde{T} S_{\Omega_i}^* S_{\Omega_i} T^* + I_N - T T^\dagger \right) q_{i-1},$$ where $q_i$s are generated as follows: first, initialize $q_0 = \mbox{sgn}(T x)$; next, generate $q_i$s recursively by $$q_i = \Pi_J \left( \widetilde{T} T^* - \frac{n}{m_i} \widetilde{T} S_{\Omega_i}^* S_{\Omega_i} T^* \right) q_{i-1}, \quad i = 1,\ldots,\ell-1.$$ Here, $\widetilde{T}$ denotes the adjoint of $T^\dagger$.

Note that $$\begin{aligned}
{} & (T T^\dagger - T S_{\Omega'}^* S_{\Omega'} T^\dagger)^*
\left( \frac{n}{m_i} \widetilde{T} S_{\Omega_i}^* S_{\Omega_i} T^* + I_N - \widetilde{T} T^* \right) \\
{} & = \frac{n}{m_i} (T T^\dagger - T S_{\Omega'}^* S_{\Omega'} T^\dagger)^* \widetilde{T} S_{\Omega_i}^* S_{\Omega_i} T^*
+ (T T^\dagger - T S_{\Omega'}^* S_{\Omega'} T^\dagger)^* (I_N - \widetilde{T} T^*) \\
{} & = \frac{n}{m_i} (\widetilde{T} T^* - \widetilde{T} S_{\Omega'}^* S_{\Omega'} T^*) \widetilde{T} S_{\Omega_i}^* S_{\Omega_i} T^*
+ (\widetilde{T} T^* - \widetilde{T} S_{\Omega'}^* S_{\Omega'} T^*) (I_N - \widetilde{T} T^*) = 0.\end{aligned}$$ Thus it follows that $v$ satisfies .

The rest of the proof is devoted to show that $v$ satisfies and , which follows similarly to the proof of [@candes2011probabilistic Lemma 3.3]. For completeness, we verify that the arguments in [@candes2011probabilistic] are valid in our setting (with neither isotropy nor self-adjointness).

We show that $q_i$ satisfies the following two properties with high probability for each $i \in [\ell]$: first, $$\label{eq:decay_qi}
\norm{q_i}_2 \leq c_i \norm{q_{i-1}}_2$$ and, second, $$\label{eq:bnd_qi_infty}
\left\| \Pi_{[N] \setminus J} \left(\frac{n}{m_i} \widetilde{T} S_{\Omega_i}^* S_{\Omega_i} T^* + I_N - \widetilde{T} T^* \right) q_{i-1} \right\|_\infty \leq t_i \norm{q_{i-1}}_2.$$

Let $p_1(i)$ (resp. $p_2(i)$) denote the probability that the inequality in (resp. ) does not hold. Since $q_{i-1}$ is independent of $\Omega_i$, by Lemma \[lemma:E2\], $p_1(i)$ is upper-bounded by $$p_1(i) \leq \exp\left( - \frac{1}{4}(c_i \sqrt{m_i(1-\norm{\gamma T^* T - I_n})/(s\mu)}-1)^2 \right).$$ Therefore, $p_1(i) \leq \frac{1}{\alpha} e^{-\beta}$ if $$\label{eq:bndmi_p1}
m_i \geq \frac{2+8(\beta + \log \alpha)}{c_i^2} \cdot \frac{\mu s}{1-\norm{\gamma T^* T - I_n}}.$$ On the other hand, note that $q_{i-1} = \Pi_J q_{i-1}$. Then it follows that $$\begin{aligned}
\left\| \Pi_{[N] \setminus J} \left(\frac{n}{m_i} \widetilde{T} S_{\Omega_i}^* S_{\Omega_i} T^* + I_N - \widetilde{T} T^* \right) q_{i-1} \right\|_\infty
{} & = \left\| \Pi_{[N] \setminus J} \left(\frac{n}{m_i} \widetilde{T} S_{\Omega_i}^* S_{\Omega_i} T^* + I_N - \widetilde{T} T^* \right) \Pi_J q_{i-1} \right\|_\infty \\
{} & = \left\| \Pi_{[N] \setminus J} \left(\frac{n}{m_i} \widetilde{T} S_{\Omega_i}^* S_{\Omega_i} T^* - \widetilde{T} T^* \right) \Pi_J q_{i-1} \right\|_\infty.\end{aligned}$$ Again, we use the fact that $q_{i-1}$ is independent of $\Omega_i$. Then, by Lemma \[lemma:E3\], $p_2(i)$ is upper-bounded by $$p_2(i) \leq 2N \exp\left( - \frac{3t_i^2 m_i}{6\mu/(1-\norm{\gamma T^* T - I_n}) + 2 \mu \sqrt{s} t_i} \right).$$ Therefore, $p_2(i) \leq \frac{1}{\alpha} e^{-\beta}$ if $$\label{eq:bndmi_p2}
m_i \geq \left( \frac{2}{t_i^2 s (1-\norm{\gamma T^* T - I_n})} + \frac{2}{3t_i\sqrt{s}} \right) (\beta + \log(2\alpha) + \log N) s\mu.$$

We set the parameters similarly to the proof of [@candes2011probabilistic Lemma 3.3] as follows: $$\label{eq:param}
\begin{aligned}
\ell {} & = \left\lceil \frac{\log_2 s}{2} + \log_2 n
+ \log_2 \left( \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} \right) \right\rceil + 3, \\
c_i {} & =
\begin{cases}
1/\lceil 2 \sqrt{\log N} ~ \rceil & i=1,2,3, \\
1/2 & 3 \leq i \leq \ell,
\end{cases} \\
t_i {} & =
\begin{cases}
1/\lceil 4 \sqrt{s} ~\rceil & i=1,2,3, \\
\log N / \lceil 4 \sqrt{s} ~\rceil & 3 \leq i \leq \ell,
\end{cases}\\
m_i {} & = \lceil 10(1+\log 6+\beta) \mu s c_i^{-2} \rceil, \quad \forall i. \\
\end{aligned}$$ By the construction of $v$, we have $$\begin{aligned}
\Pi_J v {} & = \sum_{i=1}^\ell \Pi_J \left(\frac{n}{m_i} \widetilde{T} S_{\Omega_i}^* S_{\Omega_i} T^* + I_N - \widetilde{T} T^* \right) q_{i-1} \\
{} & = \sum_{i=1}^\ell \left[ \Pi_J q_{i-1} - \Pi_J \left(\widetilde{T} T^* - \frac{n}{m_i} \widetilde{T} S_{\Omega_i}^* S_{\Omega_i} T^* \right) q_{i-1} \right] \\
{} & = \sum_{i=1}^\ell \left( q_{i-1} - q_i \right)
= q_0 - q_\ell \\
{} & = \mbox{sgn}(T x) - q_\ell = \Pi_J \mbox{sgn}(T x) - q_\ell.\end{aligned}$$ Therefore, implies $$\norm{\Pi_J (v - \mbox{sgn}(T x))}_2
= \norm{q_\ell}_2
\leq \prod_{i=1}^\ell c_i \norm{\mbox{sgn}(T x)}_2
\leq \frac{\sqrt{s}}{2^\ell \log N}.$$

Next, by and , we have $$\label{eq:dualcert_bnd_proof}
\begin{aligned}
\norm{\Pi_{[N] \setminus J} v}_\infty
{} & \leq \sum_{i=1}^\ell \left\| \Pi_{[N] \setminus J} \left(\frac{n}{m_i} \widetilde{T} S_{\Omega_i}^* S_{\Omega_i} T^* + I_N - \widetilde{T} T^* \right) q_{i-1} \right\|_\infty \\
{} & \leq \sum_{i=1}^\ell t_i \norm{q_{i-1}}_2 \\
{} & \leq \sqrt{s} \left(t_1 + \sum_{i=2}^\ell t_i \prod_{j=1}^{i-1} c_j\right).
\end{aligned}$$ By setting parameters as in , the right-hand side in is further upper-bounded by $$\frac{1}{4} \left( 1 + \frac{1}{2\sqrt{\log N}} + \frac{\log N}{4 \log N} + \cdots \right) < \frac{1}{2}.$$ Then, we have shown that $v$ satisfies .

It remains to show that and hold with the desired probability. From and , it follows that $$p_j(i) \leq \frac{1}{6} e^{-\beta}, \quad \forall i \in [\ell], ~ \forall j=1,2.$$ In particular, we have $$\sum_{j=1}^2 \sum_{i=1}^3 p_j(i) \leq e^{-\beta}.$$ This implies that the first three $\Omega_i$s satisfy and except with probability $e^{-\beta}$.

On the other hand, we also have $$p_1(i) + p_2(i) < \frac{1}{3}, \quad \forall i = 4,\ldots,\ell.$$ In other words, the probability that $\Omega_i$ satisfies and is at least $2/3$. The union bound doesn’t show that $\Omega_i$ satisfies and for all $i \geq 4$ with the desired probability.

As in the proof of [@candes2011probabilistic Lemma 3.3], we adopt the oversampling and refinement strategy by Gross [@gross2011recovering]. Recall that each random index set $\Omega_i$ consists of i.i.d. random indices following the uniform distribution on $[n]$. Thus $\Omega_i$s are mutually independent. In particular, we set $\Omega_i$s are of the same cardinality in . Therefore, $\Omega_i$s are i.i.d. random variables. We generate a few extra copies of $\Omega_i$ for $i = \ell+1,\ldots,\ell'+3$ where $\ell' = 3(\ell-3)$. Then, by Hoeffding’s inequality, there exist at least $\ell-3$ $\Omega_i$s for $i \geq 4$ that satisfy and with probability $1 - 1/n$. (We refer more technical details for this step to [@candes2011probabilistic Section III.B].) Therefore, there are $\ell$ good $\Omega_i$s satisfying and with probability $1 - e^{-\beta} - 1/n$, and the dual certificate $v$ is constructed from these good $\Omega_i$s. The total number of samples for this construction requires $$m \geq \frac{40(1+\log 6 +\beta)\mu s (3\log N + 3\ell)}{1 - \norm{\gamma T^* T - I_n}},$$ which can be simplified as $$m \geq \frac{C(1+\beta) \mu s}{1 - \norm{\gamma T^* T - I_n}} \left[ \log N
+ \log \left( \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} \right) \right]$$ for a numerical constant $C$.

Proofs for Theorems \[thm:stability1\] and \[thm:stability2\] {#sec:pf_main_result_noisy}
=============================================================

In this section, we prove Theorems \[thm:stability1\] and \[thm:stability2\], which provide sufficient conditions for stable recovery of sparse signals in a transform domain from noisy data.

Proof of Theorem \[thm:stability1\] {#subsec:pf:thm:stability1}
-----------------------------------

Let $h := \hat{x} - x$. Since $\hat{x}$ is the minimizer to , it follows that $$\label{eq:pf_thm_stability:bnd1}
\begin{aligned}
\norm{T x}_1
{} & \geq \norm{T \hat{x}}_1 = \norm{T x + T h}_1 \\
{} & \geq \norm{T x + T (I_n - S_{\Omega'}^* S_{\Omega'}) h}_1 - \norm{T S_{\Omega'}^* S_{\Omega'} h}_1.
\end{aligned}$$

Since $x$ and $\hat{x}$ are feasible for , it follows that $$\label{eq:noisy_feas}
\begin{aligned}
{} & \max\left( \norm{T S_{\Omega'}^* S_{\Omega'} (\hat{x} - x^\sharp)}_2, ~ \norm{T S_{\Omega'}^* S_{\Omega'} (x - x^\sharp)}_2 \right) \\
{} & \leq \norm{T} \max\left( \norm{S_{\Omega'} (\hat{x} - x^\sharp)}_2, ~ \norm{S_{\Omega'} (x - x^\sharp)}_2 \right) \leq \epsilon \norm{T}.
\end{aligned}$$ Therefore, by the triangle inequality, we have $$\label{eq:tube_cstr}
\norm{T S_{\Omega'}^* S_{\Omega'} h}_2 = \norm{T S_{\Omega'}^* S_{\Omega'} (\hat{x} - x)}_2
\leq \norm{T S_{\Omega'}^* S_{\Omega'} (\hat{x} - x^\sharp)}_2 + \norm{T S_{\Omega'}^* S_{\Omega'} (x - x^\sharp)}_2 \leq 2 \epsilon \norm{T}.$$

The rest of the proof will compute upper bounds on $\norm{T h}_2$ in two complementary cases similarly to the proof of Lemma \[lemma:uniqueness\]. Unlike the noiseless case ($x^\sharp = x$ and $\epsilon = 0$) in Lemma \[eq:bnd\_qi\_infty\], the condition in does not necessarily imply $S_\Omega h = 0$. In fact, the proof of Lemma \[lemma:uniqueness\] critically depends on the condition $S_\Omega h = 0$. Essentially, we replace $h$ by $(I_n - S_{\Omega'}^* S_{\Omega'}) h$. Then it follows that $$\label{eq:noisy_vanish}
%B_{\Omega'} (B - B_{\Omega'}) T h = 0.
S_{\Omega'} (I_n - S_{\Omega'}^* S_{\Omega'}) h = 0.$$

**Case 1:** We first consider the case when $(I_n - S_{\Omega'}^* S_{\Omega'}) h$ satisfies $$\label{eq:case1noisy}
\norm{\Pi_J T (I_n - S_{\Omega'}^* S_{\Omega'}) h}_2
\leq 3 n \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} \norm{\Pi_{[N] \setminus J} T (I_n - S_{\Omega'}^* S_{\Omega'}) h}_2,$$ where $J$ denotes the support of $T x$.

Under , similarly to the proof of Lemma \[lemma:uniqueness\], we have $$\label{eq:pf_thm_stability:bnd2}
\norm{T x + T (I_n - S_{\Omega'}^* S_{\Omega'}) h}_1
\geq \norm{T x}_1 + \frac{1}{14} \norm{\Pi_{[N] \setminus J} T (I_n - S_{\Omega'}^* S_{\Omega'}) h}_2.$$ Combining and provides $$\label{eq:pf_thm_stability:bnd3}
\norm{\Pi_{[N] \setminus J} T (I_n - S_{\Omega'}^* S_{\Omega'}) h}_2
\leq 14 \norm{T S_{\Omega'}^* S_{\Omega'} h}_1
\leq 14 \sqrt{N} \norm{T S_{\Omega'}^* S_{\Omega'} h}_2 \leq 28\sqrt{N} \epsilon \norm{T}.$$ On the other hand, implies $$\label{eq:pf_thm_stability:bnd4}
\begin{aligned}
\norm{T (I_n - S_{\Omega'}^* S_{\Omega'}) h}_2
{} & \leq \norm{\Pi_{[N] \setminus J} T (I_n - S_{\Omega'}^* S_{\Omega'}) h}_2 + \norm{\Pi_J T (I_n - S_{\Omega'}^* S_{\Omega'}) h}_2 \\
{} & \leq (1 + 3 n \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty}) \norm{\Pi_{[N] \setminus J} T (I_n - S_{\Omega'}^* S_{\Omega'}) h}_2.
\end{aligned}$$ Therefore, combining \[eq:tube\_cstr,eq:pf\_thm\_stability:bnd3,eq:pf\_thm\_stability:bnd4\] provides $$\label{eq:pf_thm_stability:bnd5}
\norm{T h}_2 \leq \left\{ 2 + 28 \sqrt{N} \left( 3 n \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} + 1 \right) \right\} \epsilon \norm{T}.$$

**Case 2:** Next, we consider the complementary case when $(I_n - S_{\Omega'}^* S_{\Omega'}) h$ satisfies $$\label{eq:case2noisy}
\norm{\Pi_J T (I_n - S_{\Omega'}^* S_{\Omega'}) h}_2
> 3 n \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} \norm{\Pi_{[N] \setminus J} T (I_n - S_{\Omega'}^* S_{\Omega'}) h}_2.$$

Again, similarly to the proof of Lemma \[lemma:uniqueness\], we get $(I_n - S_{\Omega'}^* S_{\Omega'}) h = 0$. Therefore, $$\norm{T h}_2 \leq \norm{T (I_n - S_{\Omega'}^* S_{\Omega'}) h}_2 + \norm{T S_{\Omega'}^* S_{\Omega'} T h}_2 \leq 2 \epsilon \norm{T},$$ which is smaller than the upper bound on $\norm{T h}_2$ in the previous case.

By applying $\norm{h}_2 \leq \norm{T h}_2 / \sigma_{\min}(T)$ to , we obtain the desired upper bound on $\norm{h}_2$. This completes the proof.

Proof of Theorem \[thm:stability2\] {#subsec:pf:thm:stability2}
-----------------------------------

By Theorem \[thm:rboplike\], the condition in implies that $\frac{n}{m} T S_\Omega^* S_\Omega T^\dagger$ satisfies the condition in with constant $\delta = 1/3$. Note that the estimates in Lemmas \[lemma:E1,lemma:E2,lemma:E3\] are implied by . Therefore, the rest of the proof will be identical to that of Theorem \[thm:stability2\] except that we compute a tighter upper bound on $\norm{\Pi_J T (I_n - S_{\Omega'}^* S_{\Omega'}) h}_2$ as follows.

First, we decompose $\Pi_J T (I_n - S_{\Omega'}^* S_{\Omega'}) h$ as $$\label{eq:pf_thm_stability2:decomp}
\begin{aligned}
\Pi_J T (I_n - S_{\Omega'}^* S_{\Omega'}) h
{} & = \Pi_J \left(T T^\dagger - \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger\right) T h \\
{} & \quad + \Pi_J \frac{n}{m} T (S_\Omega^* S_\Omega - S_{\Omega'}^* S_{\Omega'}) h \\
{} & \quad + \Pi_J \left( \frac{n}{m} - 1 \right) T S_{\Omega'}^* S_{\Omega'} h.
\end{aligned}$$

Let $J_1$ correspond to the indices of the $s$-largest coefficients of $\Pi_{[N] \setminus J} T h$; $J_2$ to the indices of the next $s$-largest coefficients of $\Pi_{[N] \setminus J} T h$, and so on. Then the $\ell_2$-norm first term in the right-hand side of is upper-bounded by $$\label{eq:pf_thm_stability2:bnd1}
\begin{aligned}
{} & \left\|\Pi_J \left(T T^\dagger - \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger\right) T h\right\|_2 \\
{} & \leq \left\|\Pi_J \left(T T^\dagger - \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger\right) \Pi_{J \cup J_1} T h\right\|_2 \\
{} & \quad + \sum_{i \geq 2} \left\|\Pi_J \left(T T^\dagger - \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger\right) \Pi_{J_i} T h\right\|_2.
\end{aligned}$$ By , the first term in the right-hand side of is upper-bounded by $$\label{eq:pf_thm_stability2:bnd2}
\left\|\Pi_J \left(T T^\dagger - \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger\right) \Pi_{J \cup J_1} T h\right\|_2
\leq \frac{1}{3} \norm{\Pi_{J \cup J_1} T h}_2
\leq \frac{1}{3} \norm{T h}_2.$$

By , the second term in the right-hand side of is upper-bounded by $$\label{eq:pf_thm_stability2:bnd3}
\begin{aligned}
{} & \sum_{i \geq 2} \left\|\Pi_J \left(T T^\dagger - \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger\right) \Pi_{J_i} T h\right\|_2 \\
{} & \leq \frac{1}{3} \sum_{i \geq 2} \norm{\Pi_{J_i} T h}_2
\leq \frac{1}{3\sqrt{s}} \sum_{i \geq 1} \norm{\Pi_{J_i} T h}_1
= \frac{1}{3\sqrt{s}} \norm{\Pi_{[N] \setminus J} T h}_1.
\end{aligned}$$ Since $\hat{x}$ is the minimizer to , we have the so called “cone” constraint: $$\norm{T x}_1 \geq \norm{T \hat{x}}_1 \geq \norm{Tx + T h}_1 \geq \norm{\Pi_J T x}_1 - \norm{\Pi_J T h}_1 + \norm{\Pi_{[N] \setminus J} T h}_1 - \norm{\Pi_{[N] \setminus J} T x}_1,$$ which implies $$\norm{\Pi_{[N] \setminus J} T h}_1 \leq 2 \norm{\Pi_{[N] \setminus J} T x}_1 + \norm{\Pi_J T h}_1 = \norm{\Pi_J T h}_1,$$ where the last step follows since $T x$ is supported on $J$. Therefore, implies $$\label{eq:pf_thm_stability2:bnd4}
\sum_{i \geq 2} \left\|\Pi_J \left(T T^\dagger - \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger\right) \Pi_{J_i} T h\right\|_2
\leq \frac{1}{3\sqrt{s}} \norm{\Pi_{[N] \setminus J} T h}_1
\leq \frac{1}{3\sqrt{s}} \norm{\Pi_J T h}_1
\leq \frac{1}{3} \norm{\Pi_J T h}_2.$$

Plugging and to provides $$\label{eq:pf_thm_stability2:bnd5}
\left\|\Pi_J \left(T T^\dagger - \frac{n}{m} T S_\Omega^* S_\Omega T^\dagger\right) T h\right\|_2
\leq \frac{2}{3} \norm{T h}_2.$$

Next, we derive an upper bound on the $\ell_2$-norm of the second term in the right-hand side of . Since $\Omega'$ consists of distinct elements in $\Omega$, it follows that $$S_{\Omega'}^* S_{\Omega'} S_\Omega^* S_\Omega
= \sum_{k \in \Omega} S_{\Omega'}^* S_{\Omega'} e_k e_k^*
= \sum_{k \in \Omega} e_k e_k^*
= S_\Omega^* S_\Omega.$$ Furthermore, $S_{\Omega'}^* S_{\Omega'}$ is idempotent. Therefore, we obtain the following identity: $$\label{eq:pf_thm_stability2:id1}
S_\Omega^* S_\Omega - S_{\Omega'}^* S_{\Omega'} = (S_\Omega^* S_\Omega - S_{\Omega'}^* S_{\Omega'}) S_{\Omega'}^* S_{\Omega'}.$$ From , we get $$\label{eq:pf_thm_stability2:bnd6}
\begin{aligned}
\norm{T (S_\Omega^* S_\Omega - S_{\Omega'}^* S_{\Omega'}) h}_2
{} & = \norm{T (S_\Omega^* S_\Omega - S_{\Omega'}^* S_{\Omega'}) S_{\Omega'}^* S_{\Omega'} h}_2 \\
{} & = \norm{T (S_\Omega^* S_\Omega - S_{\Omega'}^* S_{\Omega'}) T^\dagger T S_{\Omega'}^* S_{\Omega'} h}_2 \\
{} & \leq \norm{T (S_\Omega^* S_\Omega - S_{\Omega'}^* S_{\Omega'}) T^\dagger} \norm{T S_{\Omega'}^* S_{\Omega'} h}_2 \\
{} & \leq \max_k \norm{T e_k e_k^* T^\dagger} (|\Omega|-|\Omega'|) \norm{T S_{\Omega'}^* S_{\Omega'} h}_2 \\
{} & \leq \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} (|\Omega|-|\Omega'|) \norm{T S_{\Omega'}^* S_{\Omega'} h}_2.
\end{aligned}$$ Then the $\ell_2$-norm of the second term in the right-hand side of is upper-bounded by $$\label{eq:pf_thm_stability2:bnd7}
\begin{aligned}
\left\|\Pi_J \frac{n}{m} T (S_\Omega^* S_\Omega - S_{\Omega'}^* S_{\Omega'}) h\right\|_2
{} & \leq \frac{n}{m} \norm{T (S_\Omega^* S_\Omega - S_{\Omega'}^* S_{\Omega'}) h}_2 \\
{} & \leq \frac{n}{m} \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} (|\Omega|-|\Omega'|) \norm{T S_{\Omega'}^* S_{\Omega'} h}_2.
\end{aligned}$$

By applying and to , then combining the result with and , we get $$\begin{aligned}
\norm{T h}_2
\leq 2 \epsilon \norm{T} + 28 \sqrt{N} \epsilon \norm{T} + \frac{2}{3} \norm{T h}_2
+ 2 \frac{n}{m} \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} (|\Omega|-|\Omega'|) \epsilon \norm{T}
+ 2 \left( \frac{n}{m} - 1 \right) \epsilon \norm{T},\end{aligned}$$ which implies $$\norm{T h}_2 \leq 6 \left[ 14\sqrt{N} + \frac{n}{m} \left( \norm{T}_{1 \to 2} \norm{T^\dagger}_{2 \to \infty} (|\Omega|-|\Omega'|) + 1 \right) \right] \epsilon \norm{T}.$$

In the case when $T^* T = I_n$, $T e_k e_k^* T^\dagger$s correspond to orthogonal projections onto mutually orthogonal one-dimensional subspaces. Recall that the summands in $T S_\Omega^* S_\Omega T^\dagger$ repeat at most $R$ times. Then the summands in $T S_\Omega^* S_\Omega T^\dagger - T S_{\Omega'}^* S_{\Omega'} T^\dagger$ repeat at most $R - 1$ times. Therefore, we get a sharper estimate than that in given by $$\label{eq:pf_thm_stability2:bnd8}
\begin{aligned}
\norm{T (S_\Omega^* S_\Omega - S_{\Omega'}^* S_{\Omega'}) h}_2
{} & \leq \norm{T (S_\Omega^* S_\Omega - S_{\Omega'}^* S_{\Omega'}) T^\dagger} \norm{T S_{\Omega'}^* S_{\Omega'} h}_2 \\
{} & \leq (R - 1) \norm{T S_{\Omega'}^* S_{\Omega'} h}_2.
\end{aligned}$$ This completes the proof for the second claim.

Numerical Results {#sec:numres}
=================

In this section, we conduct numerical experiments of solving and , with partial Fourier measurements and several different sparsifying transforms. We compare different sampling schemes in Monte-Carlo experiments, and observe that the variable density sampling schemes proposed in and yield superior recovery results in terms of success rate.

The optimization problems and are solved using Alternating Direction Method of Multipliers (ADMM) [@boyd2011distributed]. For example, for $T=\Phi\Psi^*\in\cz^{n\times n}$, is rewritten in the following form with two linear constraints, and solved by ADMM with two additional terms in the augmented Lagrangian. $$\begin{array}{ll}
\displaystyle \minimize_{y \in \cz^n} & \norm{y}_1 \\
\mathrm{subject~to} & T g = y,\\
                    & S_\Omega g = S_\Omega x.
\end{array}$$ In all experiments, the ADMM algorithm runs for 1,000 iterations.

1D Signals
----------

For 1D signals, we use the DFT $\Psi\in\cz^{n\times n}$, and two sparsifying transforms $\Psi_{\mathrm{TV}, n}, \Psi_{\mathrm{W}, n, \ell}\in \cz^{n\times n}$, denoting the finite difference operator and the discrete Haar wavelet [@mallat2008wavelet] at level $\ell$, respectively. For the finite difference operator $\Psi_{\mathrm{TV}, n}$, we use the two-step scheme in Section \[sec:TV\]. In Step 2), we either use the uniform density according to Corollary \[cor:circulant1\] (see Fig. \[fig:1d\_a\]), or the distribution restricted to $\{2,3,\dots, n\}$ computed from the other transform $\Psi_{\mathrm{W}, n, \ell}$ (see Fig. \[fig:1d\_b\]). For the discrete Haar wavelet $\Psi_{\mathrm{W}, n, \ell}$, we test two distributions on $[n]$ – the uniform distribution (see Fig. \[fig:1d\_a\]) and the variable density distribution (see Fig. \[fig:1d\_b\]).

In the numerical experiments, we choose $n = 512$, and synthesize signals $f$ at sparsity levels $s = 16, 32, 48, \dots, 128$ with respect to the above two sparsifying transforms. We use the Haar wavelet at level $\ell = 6$. To make the experiments more realistic, we synthesize the sparse signals by thresholding a real-world signal (see Fig. \[fig:1d\_sig\]) in the transform domains. For the discrete Haar wavelet, we analyze the signal using $\Psi_{\mathrm{W}, n, \ell}$, zero out small coefficients to achieve a certain sparsity level, and synthesize the signal using $\Psi_{\mathrm{W}, n, \ell}^*$. Due to the non-injectivity of the finite difference operator, we replace the last row of $\Psi_{\mathrm{TV}, n}$ by $[1,1,\dots, 1]^\top \in\cz^n$ in the signal analysis and synthesis steps.

For every sampling scheme, we repeat the experiment for $m = 16, 32, 48, \dots, 512$. We run 50 Monte-Carlo experiments for each setting. An instance is declared a success if the following reconstruction signal-to-noise ratio (RSNR) of the solution $\hat{g}$ to exceeds $60$dB. $$\mathrm{RSNR} = -20\log_{10}\left(\frac{\norm{\hat{g}-x}_2}{\norm{x}_2}\right).$$ The success rate is computed for every pair $(s, m)$ and shown in Fig. \[fig:1d\_c\] – \[fig:1d\_f\].

For signal recovery using the Haar wavelet, the variable density sampling scheme yields higher success rate than the uniform density sampling scheme (see Fig. \[fig:1d\_c\] and \[fig:1d\_d\]). For 1D TV, the density computed using 1D TV, which is uniform, yields higher success rate than that computed from the Haar wavelet (see Fig. \[fig:1d\_e\] and \[fig:1d\_f\]). These experiments show that one can recover sparse signals more successfully using the sampling density computed from the specific sparsifying transform used in the recovery, which is adaptive to local incoherence between the transform and the measurement. It is commonly believed among practitioners that sampling more densely in the low frequency region, where the energy of a natural signal is concentrated, always provides a better reconstruction. However, that turns out not be the case when one cares about perfect recovery of exactly sparse signals in a certain transform domain from noise-free measurements.

\
\

\

2D Signals
----------

We also run numerical experiments on a 2D signal, the modified Shepp-Logan phantom (see Fig. \[fig:2d\_sig\]). We minimize the anisotropic and isotropic 2D total variations, which correspond to solving and for the 2D finite difference operator $\Phi_{\mathrm{TV},n_1,n_2}$.

For the two types of total variations, we use the two-step scheme in Section \[sec:TV\]. In Step 2), we use the densities in and for anisotropic and isotropic total variations, respectively. As a comparison, we use the variable density proposed by Krahmer and Ward [@krahmer2014stable], which is computed with the 2D separable Haar wavelet $\Psi_{\mathrm{W}, n_2, \log_2n_2}\otimes \Psi_{\mathrm{W}, n_1, \log_2n_1}$.

We use a phantom of size $n = n_1\times n_2 = 256\times 256$, and repeat the experiments for $m= n/32, n/16,3n/32,\dots, n/4$. We run 50 Monte-Carlo experiments for each setting, and compute the success rate for every chioce of $m$, as shown in Fig. \[fig:2d\_d\] and \[fig:2d\_e\].

For both anisotropic TV minimization and isotropic TV minimization , the success rates using sampling density computed from TV are higher than those using sampling density computed from separable Haar wavelet. Although the performances of two sampling schemes are relatively close for anisotropic TV minimization (see Fig. \[fig:2d\_d\]), the advantage of the density computed from TV over that computed from wavelet is more pronounced for isotropic TV minimization (see Fig. \[fig:2d\_e\]). Contrary to common belief, sampling low frequencies more densely does not always lead to superior recovery. We suggest using sampling densities and tailored to the specific sparsifying transform and the measurement operator.

Conclusion {#sec:concl}
==========

In this paper, we established a unified theory for recovery of sparse signals in a transform domain. Our theory guaranteed robust recovery from noisy measurements by convex programming and apply without relying on a particular choice of measurement and sparsifying transforms. We quantified the sufficient sampling rate using functions of the two transforms, and this result identifies a class of measurement and sparsity models enabling recovery at a near optimal sampling rate. We also proposed a variable sampling density designed with incoherence parameters of the two transforms, which provided recovery guarantee at a lower sampling rate than previous works in various scenarios. Furthermore, we extended the result to the group-sparsity models so that it also applies to the popular isotropic total variation minimization. In particular, for the partial Fourier recovery of sparse signals over a circulant transform, our theory suggests a uniformly random sampling or its variation. Our numerical results showed that our variable density random sampling strategy outperforms other known sampling strategies in various scenarios. This suggests that our new theory is indeed universally useful.

Acknowledgement {#acknowledgement .unnumbered}
===============

The authors thank referees for their valuable comments and suggestions.

Bernstein inequalities
======================

\[thm:mtx\_bernstein\_ineq\] Let $\{X_j\} \in \cz^{d \times d}$ be a finite sequence of independent random matrices. Suppose that $\mathbb{E} X_j = 0$ and $\norm{X_j} \leq B$ almost surely for all $j$ and $$\max\left( \left\| \sum_j \mathbb{E} X_j X_j^* \right\|,~ \left\| \sum_j \mathbb{E} X_j^* X_j \right\| \right) \leq \sigma^2.$$ Then for all $t \geq 0$, $$\mathbb{P} \left( \left\| \sum_j X_j \right\| \geq t \right)
\leq 2d \exp \left( \frac{-t^2/2}{\sigma^2 + Bt/3} \right).$$

\[thm:vec\_bernstein\_ineq\] Let $\{v_j\} \in \cz^d$ be a finite sequence of independent random vectors. Suppose that $\mathbb{E} v_j = 0$ and $\norm{v_j}_2 \leq B$ almost surely for all $j$ and $\mathbb{E} \sum_j \norm{v_j}_2^2 \leq \sigma^2$. Then for all $0 \leq t \leq \sigma^2/B$, $$\mathbb{P} \left( \left\| \sum_j v_j \right\|_2 \geq t \right)
\leq \exp \left( - \frac{t^2}{8 \sigma^2} + \frac{1}{4} \right).$$

Proof of Lemma \[lemma:E1\] {#sec:pf:lemma:E1}
===========================

Define $$X_j := \Pi_J (n T e_{\omega_j} e_{\omega_j}^* T^\dagger - T T^\dagger) \Pi_J, \quad \forall j \in [m].$$ Then, $X_j$ satisfies $\mathbb{E} X_j = 0$ and $\norm{X_j} \leq \mu s$ for all $j$. Since $$\begin{aligned}
X_j^* X_j
{} & = n^2 \Pi_J \widetilde{T} e_{\omega_j} e_{\omega_j}^* T^* \Pi_J T e_{\omega_j} e_{\omega_j}^* T^\dagger \Pi_J \\
{} & \quad - n \Pi_J \widetilde{T} e_{\omega_j} e_{\omega_j}^* T^* \Pi_J T T^\dagger \Pi_J \\
{} & \quad - n \Pi_J T T^\dagger \Pi_J T e_{\omega_j} e_{\omega_j}^* T^\dagger \Pi_J \\
{} & \quad + \Pi_J T T^\dagger \Pi_J T T^\dagger \Pi_J,\end{aligned}$$ it follows that $$\begin{aligned}
\mathbb{E} X_j^* X_j
{} & = \mathbb{E} n^2 \Pi_J \widetilde{T} e_{\omega_j} e_{\omega_j}^* T^* \Pi_J T e_{\omega_j} e_{\omega_j}^* T^\dagger \Pi_J - \Pi_J T T^\dagger \Pi_J T T^\dagger \Pi_J \\
{} & \leq \mathbb{E} n^2 e_{\omega_j}^* T^* \Pi_J T e_{\omega_j} \Pi_J \widetilde{T} e_{\omega_j} e_{\omega_j}^* T^\dagger \Pi_J \\
{} & = \mathbb{E} n^2 \norm{\gamma^{1/2} \Pi_J T e_{\omega_j}}_2^2 \gamma^{-1} \Pi_J \widetilde{T} e_{\omega_j} e_{\omega_j}^* T^\dagger \Pi_J \\
{} & \leq \mathbb{E} n \mu s \gamma^{-1} \Pi_J \widetilde{T} e_{\omega_j} e_{\omega_j}^* T^\dagger \Pi_J \\
{} & = \mu s \gamma^{-1} \Pi_J \widetilde{T} T^\dagger \Pi_J.\end{aligned}$$ By symmetry, we also have $$\mathbb{E} X_j X_j^* \leq \mu s \gamma \Pi_J T T^* \Pi_J.$$ Therefore, $$\max\left( \left\| \sum_{j=1}^m \mathbb{E} X_j X_j^* \right\|,~ \left\| \sum_{j=1}^m \mathbb{E} X_j^* X_j \right\| \right)
\leq m \mu s \max( \norm{\gamma^{-1} \widetilde{T} T^\dagger}, \norm{\gamma T T^*} )
\leq \frac{m \mu s}{1 - \norm{\gamma T^* T - I_n}}.$$ Applying the above results to Theorem \[thm:mtx\_bernstein\_ineq\] with $t = m \delta$ completes the proof.

Proof of Lemma \[lemma:E2\] {#sec:pf:lemma:E2}
===========================

Define $$v_j := \Pi_J (n T e_{\omega_j} e_{\omega_j}^* T^\dagger - T T^\dagger) \Pi_J q, \quad \forall j \in [m].$$ Then, $v_j$ satisfies $\mathbb{E} v_j = 0$ and $$\begin{aligned}
\norm{v_j}_2
{} & \leq \norm{\Pi_J n T e_{\omega_j} e_{\omega_j}^* T^\dagger \Pi_J q}_2 + \norm{\Pi_J T T^\dagger \Pi_J q}_2 \\
{} & \leq (\norm{\gamma^{1/2} \Pi_J \sqrt{n} T e_{\omega_j}}_2 \norm{\gamma^{-1/2} \Pi_J \sqrt{n} \widetilde{T} e_{\omega_j}}_2 + 1) \norm{\Pi_J q}_2 \\
{} & \leq (s\mu+1) \norm{\Pi_J q}_2.\end{aligned}$$ Furthermore, $$\begin{aligned}
\mathbb{E} \norm{v_j}_2^2
{} & = \mathbb{E} n^2 q^* \Pi_J \widetilde{T} e_{\omega_j} e_{\omega_j}^* T^* \Pi_J T e_{\omega_j} e_{\omega_j}^* T^\dagger \Pi_J q
- q^* \Pi_J T T^\dagger \Pi_J q \\
{} & \leq n \norm{\gamma^{1/2} \Pi_J T e_{\omega_j}}_2^2 \mathbb{E} n \gamma^{-1} q^* \Pi_J \widetilde{T} e_{\omega_j} e_{\omega_j}^* T^\dagger \Pi_J q \\
{} & \leq \mu s \gamma^{-1} \mathbb{E} n q^* \Pi_J \widetilde{T} e_{\omega_j} e_{\omega_j}^* T^\dagger \Pi_J q \\
{} & = \mu s \gamma^{-1} q^* \Pi_J \widetilde{T} T^\dagger \Pi_J q \\
{} & \leq \frac{\mu s \norm{\Pi_J q}_2^2}{1 - \norm{\gamma T^* T - I_n}},\end{aligned}$$ where the second inequality follows by the incoherence property. Applying the above results to Theorem \[thm:vec\_bernstein\_ineq\] completes the proof.

Proof of Lemma \[lemma:E3\] {#sec:pf:lemma:E3}
===========================

Let $i \in [n] \setminus J$ be arbitrarily fixed. Define $$w_j := \langle e_i, (n T e_{\omega_j} e_{\omega_j}^* T^\dagger - T T^\dagger) \Pi_J q \rangle, \quad \forall j \in [m].$$ Then, $w_j$ satisfies $\mathbb{E} w_j = 0$ and $$\begin{aligned}
|w_j|
{} & \leq |e_j^* n T e_{\omega_j} e_{\omega_j}^* T^\dagger \Pi_J q| + \norm{T T^\dagger \Pi_J q}_\infty \\
{} & \leq (\norm{\gamma^{1/2} \sqrt{n} T e_{\omega_j}}_\infty \norm{\gamma^{-1/2} \sqrt{n} \Pi_J \widetilde{T} e_{\omega_j}}_2 + 1) \norm{\Pi_J q}_2 \\
{} & \leq (\sqrt{s} \mu+1) \norm{\Pi_J q}_2.\end{aligned}$$ Furthermore, $$\begin{aligned}
\mathbb{E} |w_j|^2
{} & = \mathbb{E} n^2 q^* \Pi_J \widetilde{T} e_{\omega_j} e_{\omega_j}^* T^* e_i e_i^* T e_{\omega_j} e_{\omega_j}^* T^\dagger \Pi_J q
- q^* \Pi_J T T^\dagger e_i e_i^* T T^\dagger \Pi_J q \\
{} & \leq n \norm{\gamma^{1/2} T e_{\omega_j}}_\infty^2 \gamma^{-1} \mathbb{E} n q^* \Pi_J \widetilde{T} e_{\omega_j} e_{\omega_j}^* T^\dagger \Pi_J q \\
{} & \leq \mu \gamma^{-1} q^* \Pi_J \widetilde{T} T^\dagger \Pi_J q \\
{} & \leq \frac{\mu \norm{\Pi_J q}_2^2}{1 - \norm{\gamma T^* T - I_n}}.\end{aligned}$$ Applying the above results to Theorem \[thm:mtx\_bernstein\_ineq\] gives $$\mathbb{P}\left(\left| \left\langle e_i, \left(\frac{n}{m} B_\Omega^* - B\right) \Pi_J q \right\rangle \right| \geq t \norm{\Pi_J q}_2\right)
\leq \exp\left( - \frac{m}{2\mu} \cdot \frac{t^2}{1/(1-\norm{\gamma T^* T - I_n}) + \sqrt{s}t/3} \right).$$ Combine this for $i \in [N]$ with the union bound completes the proof.

Proof of Lemma \[lemma:E3’\] {#sec:pf:lemma:E3'}
============================

Let $i \in [n] \setminus J$ be arbitrarily fixed. Define $$v_j := \Pi_{\calG_i} (n T e_{\omega_j} e_{\omega_j}^* T^\dagger - T T^\dagger) \Pi_{\calG_J} q, \quad \forall j \in [m].$$ Then, $v_j$ satisfies $\mathbb{E} v_j = 0$ and $$\begin{aligned}
\norm{v_j}_2
{} & \leq \norm{\Pi_{\calG_i} n T e_{\omega_j} e_{\omega_j}^* T^\dagger \Pi_{\calG_J} q}_2 + \norm{\Pi_{\calG_i} T T^\dagger \Pi_{\calG_J} q}_2 \\
{} & \leq (\norm{\gamma^{1/2} \sqrt{n} \Pi_{\calG_i} T e_{\omega_j}}_2 \norm{\gamma^{-1/2} \sqrt{n} \Pi_{\calG_J} \widetilde{T} e_{\omega_j}}_2 + 1) \norm{\Pi_{\calG_J} q}_2 \\
{} & \leq (\sqrt{s} \mu_\calG + 1) \norm{\Pi_{\calG_J} q}_2.\end{aligned}$$ Furthermore, $$\begin{aligned}
\mathbb{E} v_j^* v_j
{} & = \mathbb{E} n^2 q^* \Pi_{\calG_J} \widetilde{T} e_{\omega_j} e_{\omega_j}^* T^* \Pi_{\calG_i} T e_{\omega_j} e_{\omega_j}^* T^\dagger \Pi_{\calG_J} q
- q^* \Pi_{\calG_J} T T^\dagger \Pi_{\calG_i} T T^\dagger \Pi_{\calG_J} q \\
{} & \leq n \norm{\gamma^{1/2} \Pi_{\calG_i} T e_{\omega_j}}_2^2 \gamma^{-1} \mathbb{E} n q^* \Pi_{\calG_J} \widetilde{T} e_{\omega_j} e_{\omega_j}^* T^\dagger \Pi_{\calG_J} q \\
{} & \leq \mu_\calG \gamma^{-1} q^* \Pi_{\calG_J} \widetilde{T} T^\dagger \Pi_{\calG_J} q \\
{} & \leq \frac{\mu_\calG \norm{\Pi_{\calG_J} q}_2^2}{1 - \norm{\gamma T^* T - I_n}}.\end{aligned}$$ Note that $$v_j v_j^* \leq v_j^* v_j I_L, \quad \forall j \in [m].$$ Applying the above results to Theorem \[thm:vec\_bernstein\_ineq\] gives $$\mathbb{P}\left(\left\| \Pi_{\calG_i} \left(\frac{n}{m} B_\Omega^* - B\right) \Pi_{\calG_J} q \right\|_2 \geq t \norm{\Pi_{\calG_J} q}_2\right)
\leq \exp\left( - \frac{m}{2\mu} \cdot \frac{t^2}{1/(1-\norm{\gamma T^* T - I_n}) + \sqrt{s}t/3} \right).$$ Combine this for $i \in [N]$ with the union bound completes the proof.

Proof of Theorem \[thm:rboplike\] {#sec:pf:thm:rboplike}
=================================

Theorem \[thm:rboplike\] is analogous to [@lee2013oblique Theorem 3.1]. It has been shown that if $T$ is of full row rank, then the deviation of $\frac{n}{m} T S_\Omega^* S_\Omega T^\dagger$ from $T T^\dagger = I_N$ is small with high probability [@lee2013oblique Theorem 3.1]. On the contrary, Theorem \[thm:rboplike\] assumes that $T$ is of full column rank and shows that the deviation of $\frac{n}{m} T S_\Omega^* S_\Omega T^\dagger$ from $T T^\dagger$, which is not necessarily $I_N$, is small with high probability.

The proof of Theorem \[thm:rboplike\] is obtained from that of [@lee2013oblique Theorem 3.1] by replacing $I_N$ by $T T^\dagger$. For example, the isotropy condition $$\frac{n}{m} \mathbb{E} T S_\Omega^* S_\Omega T^\dagger = I_N$$ is replaced by $$\frac{n}{m} \mathbb{E} T S_\Omega^* S_\Omega T^\dagger = T T^\dagger.$$ For a matrix $M \in \cz^{N \times N}$, the term $\theta_s(M)$, previously defined by in [@lee2013oblique] $$\theta_s(M) := \max_{|\widetilde{J}| \leq s} \norm{\Pi_{\widetilde{J}} (M - I_N) \Pi_{\widetilde{J}}}$$ is replaced by $$\theta_s(M) := \max_{|\widetilde{J}| \leq s} \norm{\Pi_{\widetilde{J}} (M - T T^\dagger) \Pi_{\widetilde{J}}}$$ Clearly, $T T^\dagger = I_N$ if $T$ has full row rank. However, in the hypothesis of Theorem \[thm:rboplike\], $T$ has full column rank and $T T^\dagger$ may be rank deficient. Since the modifications are rather straightforward, we omit the details of the proof and refer them to [@lee2013oblique Appendix E].

By modifying [@lee2013oblique Theorem 3.1] and its proof as shown above, is implied by and $$m \geq C_1 \delta^{-2} K_T \mu s \log^2 s \log N \log m,$$ where the factor $K_T$ is given by $$\begin{aligned}
K_T
{} & = \left\{
\left(2 + \max_{|\widetilde{J}| \leq s} \left\|\Pi_{\widetilde{J}} (\gamma T T^* - T T^\dagger) \Pi_{\widetilde{J}}\right\|\right)^{1/2}
+
\left(2 + \max_{|\widetilde{J}| \leq s} \left\|\Pi_{\widetilde{J}} (\gamma^{-1} \widetilde{T} T^\dagger - T T^\dagger) \Pi_{\widetilde{J}}\right\|\right)^{1/2}
\right\}^2 \\
{} & \leq 4 + 2 \max\left(
\max_{|\widetilde{J}| \leq s} \norm{\Pi_{\widetilde{J}}(\gamma T T^* - T T^\dagger)\Pi_{\widetilde{J}}}
,~
\max_{|\widetilde{J}| \leq s} \norm{\Pi_{\widetilde{J}}(\gamma^{-1} \widetilde{T} T^\dagger - T T^\dagger)\Pi_{\widetilde{J}}}
\right) \\
{} & \leq 4 + 2 \max\left(
\norm{\gamma T T^* - T T^\dagger}
,~
\norm{\gamma^{-1} \widetilde{T} T^\dagger - T T^\dagger}
\right) \\
{} & = 4 + 2 \max\left(
\norm{\gamma T^* T - I_n}
,~
\norm{\gamma^{-1} T^\dagger \widetilde{T} - I_n}
\right).\end{aligned}$$ Finally, we verify that $$\norm{\gamma^{-1} T^\dagger \widetilde{T} - I_n} \leq \frac{1}{\norm{\gamma T^* T - I_n}},$$ where the upper bound dominates $\norm{\gamma T^* T - I_n}$. This completes the proof.

[^1]: This work was supported in part by the National Science Foundation under grants IIS 14-47879 and Korea Science and Engineering Foundation under grants NRF-2013M3A9B2076548 and NRF-2016R1A2B3008104. K. Lee is with the School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA 30332 USA (e-mail: kiryung@ece.gatech.edu). Y. Li is with the Coordinated Science Laboratory and the Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA (e-mail: yli145@illinois.edu). K.H. Jin is with the Biomedical Imaging Group, École Polytechnique Fédérale de Lausanne, 1015 Lausanne, Switzerland (e-mail: kyong.jin@epfl.ch). J.C. Ye is with the Department of Bio and Brain Engineering, Korea Advanced Institute of Science and Technology (KAIST), Daejon 305-701, Korea (e-mail: jong.ye@kaist.ac.kr).

[^2]: A Gaussian sensing matrix is also obtained in the form of by choosing $\Psi$ as a Gaussian matrix.

[^3]: Krahmer and Ward [@krahmer2014stable] considered orthonormal $\Phi$ and $\Psi$ respectively corresponding to the DFT and the Haar DWT. In this case, $T^\dagger = T^*$. Thus, $\widetilde{T} = T$.

[^4]: A subset of the authors [@ye2016compressive] sharpened the original analysis of the completion of structured low-rank matrices by Chen and Chi [@chen2014robust] particularly on the noise propagation in the recovery. In this paper, we generalize the improved version [@ye2016compressive].
