Recovery of Sparsely Corrupted Signals

I Introduction

This recovery problem occurs in many applications, some of which are described next:

Clipping: Non-linearities in (power-)amplifiers or in analog-to-digital converters often cause signal clipping or saturation . This impairment can be cast into the signal model \frefeq:systemmodel by setting $\mathbf{B}=\mathbf{I}_{M}$, where $\mathbf{I}_{M}$ denotes the $M\times M$ identity matrix, and rewriting \frefeq:systemmodel as $\mathbf{z}=\mathbf{y}+\mathbf{e}$ with $\mathbf{e}=g_{a}(\mathbf{y})-\mathbf{y}$. Concretely, instead of the $M$-dimensional signal vector $\mathbf{y}=\mathbf{A}\mathbf{x}$ of interest, the device in question delivers $g_{a}(\mathbf{y})$, where the function $g_{a}(\mathbf{y})$ realizes entry-wise signal clipping to the interval $[-a,+a]$. The vector $\mathbf{e}$ will be sparse, provided the clipping level is high enough. Furthermore, in this case the support set of $\mathbf{e}$ can be identified prior to recovery, by simply comparing the absolute values of the entries of $\mathbf{y}$ to the clipping threshold $a$. Finally, we note that here it is essential that the noise vector $\mathbf{e}$ be allowed to depend on the vector $\mathbf{x}$ and/or the dictionary $\mathbf{A}$.

Impulse noise: In numerous applications, one has to deal with the recovery of signals corrupted by impulse noise . Specific applications include, e.g., reading out from unreliable memory or recovery of audio signals impaired by click/pop noise, which typically occurs during playback of old phonograph records. The model in \frefeq:systemmodel is easily seen to incorporate such impairments. Just set $\mathbf{B}=\mathbf{I}_{M}$ and let $\mathbf{e}$ be the impulse-noise vector. We would like to emphasize the generality of \frefeq:systemmodel which allows impulse noise that is sparse in general dictionaries $\mathbf{B}$.

Narrowband interference: In many applications one is interested in recovering audio, video, or communication signals that are corrupted by narrowband interference. Electric hum, as it may occur in improperly designed audio or video equipment, is a typical example of such an impairment. Electric hum typically exhibits a sparse representation in the Fourier basis as it (mainly) consists of a tone at some base-frequency and a series of corresponding harmonics, which is captured by setting $\mathbf{B}=\mathbf{F}_{M}$ in \frefeq:systemmodel, where $\mathbf{F}_{M}$ is the $M$-dimensional discrete Fourier transform (DFT) matrix defined below in \frefeq:fouriermatrix.

Super-resolution and inpainting: Our framework also encompasses super-resolution and inpainting for images, audio, and video signals. In both applications, only a subset of the entries of the (full-resolution) signal vector $\mathbf{y}=\mathbf{A}\mathbf{x}$ is available and the task is to fill in the missing entries of the signal vector such that $\mathbf{y}=\mathbf{A}\mathbf{x}$. The missing entries are accounted for by choosing the vector $\mathbf{e}$ such that the entries of $\mathbf{z}=\mathbf{y}+\mathbf{e}$ corresponding to the missing entries in $\mathbf{y}$ are set to some (arbitrary) value, e.g., . The missing entries of $\mathbf{y}$ are then filled in by first recovering $\mathbf{x}$ from $\mathbf{z}$ and then computing $\mathbf{y}=\mathbf{A}\mathbf{x}$. Note that in both applications the support set $\mathcal{E}$ is known (i.e., the locations of the missing entries can easily be identified) and the dictionary $\mathbf{A}$ is typically redundant (see, e.g., for a corresponding discussion), i.e., $\mathbf{A}$ has more dictionary elements (columns) than rows, which demonstrates the need for recovery results that apply to general (i.e., possibly redundant) dictionaries.

Signal separation: Separation of (audio or video) signals into two distinct components also fits into our framework. A prominent example for this task is the separation of texture from cartoon parts in images (see and references therein). In the language of our setup, the dictionaries $\mathbf{A}$ and $\mathbf{B}$ are chosen such that they allow for sparse representation of the two distinct features; $\mathbf{x}$ and $\mathbf{e}$ are the corresponding coefficients describing these features (sparsely). Note that here the vector $\mathbf{e}$ no longer plays the role of (undesired) noise. Signal separation then amounts to simultaneously extracting the sparse vectors $\mathbf{x}$ and $\mathbf{e}$ from the observation (e.g., the image) $\mathbf{z}=\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{e}$.

Naturally, it is of significant practical interest to identify fundamental limits on the recovery of $\mathbf{x}$ (and $\mathbf{e}$, if appropriate) from $\mathbf{z}$ in \frefeq:systemmodel. For the noiseless case $\mathbf{z}=\mathbf{A}\mathbf{x}$ such recovery guarantees are known and typically set limits on the maximum allowed number of nonzero entries of $\mathbf{x}$ or—more colloquially—on the “sparsity” level of $\mathbf{x}$. These recovery guarantees are usually expressed in terms of restricted isometry constants (RICs) or in terms of the coherence parameter of the dictionary $\mathbf{A}$. In contrast to coherence parameters, RICs can, in general, not be computed efficiently. In this paper, we focus exclusively on coherence-based recovery guarantees. For the case of unstructured noise, i.e., $\mathbf{z}=\mathbf{A}\mathbf{x}+\mathbf{n}$ with no constraints imposed on $\mathbf{n}$ apart from $\mathopen{}\left\lVert\mathbf{n}\right\rVert_{2}<\infty$, coherence-based recovery guarantees were derived in . The corresponding results, however, do not guarantee perfect recovery of $\mathbf{x}$, but only ensure that either the recovery error is bounded above by a function of $\mathopen{}\left\lVert\mathbf{n}\right\rVert_{2}$ or only guarantee perfect recovery of the support set of $\mathbf{x}$. Such results are to be expected, as a consequence of the generality of the setup in terms of the assumptions on the noise vector $\mathbf{n}$.

In this paper, we consider the following questions: 1) Under which conditions can the vector $\mathbf{x}$ (and the vector $\mathbf{e}$, if appropriate) be recovered perfectly from the (sparsely corrupted) observation $\mathbf{z}=\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{e}$, and 2) can we formulate practical recovery algorithms with corresponding (analytical) performance guarantees? Sparsity of the signal vector $\mathbf{x}$ and the error vector $\mathbf{e}$ will turn out to be key in answering these questions. More specifically, based on an uncertainty relation for pairs of general dictionaries, we establish recovery guarantees that depend on the number of nonzero entries in $\mathbf{x}$ and $\mathbf{e}$, and on the coherence parameters of the dictionaries $\mathbf{A}$ and $\mathbf{B}$. These recovery guarantees are obtained for the following different cases: I) The support sets of both $\mathbf{x}$ and $\mathbf{e}$ are known (prior to recovery), II) the support set of only $\mathbf{x}$ or only $\mathbf{e}$ is known, III) the number of nonzero entries of only $\mathbf{x}$ or only $\mathbf{e}$ is known, and IV) nothing is known about $\mathbf{x}$ and $\mathbf{e}$. We formulate efficient recovery algorithms and derive corresponding performance guarantees. Finally, we compare our analytical recovery thresholds to numerical results and we demonstrate the application of our algorithms and recovery guarantees to an image inpainting example.

I-B Outline of the paper

The remainder of the paper is organized as follows. In \frefsec:priorart, we briefly review relevant previous results. In \frefsec:uncertainty_rel, we derive a novel uncertainty relation that lays the foundation for the recovery guarantees reported in \frefsec:main. A discussion of our results is provided in \frefsec:discussion and numerical results are presented in \frefsec:simulations. We conclude in \frefsec:conclusion.

I-C Notation

II Review of Relevant Previous Results

Recovery of the vector $\mathbf{x}$ from the sparsely corrupted measurement $\mathbf{z}=\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{e}$ corresponds to a sparse-signal recovery problem subject to structured (i.e., sparse) noise. In this section, we briefly review relevant existing results for sparse-signal recovery from noiseless measurements, and we summarize the results available for recovery in the presence of unstructured and structured noise.

Recovery of $\mathbf{x}$ from $\mathbf{z}=\mathbf{A}\mathbf{x}$ where $\mathbf{A}$ is redundant (i.e., $M<N_{a}$) amounts to solving an underdetermined linear system of equations. Hence, there are infinitely many solutions $\mathbf{x}$, in general. However, under the assumption of $\mathbf{x}$ being sparse, the situation changes drastically. More specifically, one can recover $\mathbf{x}$ from the observation $\mathbf{z}=\mathbf{A}\mathbf{x}$ by solving

This approach results, however, in prohibitive computational complexity, even for small problem sizes. Two of the most popular and computationally tractable alternatives to solving (P0) by an exhaustive search are basis pursuit (BP) and orthogonal matching pursuit (OMP) . BP is essentially a convex relaxation of (P0) and amounts to solving

The questions that arise naturally are: Under which conditions does (P0) have a unique solution and when do BP and/or OMP deliver this solution? To formulate the answer to these questions, define $n_{x}=\mathopen{}\left\lVert\mathbf{x}\right\rVert_{0}$ and the coherence of the dictionary $\mathbf{A}$ as

As shown in , a sufficient condition for $\mathbf{x}$ to be the unique solution of (P0) applied to $\mathbf{z}=\mathbf{A}\mathbf{x}$ and for BP and OMP to deliver this solution is

II-B Recovery in the presence of unstructured noise

Coherence-based recovery guarantees in the presence of unstructured (and deterministic) noise, i.e., for $\mathbf{z}=\mathbf{A}\mathbf{x}+\mathbf{n}$, with no constraints imposed on $\mathbf{n}$ apart from $\mathopen{}\left\lVert\mathbf{n}\right\rVert_{2}<\infty$, were derived in and the references therein. Specifically, it was shown in that a suitably modified version of BP, referred to as BP denoising (BPDN), recovers an estimate $\hat{\mathbf{x}}$ satisfying $\mathopen{}\left\lVert\mathbf{x}-\hat{\mathbf{x}}\right\rVert_{2}<C\mathopen{}\left\lVert\mathbf{n}\right\rVert_{2}$ provided that \frefeq:classicalthreshold is met. Here, $C>0$ depends on the coherence $\mu_{a}$ and on the sparsity level $n_{x}$ of $\mathbf{x}$. Note that the support set of the estimate $\hat{\mathbf{x}}$ may differ from that of $\mathbf{x}$. Another result, reported in , states that OMP delivers the correct support set (but does not perfectly recover the nonzero entries of $\mathbf{x}$) provided that

where $\mathopen{}\left\lvert x_{\textrm{min}}\right\rvert$ denotes the absolute value of the component of $\mathbf{x}$ with smallest nonzero magnitude. The recovery condition \frefeq:noisethreshold yields sensible results only if $\mathopen{}\left\lVert\mathbf{n}\right\rVert_{2}\!/\mathopen{}\left\lvert x_{\text{min}}\right\rvert$ is small. Results similar to those reported in were obtained in . Recovery guarantees in the case of stochastic noise $\mathbf{n}$ can be found in . We finally point out that perfect recovery of $\mathbf{x}$ is, in general, impossible in the presence of unstructured noise. In contrast, as we shall see below, perfect recovery is possible under structured noise according to \frefeq:systemmodel.

II-C Recovery guarantees in the presence of structured noise

As outlined in the introduction, many practically relevant signal recovery problems can be formulated as (sparse) signal recovery from sparsely corrupted measurements, a problem that seems to have received comparatively little attention in the literature so far and does not appear to have been developed systematically.

A straightforward way leading to recovery guarantees in the presence of structured noise, as in (1), follows from rewriting \frefeq:systemmodel as

with the concatenated dictionary $\mathbf{D}=[\,\mathbf{A}\,\,\mathbf{B}\,]$ and the stacked vector $\mathbf{w}=[\,\mathbf{x}^{T}\,\,\mathbf{e}^{T}\,]^{T}$. This formulation allows us to invoke the recovery guarantee in \frefeq:classicalthreshold for the concatenated dictionary $\mathbf{D}$, which delivers a sufficient condition for $\mathbf{w}$ (and hence, $\mathbf{x}$ and $\mathbf{e}$) to be the unique solution of (P0) applied to $\mathbf{z}=\mathbf{D}\mathbf{w}$ and for BP and OMP to deliver this solution . However, the so obtained recovery condition

with the dictionary coherence $\mu_{d}$ defined as

Special cases of the general setup \frefeq:systemmodel, explicitly taking into account certain structural aspects of the recovery problem were considered in . Specifically, in it was shown that for $\mathbf{A}=\mathbf{F}_{M}$, $\mathbf{B}=\mathbf{I}_{M}$, and knowledge of the support set of $\mathbf{e}$, perfect recovery of the $M$-dimensional vector $\mathbf{x}$ is possible if

We conclude this literature overview by noting that the present paper is inspired by . Specifically, we note that the recovery guarantee \frefeq:donohostarkcondition reported in is obtained from an uncertainty relation that puts limits on how sparse a given signal can simultaneously be in the Fourier basis and in the identity basis. Inspired by this observation, we start our discussion by presenting an uncertainty relation for pairs of general dictionaries, which forms the basis for the recovery guarantees reported later in this paper.

III A General Uncertainty Relation for ϵitalic-ϵ\epsilon-Concentrated Vectors

We next present a novel uncertainty relation, which extends the uncertainty relation in [33, Lem. 1] for pairs of general dictionaries to vectors that are $\epsilon$-concentrated rather than perfectly sparse. As shown in \frefsec:main, this extension constitutes the basis for the derivation of recovery guarantees for BP.

Define the mutual coherence between the dictionaries $\mathbf{A}$ and $\mathbf{B}$ as

Furthermore, we will need the following definition, which appeared previously in .

We can now state the following uncertainty relation for pairs of general dictionaries and for $\epsilon$-concentrated vectors.

The proof follows closely that of [33, Lem. 1], which applies to perfectly concentrated vectors $\mathbf{p}$ and $\mathbf{q}$. We therefore only summarize the modifications to the proof of [33, Lem. 1]. Instead of using $\sum_{p\in\mathcal{P}}\mathopen{}\left\lvert[\mathbf{p}]_{p}\right\rvert=\mathopen{}\left\lVert\mathbf{p}\right\rVert_{1}$ to arrive at [33, Eq. 29]

we invoke $\sum_{p\in\mathcal{P}}\mathopen{}\left\lvert[\mathbf{p}]_{p}\right\rvert\geq(1-\epsilon_{\mathcal{P}})\mathopen{}\left\lVert\mathbf{p}\right\rVert_{1}$ to arrive at the following inequality valid for $\epsilon_{\mathcal{P}}$-concentrated vectors $\mathbf{p}$:

Similarly, $\epsilon_{\mathcal{Q}}$-concentration, i.e., $\sum_{\mathcal{Q}}\mathopen{}\left\lvert[\mathbf{q}]_{q}\right\rvert\geq(1-\epsilon_{\mathcal{Q}})\mathopen{}\left\lVert\mathbf{q}\right\rVert_{1}$, is used to replace [33, Eq. 30] by

The uncertainty relation \frefeq:uncertaintyconcentrated is then obtained by multiplying \frefeq:uncertain5 and \frefeq:uncertain6 and dividing the resulting inequality by $\mathopen{}\left\lVert\mathbf{p}\right\rVert_{1}\mathopen{}\left\lVert\mathbf{q}\right\rVert_{1}$. ∎

In the case where both $\mathbf{p}$ and $\mathbf{q}$ are perfectly concentrated, i.e., $\epsilon_{\mathcal{P}}=\epsilon_{\mathcal{Q}}=0$, \frefthm:uncertainty reduces to the uncertainty relation reported in [33, Lem. 1], which we restate next for the sake of completeness.

If $\mathcal{P}=\textrm{supp}(\mathbf{p})$ and $\mathcal{Q}=\textrm{supp}(\mathbf{q})$, the following holds:

As detailed in , the uncertainty relation in \frefcor:uncertainty generalizes the uncertainty relation for two orthonormal bases (ONBs) found in . Furthermore, it extends the uncertainty relations provided in for pairs of square dictionaries (having the same number of rows and columns) to pairs of general dictionaries $\mathbf{A}$ and $\mathbf{B}$.

III-B Tightness of the uncertainty relation

In certain special cases it is possible to find signals that satisfy the uncertainty relation \frefeq:uncertaintyconcentrated with equality. As in , consider $\mathbf{A}=\mathbf{F}_{M}$ and $\mathbf{B}=\mathbf{I}_{M}$, so that $\mu_{m}=1/\sqrt{M}$, and define the comb signal containing equidistant spikes of unit height as

where we shall assume that $t$ divides $M$. It can be shown that the vectors $\mathbf{p}=\bm{\delta}_{\sqrt{M}}$ and $\mathbf{q}=\bm{\delta}_{\sqrt{M}}$, both having $\sqrt{M}$ nonzero entries, satisfy $\mathbf{F}_{M}\mathbf{p}=\mathbf{I}_{M}\mathbf{q}$. If $\mathcal{P}=\textrm{supp}(\mathbf{p})$ and $\mathcal{Q}=\textrm{supp}(\mathbf{q})$, the vectors $\mathbf{p}$ and $\mathbf{q}$ are perfectly concentrated to $\mathcal{P}$ and $\mathcal{Q}$, respectively, i.e., $\epsilon_{\mathcal{P}}=\epsilon_{\mathcal{Q}}=0$. Since $\mathopen{}\left\lvert\mathcal{P}\right\rvert=\mathopen{}\left\lvert\mathcal{Q}\right\rvert=\sqrt{M}$ and $\mu_{m}=1/\sqrt{M}$ it follows that $\mathopen{}\left\lvert\mathcal{P}\right\rvert\mathopen{}\left\lvert\mathcal{Q}\right\rvert=1/\mu_{m}^{2}=M$ and, hence, $\mathbf{p}=\mathbf{q}=\bm{\delta}_{\sqrt{M}}$ satisfies \frefeq:uncertaintyconcentrated with equality.

We will next show that for pairs of general dictionaries $\mathbf{A}$ and $\mathbf{B}$, finding signals that satisfy the uncertainty relation \frefeq:uncertaintyconcentrated with equality is NP-hard. For the sake of simplicity, we restrict ourselves to the case $\mathcal{P}=\textrm{supp}(\mathbf{p})$ and $\mathcal{Q}=\textrm{supp}(\mathbf{q})$, which implies $\mathopen{}\left\lvert\mathcal{P}\right\rvert=\mathopen{}\left\lVert\mathbf{p}\right\rVert_{0}$ and $\mathopen{}\left\lvert\mathcal{Q}\right\rvert=\mathopen{}\left\lVert\mathbf{q}\right\rVert_{0}$. Next, consider the problem

where $\mathbf{x}=\mathbf{p}/q$. However, as $(\textrm{U}0^{*})$ is equivalent to (P0), which is NP-hard , in general, we can conclude that finding a pair $\mathbf{p}$ and $\mathbf{q}$ satisfying the uncertainty relation (10) with equality is NP-hard.

IV Recovery of Sparsely Corrupted Signals

In the remainder of the paper, $\mathcal{X}$ denotes $\textrm{supp}(\mathbf{x})$ and $\mathcal{E}$ stands for $\textrm{supp}(\mathbf{e})$. We furthermore assume that the dictionaries $\mathbf{A}$ and $\mathbf{B}$ are known perfectly to the recovery algorithms. Moreover, we assume thatIf $\mu_{m}=0$, the space spanned by the columns of $\mathbf{A}$ is orthogonal to the space spanned by the columns of $\mathbf{B}$. This makes the separation of the components $\mathbf{A}\mathbf{x}$ and $\mathbf{B}\mathbf{e}$ given $\mathbf{z}$ straightforward. Once this separation is accomplished, $\mathbf{x}$ can be recovered from $\mathbf{A}\mathbf{x}$ using (P0), BP, or OMP, if \frefeq:classicalthreshold is satisfied. $\mu_{m}>0$.

We start with the case where both $\mathcal{X}$ and $\mathcal{E}$ are known prior to recovery. The values of the nonzero entries of $\mathbf{x}$ and $\mathbf{e}$ are unknown. This scenario is relevant, for example, in applications requiring recovery of clipped band-limited signals with known spectral support $\mathcal{X}$. Here, we would have $\mathbf{A}=\mathbf{F}_{M}$, $\mathbf{B}=\mathbf{I}_{M}$, and $\mathcal{E}$ can be determined as follows: Compare the measurements $[\mathbf{z}]_{i}$, $i=1,\ldots,M$, to the clipping threshold $a$; if $\mathopen{}\left\lvert[\mathbf{z}]_{i}\right\rvert=a$ add the corresponding index $i$ to $\mathcal{E}$.

Recovery of $\mathbf{x}$ from $\mathbf{z}$ is then performed as follows. We first rewrite the input-output relation in \frefeq:systemmodel as

with the concatenated dictionary $\mathbf{D}_{\mathcal{X},\mathcal{E}}=\left[\,\mathbf{A}_{\mathcal{X}}\,\,\mathbf{B}_{\mathcal{E}}\,\right]$ and the stacked vector \mathbf{s}_{\mathcal{X},\mathcal{E}}=\big{[}\,\mathbf{x}_{\mathcal{X}}^{T}\,\,\mathbf{e}_{\mathcal{E}}^{T}\,\big{]}^{T}. Since $\mathcal{X}$ and $\mathcal{E}$ are known, we can recover the stacked vector \mathbf{s}_{\mathcal{X},\mathcal{E}}=\big{[}\,\mathbf{x}_{\mathcal{X}}^{T}\,\,\mathbf{e}_{\mathcal{E}}^{T}\,\big{]}^{T}, perfectly and, hence, the nonzero entries of both $\mathbf{x}$ and $\mathbf{e}$, if the pseudo-inverse $\mathbf{D}^{\dagger}_{\mathcal{X},\mathcal{E}}$ exists. In this case, we can obtain $\mathbf{s}_{\mathcal{X},\mathcal{E}}$, as

The following theorem states a sufficient condition for $\mathbf{D}_{\mathcal{X},\mathcal{E}}$ to have full (column) rank, which implies existence of the pseudo-inverse $\mathbf{D}^{\dagger}_{\mathcal{X},\mathcal{E}}$. This condition depends on the coherence parameters $\mu_{a}$, $\mu_{b}$, and $\mu_{m}$, of the involved dictionaries $\mathbf{A}$ and $\mathbf{B}$ and on $\mathcal{X}$ and $\mathcal{E}$ through the cardinalities $\mathopen{}\left\lvert\mathcal{X}\right\rvert$ and $\mathopen{}\left\lvert\mathcal{E}\right\rvert$, i.e., the number of nonzero entries in $\mathbf{x}$ and $\mathbf{e}$, respectively.

Let $\mathbf{z}=\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{e}$ with $\mathcal{X}=\textrm{supp}(\mathbf{x})$ and $\mathcal{E}=\textrm{supp}(\mathbf{e})$. Define $n_{x}=\mathopen{}\left\lVert\mathbf{x}\right\rVert_{0}$ and $n_{e}=\mathopen{}\left\lVert\mathbf{e}\right\rVert_{0}$. If

then the concatenated dictionary $\mathbf{D}_{\mathcal{X},\mathcal{E}}=\left[\,\mathbf{A}_{\mathcal{X}}\,\,\mathbf{B}_{\mathcal{E}}\,\right]$ has full (column) rank.

For the special case $\mathbf{A}=\mathbf{F}_{M}$ and $\mathbf{B}=\mathbf{I}_{M}$ (so that $\mu_{a}=\mu_{b}=0$ and $\mu_{m}=1/\sqrt{M}$) the recovery condition \frefeq:P1_bothknown_assump reduces to $n_{x}n_{e}<M$, a result obtained previously in . Tightness of \frefeq:P1_bothknown_assump can be established by noting that the pairs $\mathbf{x}=\lambda\bm{\delta}_{\sqrt{M}}$, $\mathbf{e}=(1-\lambda)\bm{\delta}_{\sqrt{M}}$ with $\lambda\in(0,1)$ and $\mathbf{x}^{\prime}=\lambda^{\prime}\bm{\delta}_{\sqrt{M}}$, $\mathbf{e}^{\prime}=(1-\lambda^{\prime})\bm{\delta}_{\sqrt{M}}$ with $\lambda^{\prime}\neq\lambda$ and $\lambda^{\prime}\in(0,1)$ both satisfy \frefeq:P1_bothknown_assump with equality and lead to the same measurement outcome $\mathbf{z}=\mathbf{F}_{M}\mathbf{x}+\mathbf{e}=\mathbf{F}_{M}\mathbf{x}^{\prime}+\mathbf{e}^{\prime}$ .

It is interesting to observe that \frefthm:P1_bothknown yields a sufficient condition on $n_{x}$ and $n_{e}$ for any $(M-n_{e})\times n_{x}$-submatrix of $\mathbf{A}$ to have full (column) rank. To see this, consider the special case $\mathbf{B}=\mathbf{I}_{M}$ and hence, $\mathbf{D}_{\mathcal{X},\mathcal{E}}=\left[\,\mathbf{A}_{\mathcal{X}}\,\,\mathbf{I}_{\mathcal{E}}\,\right]$. Condition \frefeq:P1_bothknown_assump characterizes pairs ($n_{x},n_{e}$), for which all matrices $\mathbf{D}_{\mathcal{X},\mathcal{E}}$ with $n_{x}=\mathopen{}\left\lvert\mathcal{X}\right\rvert$ and $n_{e}=\mathopen{}\left\lvert\mathcal{E}\right\rvert$ are guaranteed to have full (column) rank. Hence, the sub-matrix consisting of all rows of $\mathbf{A}_{\mathcal{X}}$ with row index in $\mathcal{E}^{c}$ must have full (column) rank as well. Since the result holds for all support sets $\mathcal{X}$ and $\mathcal{E}$ with $\mathopen{}\left\lvert\mathcal{X}\right\rvert=n_{x}$ and $\mathopen{}\left\lvert\mathcal{E}\right\rvert=n_{e}$, all possible $(M-n_{e})\times n_{x}$-submatrices of $\mathbf{A}$ must have full (column) rank.

IV-B Case II: Only 𝒳𝒳\mathcal{X} or only ℰℰ\mathcal{E} is known

Next, we find recovery guarantees for the case where either only $\mathcal{X}$ or only $\mathcal{E}$ is known prior to recovery.

A prominent application for this setup is the recovery of clipped band-limited signals , where the signal’s spectral support, i.e., $\mathcal{X}$, is unknown. The support set $\mathcal{E}$ can be identified as detailed previously in \frefsec:bothknown. Further application examples for this setup include inpainting and super-resolution of signals that admit a sparse representation in $\mathbf{A}$ (but with unknown support set $\mathcal{X}$). The locations of the missing elements in $\mathbf{y}=\mathbf{A}\mathbf{x}$ are known (and correspond, e.g., to missing paint elements in frescos), i.e., the set $\mathcal{E}$ can be determined prior to recovery. Inpainting and super-resolution then amount to reconstructing the vector $\mathbf{x}$ from the sparsely corrupted measurement $\mathbf{z}=\mathbf{A}\mathbf{x}+\mathbf{e}$ and computing $\mathbf{y}=\mathbf{A}\mathbf{x}$.

The setting of $\mathcal{E}$ known and $\mathcal{X}$ unknown was considered previously in for the special case $\mathbf{A}=\mathbf{F}_{M}$ and $\mathbf{B}=\mathbf{I}_{M}$. The recovery condition \frefeq:P0uk_assump in \frefthm:P0_uk below extends the result in [26, Thms. 5 and 9] to pairs of general dictionaries $\mathbf{A}$ and $\mathbf{B}$.

Let $\mathbf{z}=\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{e}$ where $\mathcal{E}=\textrm{supp}(\mathbf{e})$ is known. Consider the problem

If $n_{x}=\mathopen{}\left\lVert\mathbf{x}\right\rVert_{0}$ and $n_{e}=\mathopen{}\left\lVert\mathbf{e}\right\rVert_{0}$ satisfy

then the unique solution of $(\textrm{P0},\mathcal{E})$ applied to $\mathbf{z}=\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{e}$ is given by $\mathbf{x}$ and $(\textrm{BP},\mathcal{E})$ will deliver this solution.

Tightness of \frefeq:P0uk_assump can be established by setting $\mathbf{A}=\mathbf{F}_{M}$ and $\mathbf{B}=\mathbf{I}_{M}$. Specifically, the pairs $\mathbf{x}=\bm{\delta}_{2\sqrt{M}}-\bm{\delta}_{\sqrt{M}}$, $\mathbf{e}=\bm{\delta}_{\sqrt{M}}$ and $\mathbf{x}^{\prime}=\bm{\delta}_{2\sqrt{M}}$, $\mathbf{e}^{\prime}=\mathbf{e}$ both satisfy \frefeq:P0uk_assump with equality. One can furthermore verify that $\mathbf{x}$ and $\mathbf{x}^{\prime}$ are both in the admissible set specified by the constraints in $(\textrm{P0},\mathcal{E})$ and $(\textrm{BP},\mathcal{E})$ and $\mathopen{}\left\lVert\mathbf{x}^{\prime}\right\rVert_{0}=\mathopen{}\left\lVert\mathbf{x}\right\rVert_{0}$, $\mathopen{}\left\lVert\mathbf{x}^{\prime}\right\rVert_{1}=\mathopen{}\left\lVert\mathbf{x}\right\rVert_{1}$. Hence, $(\textrm{P0},\mathcal{E})$ and $(\textrm{BP},\mathcal{E})$ both cannot distinguish between $\mathbf{x}$ and $\mathbf{x}^{\prime}$ based on the measurement outcome $\mathbf{z}$. For a detailed discussion of this example we refer to .

Rather than solving $(\textrm{P0},\mathcal{E})$ or $(\text{BP},\mathcal{E})$, we may attempt to recover the vector $\mathbf{x}$ by exploiting more directly the fact that $\mathcal{R}(\mathbf{B}_{\mathcal{E}})$ is known (since $\mathbf{B}$ and $\mathcal{E}$ are assumed to be known) and projecting the measurement outcome $\mathbf{z}$ onto the orthogonal complement of $\mathcal{R}(\mathbf{B}_{\mathcal{E}})$. This approach would eliminate the (sparse) noise component and leave us with a standard sparse-signal recovery problem for the vector $\mathbf{x}$. We next show that this ansatz is guaranteed to recover the sparse vector $\mathbf{x}$ provided that condition (22) is satisfied. Let us detail the procedure. If the columns of $\mathbf{B}_{\mathcal{E}}$ are linearly independent, the pseudo-inverse $\mathbf{B}^{\dagger}_{\mathcal{E}}$ exists, and the projector onto the orthogonal complement of $\mathcal{R}(\mathbf{B}_{\mathcal{E}})$ is given by

Applying $\mathbf{R}_{\mathcal{E}}$ to the measurement outcome $\mathbf{z}$ yields

where $\mathbf{\Delta}$ is the diagonal matrix with elements

If \frefeq:P0uk_assump is satisfied, the unique solution of (P0) applied to $\hat{\mathbf{z}}=\mathbf{R}_{\mathcal{E}}\mathbf{A}\mathbf{\Delta}\hat{}\mathbf{x}$ is given by $\hat{}\mathbf{x}$. Furthermore, BP and OMP applied to $\hat{\mathbf{z}}=\mathbf{R}_{\mathcal{E}}\mathbf{A}\mathbf{\Delta}\hat{}\mathbf{x}$ are guaranteed to recover the unique (P0)-solution.

thm:P1uk_equivalence generalizes the results in [26, Thms. 5 and 9] obtained for the special case $\mathbf{A}=\mathbf{F}_{M}$ and $\mathbf{B}=\mathbf{I}_{M}$ to pairs of general dictionaries and additionally shows that OMP delivers the correct solution provided that \frefeq:P0uk_assump is satisfied.

It follows from \frefeq:projectednormalizeddict that other sparse-signal recovery algorithms, such as iterative thresholding-based algorithms , CoSaMP , or subspace pursuit can be applied to recover $\mathbf{x}$.Finding analytical recovery guarantees for these algorithms remains an interesting open problem. Finally, we note that the idea of projecting the measurement outcome onto the orthogonal complement of the space spanned by the active columns of $\mathbf{B}$ and investigating the effect on the RICs, instead of the coherence parameter $\mu_{a}$ (as was done in \frefapp:effectivecoherence) was put forward in along with RIC-based recovery guarantees that apply to random matrices $\mathbf{A}$ and guarantee the recovery of $\mathbf{x}$ with high probability (with respect to $\mathbf{A}$ and irrespective of the locations of the sparse corruptions).

IV-B2 Recovery when 𝒳𝒳\mathcal{X} is known and ℰℰ\mathcal{E} is unknown

A possible application scenario for this situation is the recovery of spectrally sparse signals with known spectral support that are impaired by impulse noise with unknown impulse locations.

Let $\mathbf{z}=\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{e}$ where $\mathcal{X}=\textrm{supp}(\mathbf{x})$ is known. If the number of nonzero entries in $\mathbf{x}$ and $\mathbf{e}$, i.e., $n_{x}=\mathopen{}\left\lVert\mathbf{x}\right\rVert_{0}$ and $n_{e}=\mathopen{}\left\lVert\mathbf{e}\right\rVert_{0}$, satisfy

then the unique solution of (P0) applied to $\hat{\mathbf{z}}^{\prime}=\mathbf{R}_{\mathcal{X}}\mathbf{B}\mathbf{\Delta}^{\prime}\hat{}\mathbf{e}$ is given by $\hat{}\mathbf{e}=(\mathbf{\Delta}^{\prime})^{-1}\,\mathbf{e}$. Furthermore, BP and OMP applied to $\hat{\mathbf{z}}^{\prime}=\mathbf{R}_{\mathcal{X}}\mathbf{B}\mathbf{\Delta}^{\prime}\hat{}\mathbf{e}$ recover the unique (P0)-solution.

Once we have $\hat{}\mathbf{e}$, the vector $\mathbf{e}$ can be obtained easily, since $\mathbf{e}=\mathbf{\Delta}^{\prime}\hat{}\mathbf{e}$ and the nonzero entries of $\mathbf{x}$ are given by

Since (26) ensures that the columns of $\mathbf{A}_{\mathcal{X}}$ are linearly independent, the pseudo-inverse $\mathbf{A}^{\dagger}_{\mathcal{X}}$ is guaranteed to exist. Note that tightness of the recovery condition \frefeq:P1signaluk_assump can be established analogously to the case of $\mathcal{E}$ known and $\mathcal{X}$ unknown (discussed in \frefsec:Eknown).

IV-C Case III: Cardinality of ℰℰ\mathcal{E} or 𝒳𝒳\mathcal{X} known

We next consider the case where neither $\mathcal{X}$ nor $\mathcal{E}$ are known, but knowledge of either $\mathopen{}\left\lVert\mathbf{x}\right\rVert_{0}$ or $\mathopen{}\left\lVert\mathbf{e}\right\rVert_{0}$ is available (prior to recovery). An application scenario for $\mathopen{}\left\lVert\mathbf{x}\right\rVert_{0}$ unknown and $\mathopen{}\left\lVert\mathbf{e}\right\rVert_{0}$ known would be the recovery of a sparse pulse-stream with unknown pulse-locations from measurements that are corrupted by electric hum with unknown base-frequency but known number of harmonics (e.g., determined by the base frequency of the hum and the acquisition bandwidth of the system under consideration). We state our main result for the case $n_{e}=\mathopen{}\left\lVert\mathbf{e}\right\rVert_{0}$ known and $n_{x}=\mathopen{}\left\lVert\mathbf{x}\right\rVert_{0}$ unknown. The case where $n_{x}$ is known and $n_{e}$ is unknown can be treated similarly.

Let $\mathbf{z}=\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{e}$, define $n_{x}=\mathopen{}\left\lVert\mathbf{x}\right\rVert_{0}$ and $n_{e}=\mathopen{}\left\lVert\mathbf{e}\right\rVert_{0}$, and assume that $n_{e}$ is known. Consider the problem

where $\mathscr{P}=\wp_{n_{e}}(\{1,\ldots,{N_{b}}\})$ denotes the set of subsets of $\{1,\ldots,{N_{b}}\}$ of cardinality less than or equal to $n_{e}$. The unique solution of ($\textrm{P0},n_{e}$) applied to $\mathbf{z}=\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{e}$ is given by $\mathbf{x}$ if

We finally note that tightness of \frefeq:P0_nothingknown_assump can be established for $\mathbf{A}=\mathbf{F}_{M}$ and $\mathbf{B}=\mathbf{I}_{M}$. Specifically, consider the pair $\mathbf{x}=\bm{\delta}_{2\sqrt{M}}$, $\mathbf{e}=-\bm{\delta}_{2\sqrt{M}}$ and the alternative pair $\mathbf{x}^{\prime}=\bm{\delta}_{2\sqrt{M}}-\bm{\delta}_{\sqrt{M}}$, $\mathbf{e}^{\prime}=-\bm{\delta}_{2\sqrt{M}}+\bm{\delta}_{\sqrt{M}}$. It can be shown that both $\mathbf{x}$ and $\mathbf{x}^{\prime}$ are in the admissible set of $(\textrm{P0},\,n_{e})$ in (29), satisfy $\mathopen{}\left\lVert\mathbf{x}^{\prime}\right\rVert_{0}=\mathopen{}\left\lVert\mathbf{x}\right\rVert_{0}$, and lead to the same measurement outcome $\mathbf{z}$. Therefore, (P0, $n_{e}$) cannot distinguish between $\mathbf{x}$ and $\mathbf{x}^{\prime}$ (we refer to for details).

IV-D Case IV: No knowledge about the support sets

Finally, we consider the case of no knowledge (prior to recovery) about the support sets $\mathcal{X}$ and $\mathcal{E}$. A corresponding application scenario would be the restoration of an audio signal (whose spectrum is sparse with unknown support set) that is corrupted by impulse noise, e.g., click or pop noise occurring at unknown locations. Another typical application can be found in the realm of signal separation; e.g., the decomposition of images into two distinct features, i.e., into a part that exhibits a sparse representation in the dictionary $\mathbf{A}$ and another part that exhibits a sparse representation in $\mathbf{B}$. Decomposition of the image $\mathbf{z}$ then amounts to performing sparse-signal recovery based on $\mathbf{z}=\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{e}$ with no knowledge about the support sets $\mathcal{X}$ and $\mathcal{E}$ available prior to recovery. The individual image features are given by $\mathbf{A}\mathbf{x}$ and $\mathbf{B}\mathbf{e}$.

Recovery guarantees for this case follow from the results in . Specifically, by rewriting (1) as $\mathbf{z}=\mathbf{D}\mathbf{w}$ as in \frefeq:simpleconcatenation, we can employ the recovery guarantees in , which are explicit in the coherence parameters $\mu_{a}$ and $\mu_{b}$, and the dictionary coherence $\mu_{d}$ of $\mathbf{D}$. For the sake of completeness, we restate the following result from .

Let $\mathbf{z}=\mathbf{D}\mathbf{w}$ with $\mathbf{w}=[\,\mathbf{x}^{T}\,\,\mathbf{e}^{T}\,]^{T}$ and $\mathbf{D}=[\,\mathbf{A}\,\,\mathbf{B}\,]$ with the coherence parameters $\mu_{a}\leq\mu_{b}$ and the dictionary coherence $\mu_{d}$ as defined in \frefeq:coherenceAB. A sufficient condition for the vector $\mathbf{w}$ to be the unique solution of (P0) applied to $\mathbf{z}=\mathbf{D}\mathbf{w}$ is

and $\hat{x}=\min\{x_{b},x_{s}\}$. Furthermore, $x_{b}=(1+\mu_{b})/(\mu_{b}+\mu_{d}^{2})$ and

Obviously, once the vector $\mathbf{w}$ has been recovered, we can extract $\mathbf{x}$ and $\mathbf{e}$. The following theorem, originally stated in , guarantees that BP and OMP deliver the unique solution of (P0) applied to $\mathbf{z}=\mathbf{D}\mathbf{w}$ and the associated recovery threshold, as shown in , is only slightly more restrictive than that for (P0) in \frefeq:P0bound.

A sufficient condition for BP and OMP to deliver the unique solution of (P0) applied to $\mathbf{z}=\mathbf{D}\mathbf{w}$ is given by

where $\delta=1+\mu_{b}$ and $\epsilon=2\sqrt{2}\sqrt{\mu_{d}(\mu_{b}+\mu_{d})}$.

We emphasize that both thresholds \frefeq:P0bound and \frefeq:l1_final are more restrictive than those in (15), (22), (26), and (30) (see also \frefsec:factortwoinguarantees), which is consistent with the intuition that additional knowledge about the support sets $\mathcal{X}$ and $\mathcal{E}$ should lead to higher recovery thresholds. Note that tightness of \frefeq:P0bound and \frefeq:l1_final was established before in and , respectively.

V Discussion of the Recovery Guarantees

The aim of this section is to provide an interpretation of the recovery guarantees found in \frefsec:main. Specifically, we discuss the impact of support-set knowledge on the recovery thresholds we found, and we point out limitations of our results.

Comparing the recovery thresholds (15), (22), (26), and (30) (Cases I–III), we observe that the price to be paid for not knowing the support set $\mathcal{X}$ or $\mathcal{E}$ is a reduction of the recovery threshold by a factor of two (note that in Case III, both $\mathcal{X}$ and $\mathcal{E}$ are unknown, but the cardinality of either $\mathcal{X}$ or $\mathcal{E}$ is known). For example, consider the recovery thresholds (15) and (22). For given $n_{e}\in[0,1+1/\mu_{b}]$, solving (15) for $n_{x}$ yields

Similarly, still assuming $n_{e}\in[0,1+1/\mu_{b}]$ and solving (22) for $n_{x}$, we get

Hence, knowledge of $\mathcal{X}$ prior to recovery allows for the recovery of a signal with twice as many nonzero entries in $\mathbf{x}$ compared to the case where $\mathcal{X}$ is not known. This factor-of-two penalty has the same roots as the well-known factor-of-two penalty in spectrum-blind sampling . Note that the same factor-of-two penalty can be inferred from the RIC-based recovery guarantees in , when comparing the recovery threshold specified in [39, Thm. 1] for signals where partial support-set knowledge is available (prior to recovery) to that given in [15, Thm. 1.1] which does not assume prior support-set knowledge.

We illustrate the factor-of-two penalty in Figs. 1 and 2, where the recovery thresholds (15), (22), (26), (30), and \frefeq:l1_final are shown. In \freffig:th_th_ONB, we consider the case $\mu_{a}=\mu_{b}=0$ and $\mu_{m}=1/\sqrt{64}$. We can see that for $\mathcal{X}$ and $\mathcal{E}$ known the threshold evaluates to $n_{x}n_{e}<64$. When only $\mathcal{X}$ or $\mathcal{E}$ is known we have $n_{x}n_{e}<32$, and finally in the case where only $n_{e}$ is known we get $n_{x}n_{e}<16$. Note furthermore that in Case IV, where no knowledge about the support sets is available, the recovery threshold is more restrictive than in the case where $n_{e}$ is known.

In \freffig:th_th_sym, we show the recovery thresholds for $\mu_{a}=0.1258$, $\mu_{b}=0.1319$, and $\mu_{m}=0.1321$. We see that all threshold curves are straight lines. This behavior can be explained by noting that (in contrast to the assumptions underlying \freffig:th_th_ONB) the dictionaries $\mathbf{A}$ and $\mathbf{B}$ have $\mu_{a},\mu_{b}>0$ and the corresponding recovery thresholds are essentially dominated by the numerator of the RHS expressions in (15), (22), (26), and \frefeq:P0_nothingknown_assump, which depends on both $n_{x}$ and $n_{e}$. More concretely, if $\mu_{a}=\mu_{b}=\mu_{m}=\mu_{d}>0$, then the recovery threshold for Case II (where the support set $\mathcal{E}$ is known) becomes

which reflects the behavior observed in \freffig:th_th_sym.

V-B The square-root bottleneck

The recovery thresholds presented in \frefsec:main hold for all signal and noise realizations $\mathbf{x}$ and $\mathbf{e}$ and for all dictionary pairs (with given coherence parameters). However, as is well-known in the sparse-signal recovery literature, coherence-based recovery guarantees are—in contrast to RIC-based recovery guarantees—fundamentally limited by the so-called square-root bottleneck . More specifically, in the noiseless case (i.e., for $\mathbf{e}=\mathbf{0}_{N_{b}}$), the threshold (4) states that recovery can be guaranteed only for up to $\sqrt{M}$ nonzero entries in $\mathbf{x}$. Put differently, for a fixed number of nonzero entries $n_{x}$ in $\mathbf{x}$, i.e., for a fixed sparsity level, the number of measurements $M$ required to recover $\mathbf{x}$ through (P0), BP, or OMP is on the order of $n_{x}^{2}$.

As in the classical sparse-signal recovery literature, the square-root bottleneck can be broken by performing a probabilistic analysis . This line of work—albeit interesting—is outside the scope of the present paper and is further investigated in .

VI Numerical Results

We first compare simulation results to the recovery thresholds (15), (22), (26), and \frefeq:l1_final. For a given pair of dictionaries $\mathbf{A}$ and $\mathbf{B}$ we generate signal vectors $\mathbf{x}$ and error vectors $\mathbf{e}$ as follows: We first fix $n_{x}$ and $n_{e}$, then the support sets of the $n_{x}$-sparse vector $\mathbf{x}$ and the $n_{e}$-sparse vector $\mathbf{e}$ are chosen uniformly at random among all possible support sets of cardinality $n_{x}$ and $n_{e}$, respectively. Once the support sets have been chosen, we generate the nonzero entries of $\mathbf{x}$ and $\mathbf{e}$ by drawing from i.i.d. zero mean, unit variance Gaussian random variables. For each pair of support-set cardinalities $n_{x}$ and $n_{e}$, we perform 10 000 Monte-Carlo trials and declare success of recovery whenever the recovered vector $\hat{\mathbf{x}}$ satisfies

We plot the 50% success-rate contour, i.e., the border between the region of pairs ($n_{x}$, $n_{e}$) for which (36) is satisfied in at least 50% of the trials and the region where (36) is satisfied in less than 50% of the trials. The recovered vector $\hat{}\mathbf{x}$ is obtained as follows:

Case I: When $\mathcal{X}$ and $\mathcal{E}$ are both known, we perform recovery according to (14).

Case II: When either only $\mathcal{E}$ or only $\mathcal{X}$ is known, we apply BP and OMP using the modified dictionary as detailed in \frefthm:P1uk_equivalence and \frefcor:P1_signal_known, respectively.

Case IV: When neither $\mathcal{X}$ nor $\mathcal{E}$ is known, we apply BP and OMP to the concatenated dictionary $\mathbf{D}=[\,\mathbf{A}\,\,\mathbf{B}\,]$ as described in \frefthm:l1_general.

Note that for Case III, i.e., the case where the cardinality $n_{e}$ of the support set $\mathcal{E}$ is known—as pointed out in \frefsec:cardinalityKnown—we only have uniqueness results but no analytical recovery guarantees, neither for BP nor for greedy recovery algorithms that make use of the separate knowledge of $n_{x}$ or $n_{e}$ (whereas, e.g., standard OMP makes use of knowledge of $n_{x}+n_{e}$, rather than knowledge of $n_{x}$ and $n_{e}$ individually). This case is, therefore, not considered in the simulation results below.

We take $M=64$, let $\mathbf{A}$ be the Hadamard ONB and set $\mathbf{B}=\mathbf{I}_{M}$, which results in $\mu_{a}=\mu_{b}=0$ and $\mu_{m}=1/\sqrt{M}$. \freffig:pt_bpvsomp shows 50% success-rate contours, under different assumptions of support-set knowledge. For perfect knowledge of $\mathcal{X}$ and $\mathcal{E}$, we observe that the 50% success-rate contour is at about $n_{x}+n_{e}\approx M$, which is significantly better than the sufficient condition $n_{x}n_{e}<M$ (guaranteeing perfect recovery) provided in (15).For $\mathbf{A}=\mathbf{F}_{M}$ and $\mathbf{B}=\mathbf{I}_{M}$ it was proven in that a set of columns chosen randomly from both $\mathbf{A}$ and $\mathbf{B}$ is linearly independent (with high probability) given that the total number of chosen columns, i.e., $n_{x}+n_{e}$ here, does not exceed a constant proportion of $M$. When either only $\mathcal{X}$ or only $\mathcal{E}$ is known, the recovery performance is essentially independent of whether $\mathcal{X}$ or $\mathcal{E}$ is known. This is also reflected by the analytical thresholds (22) and (26) when evaluated for $\mu_{a}=\mu_{b}=0$ (see also \freffig:th_th_ONB). Furthermore, OMP is seen to outperform BP. When neither $\mathcal{X}$ nor $\mathcal{E}$ is known, OMP again outperforms BP.

It is interesting to see that the factor-of-two penalty discussed in \frefsec:factortwoinguarantees is reflected in \freffig:pt_bpvsomp (for $n_{x}=n_{e}$) between Cases I and II. Specifically, we can observe that for full support-set knowledge (Case I) the 50% success-rate is achieved at $n_{x}=n_{e}\approx 31$. If either $\mathcal{X}$ or $\mathcal{E}$ only is known (Case II), OMP achieves 50% success-rate at $n_{x}=n_{e}\approx 23$, demonstrating a factor-of-two penalty since $31\cdot 31\approx 23\cdot 23\cdot 2$. Note that the results from BP in \freffig:pt_bpvsomp do not seem to reflect the factor-of-two penalty. For lack of an efficient recovery algorithm (making use of knowledge of $n_{e}$) we do not show numerical results for Case III.

We finally note that in all cases considered above, the numerical results show that recovery is possible for significantly higher sparsity levels $n_{x}$ and $n_{e}$ than indicated by the corresponding analytical thresholds (15), (22), (26), and \frefeq:l1_final (see also Figs. 1 and 2). The underlying reasons are i) the deterministic nature of the results, i.e., the recovery guarantees in (15), (22), (26), and \frefeq:l1_final are valid for all dictionary pairs (with given coherence parameters) and all signal and noise realizations (with given sparsity level), and ii) we plot the 50% success-rate contour, whereas the analytical results guarantee perfect recovery in 100% of the cases.

VI-B Inpainting example

In transform coding one is typically interested in maximally sparse representations of a given signal to be encoded . In our setting, this would mean that the dictionary $\mathbf{A}$ should be chosen so that it leads to maximally sparse representations of a given family of signals. We next demonstrate, however, that in the presence of structured noise, the signal dictionary $\mathbf{A}$ should additionally be incoherent to the noise dictionary $\mathbf{B}$. This extra requirement can lead to very different criteria for designing transform bases (frames).

Figs. 5 and 6 show the corresponding results. As expected, the MSE increases as the amount of knowledge about the support sets decreases. More interestingly, we note that even though Haar wavelets often yield a smaller approximation error in classical transform coding compared to the DCT, here the wavelet transform performs worse than the DCT. This behavior is due to the fact that sparsity is not the only factor determining the performance of a transform coding basis (or frame) in the presence of structured noise. Rather the mutual coherence between the dictionary used to represent the signal and that used to represent the structured noise becomes highly relevant. Specifically, in the example at hand, we have $\mu_{m}=1/2$ for the Haar-wavelet and the identity basis, and $\mu_{m}\approx 0.004$ for the DCT and the identity basis. The dependence of the analytical thresholds (15), (22), (26), (30), and \frefeq:l1_final on the mutual coherence $\mu_{m}$ explains the performance difference between the Haar wavelet basis and the DCT basis. An intuitive explanation for this behavior is as follows: The Haar-wavelet basis contains only four non-zero entries in the columns associated to fine scales, which is reflected in the high mutual coherence (i.e., $\mu_{m}=1/2$) between the Haar-wavelet basis and the identity basis. Thus, when projecting onto the orthogonal complement of $(\mathbf{I}_{M})_{\mathcal{E}}$, it is likely that all non-zero entries of such columns are deleted, resulting in columns of all zeros. Recovery of the corresponding non-zero entries of $\mathbf{x}$ is thus not possible. In summary, we see that the choice of the transform basis (frame) for a sparsely corrupted signal should not only aim at sparsifying the signal as much as possible but should also take into account the mutual coherence between the transform basis (frame) and the noise sparsity basis (frame).

VII Conclusion

The setup considered in this paper, in its generality, appears to be new and a number of interesting extensions are possible. In particular, developing (coherence-based) recovery guarantees for greedy algorithms such as CoSaMP or subspace pursuit for all cases studied in the paper are interesting open problems. Note that probabilistic recovery guarantees for the case where nothing is known about the signal and noise support sets (i.e., Case IV) readily follow from the results in . Probabilistic recovery guarantees for the other cases studied in this paper are in preparation . Furthermore, an extension of the results in this paper that accounts for measurement noise (in addition to sparse noise) and applies to approximately sparse signals can be found in .

Acknowledgments

The authors would like to thank C. Aubel, A. Bracher, and G. Durisi for interesting discussions, and the anonymous reviewers for their valuable comments which helped to improve the exposition.

Appendix A Proof of \frefthm:P1_bothknown

We prove the full (column-)rank property of $\mathbf{D}_{\mathcal{X},\mathcal{E}}$ by showing that under (15) there is a unique pair $(\mathbf{x},\mathbf{e})$ with $\textrm{supp}(\mathbf{x})=\mathcal{X}$ and $\textrm{supp}(\mathbf{e})=\mathcal{E}$ satisfying $\mathbf{z}=\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{e}$. Assume that there exists an alternative pair $(\mathbf{x}^{\prime},\mathbf{e}^{\prime})$ such that $\mathbf{z}=\mathbf{A}\mathbf{x}^{\prime}+\mathbf{B}\mathbf{e}^{\prime}$ with $\textrm{supp}(\mathbf{x}^{\prime})\subseteq\mathcal{X}$ and $\textrm{supp}(\mathbf{e}^{\prime})\subseteq\mathcal{E}$ (i.e., the support sets of $\mathbf{x}^{\prime}$ and $\mathbf{e}^{\prime}$ are contained in $\mathcal{X}$ and $\mathcal{E}$, respectively). This would then imply that

Since both $\mathbf{x}$ and $\mathbf{x}^{\prime}$ have support in $\mathcal{X}$ it follows that $\mathbf{x}-\mathbf{x}^{\prime}$ also has support in $\mathcal{X}$, which implies $\mathopen{}\left\lVert\mathbf{x}-\mathbf{x}^{\prime}\right\rVert_{0}\leq n_{x}$. Similarly, we get $\mathopen{}\left\lVert\mathbf{e}^{\prime}-\mathbf{e}\right\rVert_{0}\leq n_{e}$. Defining $\mathbf{p}=\mathbf{x}-\mathbf{x}^{\prime}$ and $\mathcal{P}=\textrm{supp}(\mathbf{x}-\mathbf{x}^{\prime})\subseteq\mathcal{X}$, and, similarly, $\mathbf{q}=\mathbf{e}^{\prime}-\mathbf{e}$ and $\mathcal{Q}=\textrm{supp}(\mathbf{e}^{\prime}-\mathbf{e})\subseteq\mathcal{E}$, we obtain the following chain of inequalities:

where (37) follows by applying the uncertainty relation in \frefthm:uncertainty (with $\epsilon_{\mathcal{P}}=\epsilon_{\mathcal{Q}}=0$ since both $\mathbf{p}$ and $\mathbf{q}$ are perfectly concentrated to $\mathcal{P}$ and $\mathcal{Q}$, respectively) and (38) is a consequence of $\mathopen{}\left\lvert\mathcal{P}\right\rvert\leq n_{x}$ and $\mathopen{}\left\lvert\mathcal{Q}\right\rvert\leq n_{e}$. Obviously, (38) contradicts the assumption in (15), which completes the proof.

Appendix B Proof of \frefthm:P0_uk

We begin by proving that $\mathbf{x}$ is the unique solution of $(\textrm{P0},\mathcal{E})$ applied to $\mathbf{z}=\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{e}$. Assume that there exists an alternative vector $\mathbf{x}^{\prime}$ that satisfies $\mathbf{A}\mathbf{x}^{\prime}\in(\{\mathbf{z}\}+\mathcal{R}(\mathbf{B}_{\mathcal{E}}))$ with $\mathopen{}\left\lVert\mathbf{x}^{\prime}\right\rVert_{0}\leq n_{x}$. This would imply the existence of a vector $\mathbf{e}^{\prime}$ with $\textrm{supp}(\mathbf{e}^{\prime})\subseteq\mathcal{E}$, such that

Since $\textrm{supp}(\mathbf{e})=\mathcal{E}$ and $\textrm{supp}(\mathbf{e}^{\prime})\subseteq\mathcal{E}$, we have $\textrm{supp}(\mathbf{e}^{\prime}-\mathbf{e})\subseteq\mathcal{E}$ and hence $\mathopen{}\left\lVert\mathbf{e}^{\prime}-\mathbf{e}\right\rVert_{0}\leq n_{e}$. Furthermore, since both $\mathbf{x}$ and $\mathbf{x}^{\prime}$ have at most $n_{x}$ nonzero entries, we have $\mathopen{}\left\lVert\mathbf{x}-\mathbf{x}^{\prime}\right\rVert_{0}\leq 2n_{x}$. Defining $\mathbf{p}=\mathbf{x}-\mathbf{x}^{\prime}$ and $\mathcal{P}=\textrm{supp}(\mathbf{x}-\mathbf{x}^{\prime})$, and, similarly, $\mathbf{q}=\mathbf{e}^{\prime}-\mathbf{e}$ and $\mathcal{Q}=\textrm{supp}(\mathbf{e}^{\prime}-\mathbf{e})\subseteq\mathcal{E}$, we obtain the following chain of inequalities

where (39) follows by applying the uncertainty relation in \frefthm:uncertainty (with $\epsilon_{\mathcal{P}}=\epsilon_{\mathcal{Q}}=0$ since both $\mathbf{p}$ and $\mathbf{q}$ are perfectly concentrated to $\mathcal{P}$ and $\mathcal{Q}$, respectively) and (40) is a consequence of $\mathopen{}\left\lvert\mathcal{P}\right\rvert\leq 2n_{x}$ and $\mathopen{}\left\lvert\mathcal{Q}\right\rvert\leq n_{e}$. Obviously, (40) contradicts the assumption in (22), which concludes the first part of the proof.

We next prove that $\mathbf{x}$ is also the unique solution of $(\textrm{BP},\mathcal{E})$ applied to $\mathbf{z}=\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{e}$. Assume that there exists an alternative vector $\mathbf{x}^{\prime}$ that satisfies $\mathbf{A}\mathbf{x}^{\prime}\in(\{\mathbf{z}\}+\mathcal{R}(\mathbf{B}_{\mathcal{E}}))$ with $\mathopen{}\left\lVert\mathbf{x}^{\prime}\right\rVert_{1}\leq\mathopen{}\left\lVert\mathbf{x}\right\rVert_{1}$. This would imply the existence of a vector $\mathbf{e}^{\prime}$ with $\textrm{supp}(\mathbf{e}^{\prime})\subseteq\mathcal{E}$, such that

where (42) follows from the uncertainty relation in \frefthm:uncertainty applied to the difference vectors $\mathbf{p}$ and $\mathbf{q}$ (with $\epsilon_{\mathcal{P}}\leq 0.5$ since $\mathbf{p}$ is at least 50%-concentrated to $\mathcal{P}$ and $\epsilon_{\mathcal{Q}}=0$ since $\mathbf{q}$ is perfectly concentrated to $\mathcal{Q}$) and (43) is a consequence of $\mathopen{}\left\lvert\mathcal{P}\right\rvert=n_{x}$ and $\mathopen{}\left\lvert\mathcal{Q}\right\rvert\leq n_{e}$. Rewriting (43), we obtain

Since (44) contradicts the assumption in (22), this proves that $\mathbf{x}$ is the unique solution of $(\textrm{BP},\mathcal{E})$ applied to $\mathbf{z}=\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{e}$.

Appendix C Proof of \frefthm:P1uk_equivalence

Condition (22) can only be satisfied if $\mathopen{}\left[1\!-\!\mu_{b}(n_{e}\!-\!1)\right]^{+}>0$, which implies that $n_{e}<1+1/\mu_{b}$. It was shown in that for a dictionary $\mathbf{B}$ with coherence $\mu_{b}$ no fewer than $1+1/\mu_{b}$ columns of $\mathbf{B}$ can be linearly dependent. Hence, the $n_{e}$ columns of $\mathbf{B}_{\mathcal{E}}$ must be linearly independent.

where (47) follows from the Rayleigh-Ritz theorem [60, Thm. 4.2.2] and (48) results from

Next, applying Geršgorin’s disc theorem [60, Theorem 6.1.1], we arrive at

C-C Unique recovery through (P0), BP, and OMP

We now need to verify that (P0), BP, and OMP (applied to $\hat{}\mathbf{z}=\mathbf{R}_{\mathcal{E}}\mathbf{A}\mathbf{\Delta}\hat{}\mathbf{x}$) recover the vector $\hat{\mathbf{x}}=\mathbf{\Delta}^{\!-1}\mathbf{x}$ provided that (22) is satisfied. This will be accomplished by deriving an upper bound on the coherence $\mu(\mathbf{R}_{\mathcal{E}}\mathbf{A}\mathbf{\Delta})$ of the modified dictionary $\mathbf{R}_{\mathcal{E}}\mathbf{A}\mathbf{\Delta}$, which, via the well-known coherence-based recovery guarantee

leads to a recovery threshold guaranteeing perfect recovery of $\hat{\mathbf{x}}$. This threshold is then shown to coincide with (22). More specifically, the well-known sparsity threshold in (4) guarantees that the unique solution of (P0) applied to $\hat{}\mathbf{z}=\mathbf{R}_{\mathcal{E}}\mathbf{A}\mathbf{\Delta}\hat{}\mathbf{x}$ is given by $\hat{}\mathbf{x}$, and, furthermore, that this unique solution can be obtained through BP and OMP if \frefeq:modifiedDictRecovery holds. It is important to note that $\mathopen{}\left\lVert\hat{\mathbf{x}}\right\rVert_{0}=\mathopen{}\left\lVert\mathbf{x}\right\rVert_{0}=n_{x}$. With

Next, we upper-bound the RHS of \frefeq:equivalence_1 by upper-bounding its numerator and lower-bounding its denominator. For the numerator we have

where (56) follows from the Cauchy-Schwarz inequality and (57) from the Rayleigh-Ritz theorem [60, Thm. 4.2.2]. Defining $i=\operatorname*{arg\;max}_{r}\mathopen{}\left\lVert\mathbf{B}_{\mathcal{E}}^{H}\mathbf{a}_{r}\right\rVert_{2}$, we further have

We obtain an upper bound on $C_{2}$ using the same steps that were used to bound $C_{1}$ in (47) – (49):

where $C_{b}=\mathopen{}\left[1-\mu_{b}(n_{e}-1)\right]^{+}$. Combining \frefeq:equivalence_bound1 and \frefeq:C2bound leads to the following upper bound

Next, we derive a lower bound on the denominator on the RHS of (52). To this end, we set $j=\operatorname*{arg\;min}_{r}\mathopen{}\left\lVert\mathbf{R}_{\mathcal{E}}\mathbf{a}_{r}\right\rVert_{2}$ and note that

where (60) follows from (50). Finally, combining (59) and (60) we arrive at

Inserting (61) into the recovery threshold in (51), we obtain the following threshold guaranteeing recovery of $\hat{}\mathbf{x}$ from $\hat{\mathbf{z}}=\mathbf{R}_{\mathcal{E}}\mathbf{A}\mathbf{\Delta}\hat{\mathbf{x}}$ through $(\textrm{P0})$, BP, and OMP:

Since $2n_{x}n_{e}\,\mu_{m}^{2}\geq 0$, we can transform (62) into

which proves that (22) guarantees recovery of the vector $\hat{\mathbf{x}}$ (and thus also of $\mathbf{x}=\mathbf{\Delta}\hat{\mathbf{x}}$) through (P0), BP, and OMP.

Appendix D Proof of \frefthm:P0_nothingknown

Assume that there exists an alternative vector $\mathbf{x}^{\prime}$ that satisfies $\mathbf{A}\mathbf{x}^{\prime}\in(\{\mathbf{z}\}+\bigcup_{\mathcal{E}\in\mathscr{P}}\mathcal{R}(\mathbf{B}_{\mathcal{E}}))$ (with $\mathscr{P}=\wp_{n_{e}}(\{1,\ldots,{N_{b}}\})$) with $\mathopen{}\left\lVert\mathbf{x}^{\prime}\right\rVert_{0}\leq n_{x}$. This implies the existence of a vector $\mathbf{e}^{\prime}$ with $\mathopen{}\left\lVert\mathbf{e}^{\prime}\right\rVert_{0}\leq n_{e}$ such that

From $\mathopen{}\left\lVert\mathbf{x}\right\rVert_{0}=n_{x}$ and $\mathopen{}\left\lVert\mathbf{x}^{\prime}\right\rVert_{0}\leq n_{x}$ it follows that $\mathopen{}\left\lVert\mathbf{x}-\mathbf{x}^{\prime}\right\rVert_{0}\leq 2n_{x}$. Similarly, $\mathopen{}\left\lVert\mathbf{e}\right\rVert_{0}=n_{e}$ and $\mathopen{}\left\lVert\mathbf{e}^{\prime}\right\rVert_{0}\leq n_{e}$ imply $\mathopen{}\left\lVert\mathbf{e}^{\prime}-\mathbf{e}\right\rVert_{0}\leq 2n_{e}$. Defining $\mathbf{p}=\mathbf{x}-\mathbf{x}^{\prime}$ and $\mathcal{P}=\textrm{supp}(\mathbf{x}-\mathbf{x}^{\prime})$, and, similarly, $\mathbf{q}=\mathbf{e}^{\prime}-\mathbf{e}$ and $\mathcal{Q}=\textrm{supp}(\mathbf{e}^{\prime}-\mathbf{e})$, we arrive at

where (64) follows from the uncertainty relation in \frefthm:uncertainty applied to the difference vectors $\mathbf{p}$ and $\mathbf{q}$ (with $\epsilon_{\mathcal{P}}=\epsilon_{\mathcal{Q}}=0$ since both $\mathbf{p}$ and $\mathbf{q}$ are perfectly concentrated to $\mathcal{P}$ and $\mathcal{Q}$, respectively) and (65) is a consequence of $\mathopen{}\left\lvert\mathcal{P}\right\rvert\leq 2n_{x}$ and $\mathopen{}\left\lvert\mathcal{Q}\right\rvert\leq 2n_{e}$. Obviously, (65) is in contradiction to (30), which concludes the proof.

References