Compressed Sensing and Matrix Completion with Constant Proportion of Corruptions

Introduction

is guaranteed to be the original signal $x$ with high probability, provided $x$ is sufficiently sparse and $A$ obeys certain conditions. A typical result is this: if $A$ has iid Gaussian entries, then exact recovery occurs provided $\|x\|_{0}\leq Cm/(\log(n/m)+1)$ for some positive numerical constant $C>0$. Here is another example, if $A$ is a matrix with rows randomly selected from the DFT matrix, the condition becomes $\|x\|_{0}\leq Cm/\log n$ . This paper discusses a natural generalization of CS, which we shall refer to as compressed sensing with corruptions. We assume that some entries of the data vector $y$ are totally corrupted but we have absolutely no idea which entries are unreliable. We still want to recover the original signal efficiently and accurately. Formally, we have the mathematical model

Clipping. Signal clipping frequently appears because of nonlinearities in the acquisition device . Here, one typically measures $g(Ax)$ rather than $Ax$, where $g$ is always a nonlinear map. Letting $f=g(Ax)-Ax$, we thus observe $y=Ax+f$. Nonlinearities usually occur at large amplitudes so that for those components with small amplitudes, we have $f=g(Ax)-Ax=0$. This means that $f$ is sparse and, therefore, our model is appropriate. Just as before, locating the portion of the data vector that has been clipped may be difficult because of additional noise.

CS for networked data. In a sensor network, different sensors will collect measurements of the same signal $x$ independently (they each measure $z_{i}=\langle a_{i},x\rangle$) and send the outcome to a center hub for analysis . By setting $a_{i}$ as the row vectors of $A$, this is just $z=Ax$. However, typically some sensors will fail to send the measurements correctly, and will sometimes report totally meaningless measurements. Therefore, we collect $y=Ax+f$, where $f$ models recording errors.

There have been several theoretical papers investigating the exact recovery method for CS with corruptions , and all of them consider the following recovery procedure in the noiseless case:

We will compare them with our results in Section 1.4.

2 Introduction on matrix completion with corruptions

The problem is to recover the original matrix $L$, and there have been many papers studying this problem in recent years, see , for example. Here one minimizes the nuclear norm — the sum of all the singular values — to recover the original low rank matrix. We discuss below an improved result due to Gross (with a slight difference). Define $O\sim\text{Ber}(\rho)$ for some $0<\rho<1$ by meaning that $1_{\{(i,j)\in O\}}$ are iid Bernoulli random variables with parameter $\rho$. Then the solution to

is guaranteed to be exactly $L$ with high probability, provided $\rho\geq{{C_{\rho}r\mu\log^{2}n}\over n}$. Here, $C_{\rho}$ is a positive numerical constant, $r$ is the rank of $L$, and $\mu$ is an incoherence parameter introduced in which is only dependent of $L$. This paper is concerned with the situation in which some entries may have been corrupted. Therefore, our model is that we observe

is guaranteed to be the true pair $(L,S)$ with high probability under some assumptions about $L,O,S$ . We will compare them with our result in Section 1.4.

3 Main results

This section introduces three models and three corresponding recovery results. The proofs of these results are deferred to Section 2 for Theorem 1.1, Section 3 for Theorem 1.2 and Section 4 for Theorem 1.3.

satisfies $\|\hat{x}-x\|_{2}+\|\hat{f}-f\|_{2}\leq K\epsilon$ with probability at least $1-C\exp(-cm)$. This holds universally; that is to say, for all vectors $x$ and $f$ obeying $\|x\|_{0}\leq\alpha m/(\log(n/m)+1)$ and $\|f\|_{0}\leq\alpha m$. Here $\alpha$, $C$, $c$ and $K$ are numerical constants.

In the above statement, the matrix $A$ is random. Everything else is deterministic. The reader will notice that the number of nonzero entries is on the same order as that needed for recovery from clean data , while the condition of $f$ implies that one can tolerate a constant fraction of possibly adversarial errors. Moreover, our convex optimization is related to LASSO and Basis Pursuit .

3.2 CS with general sensing matrices [Model 2]

For the model above, the solution $(\hat{x},\hat{f})$ to (1.3), with $\lambda(n,m)=1/\sqrt{\log n}$, is exact with probability at least $1-Cn^{-3}$, provided that $s\leq\alpha{m\over{\mu\log^{2}n}}$ and $m_{b}\leq\beta{m\over{\mu}}$. Here $C$, $\alpha$ and $\beta$ are some numerical constants.

Above, $x$ and $f$ have fixed supports and random signs. However, by a recent de-randomization technique first introduced in , exact recovery with random supports and fixed signs would also hold. We will explain this de-randomization technique in the proof of Theorem 1.3. In some specific models, such as independent rows from the DFT matrix, $\mu$ could be a numerical constant, which implies the proportion of corruptions is also a constant. An open problem is whether Theorem 1.2 still holds in the case where $x$ and $f$ have both fixed supports and signs. Another open problem is to know whether the result would hold under more general conditions about $A$ as in in the case where $x$ has both random support and random signs. We emphasize that the sparsity condition $\|x\|_{0}\leq C{m\over{\mu\log^{2}n}}$ is a little stronger than the optimal result available in the noise-free literature ), namely,$\|x\|_{0}\leq C{m\over{\mu\log n}}$. The extra logarithmic factor appears to be important in the proof which we will explain in Section 3, and a third open problem is whether or not it is possible to remove this factor. Here we do not give a sensitivity analysis for the recovery procedure as in Model 1. Actually by applying a similar method introduced in to our argument in Section 3, a very good error bound could be obtained in the noisy case. However, technically there is little novelty but it will make our paper very long. Therefore we decide to only discuss the noiseless case and focus on the sampling rate and corruption ratio.

3.3 MC from corrupted entries [Model 3]

This model is the same as that originally introduced in , and later used in . We observe $\mathcal{P}_{O}(L)+S$, where $O\in[n]\times[n]$ and $S$ is supported on $\Omega\subset O$. Here we assume that $O,\Omega,S$ satisfy the following model:

Under Model 3.1, suppose $\rho>C_{\rho}{{\mu r\log^{2}n}\over{n}}$ and $s\leq C_{s}$. Moreover, suppose $\lambda:={1\over\sqrt{\rho n\log n}}$ and denote $(\hat{L},\hat{S})$ as the optimal solution to the problem (1.6). Then we have $(\hat{L},\hat{S})=(L,S)$ with probability at least $1-Cn^{-3}$ for some numerical constant $C$, provided the numerical constants $C_{s}$ is sufficiently small and $C_{\rho}$ is sufficiently large.

In this model $O$ is available while $\Omega$, $\Gamma$ and $S$ are not known explicitly from the observation $\mathcal{P}_{O}(L)+S$. By the assumption $O\sim\text{Ber}(\rho)$, we can use $|O|/(n^{2})$ to approximate $\rho$. From the following proof we can see that $\lambda$ is not required to be ${1\over\sqrt{\rho n\log n}}$ exactly for the exact recovery. The power of our result is that one can recover a low-rank matrix from a nearly minimal number of samples even when a constant proportion of these samples has been corrupted. We only discuss the noiseless case for this model. Actually by a method similar to , a suboptimal estimation error bound can be obtained by a slight modification of our argument. However, it is of little interest technically and beyond the optimal result when $n$ is large. There are other suboptimal results for matrix completion with noise, such as , but the error bound is not tight when the additional noise is small. We want to focus on the noiseless case in this paper and leave the problem with noise for future work. The values of $\lambda$ are chosen for theoretical guarantee of exact recovery in Theorem 1.1, 1.2 and 1.3. In practice, $\lambda$ is usually taken by cross validation.

4 Comparison with existing results, relative works and our contribution

A Proof of Theorem 1.1

In the proof of Theorem 1.1, we will see the notation $P_{T}x$. Here $x$ is a $k$-dimensional vector, $T$ is a subset of $\{1,...,k\}$ and we also use $T$ to represent the subspace of all $k$-dimensional vectors supported on $T$. Then $P_{T}x$ is the projection of $x$ onto the subspace $T$, which is to keep the value of $x$ on the support $T$ and to change other elements into zeros. In this section we use the notation “$\lfloor.\rfloor$” of “floor function” to represent the integer part of any real number. First we generalize the concept of the restricted isometry property (RIP) for the convenience to prove our theorem:

Proof First, we suppose $\|x_{1}\|_{2}^{2}+\|f_{1}\|_{2}^{2}=\|x_{2}\|_{2}^{2}+\|f_{2}\|_{2}^{2}=1$. By the definition of $\delta_{s_{1},s_{2}}$, we have

By the above inequalities, we have $\left|\left\langle\Phi\begin{bmatrix}x_{1}\\ f_{1}\end{bmatrix},\Phi\begin{bmatrix}x_{2}\\ f_{2}\end{bmatrix}\right\rangle\right|\leq\delta_{s_{1},s_{2}}$, and hence by homogeneity, we have $\left|\left\langle\Phi\begin{bmatrix}x_{1}\\ f_{1}\end{bmatrix},\Phi\begin{bmatrix}x_{2}\\ f_{2}\end{bmatrix}\right\rangle\right|\leq\delta_{s_{1},s_{2}}\sqrt{\|x_{1}\|_{2}^{2}+\|f_{1}\|_{2}^{2}}\sqrt{\|x_{2}\|_{2}^{2}+\|f_{2}\|_{2}^{2}}$ without the norm assumption.

Proof Suppose $\Delta x=\hat{x}-x$ and $\Delta f=\hat{f}-f$. Then by (1.7) we have

It is easy to check that the original $(x,f)$ satisfies the inequality constraint in (1.7), so we have

Then it suffices to show $\|\Delta x\|_{2}+\|\Delta f\|_{2}\leq{{4\sqrt{13+13\delta_{2s_{1},2s_{2}}}}\over{1-9\delta_{2s_{1},2s_{2}}}}\epsilon$.

Suppose $T_{0}$ with $|T_{0}|=s_{1}$ such that $\operatorname{supp}(x)\in T_{0}$. Denote $T_{0}^{c}=T_{1}\cup\cdots\cup T_{l}$ where $|T_{1}|=...=|T_{l-1}|=s_{1}$ and $|T_{l}|\leq s_{1}$. Moreover, suppose $T_{1}$ contains the indices of the $s_{1}$ largest (in the sense of absolute value) coefficients of $P_{T_{0}^{c}}\Delta x$, $T_{2}$ contains the indices of the $s_{1}$ largest coefficients of $P_{(T_{0}\cup T_{1})^{c}}\Delta x$, and so on. Similarly, define $V_{0}$ such that $\operatorname{supp}(f)\subset V_{0}$ and $|V_{0}|=s_{2}$, and divide $V_{0}^{c}=V_{1}\cup...\cup V_{k}$ in the same way. By this setup, we easily have

On the other hand, by the assumption $\operatorname{supp}(x)\subset T_{0}$ and $\operatorname{supp}(f)\subset V_{0}$, we have,

By inequalities (2.1), (2.4) and (2.5), we have

By the definition of $\delta_{2s_{1},2s_{2}}$, the fact $\left\|\Phi\begin{bmatrix}\Delta x\\ \Delta f\end{bmatrix}\right\|_{2}\leq 2\epsilon$ and Lemma 2.2, we have

Therefore, by $\delta_{2s_{1},2s_{2}}<1/9$, we have

We now cite a well-known result in the literature of CS, e.g. Theorem 5.2 of .

Suppose $A$ is a random matrix defined in model 1. Then for any $0<\delta<1$, there exist $c_{1}(\delta),c_{2}(\delta)>0$ such that with probability at least $1-2\exp(-c_{2}(\delta)m)$,

holds universally for any $x$ with $|\operatorname{supp}(x)|\leq c_{1}(\delta){m\over{\log{n\over m}+1}}$.

Also, we cite a well-know result which can give a bound for the biggest singular value of random matrix, e.g. and .

Let $B$ be an $m\times n$ matrix whose entries are independent standard normal random variables. Then for every $t\geq 0$, with probability at least $1-2\exp(-t^{2}/2)$, one has $\|B\|_{2,2}\leq\sqrt{m}+\sqrt{n}+t$.

We now prove Theorem 1.1: Proof Suppose $\alpha$, $\delta$ are two constants independent of $m$ and $n$, and their values will be specified later. Set $s_{1}=\left\lfloor\alpha{m\over{\log{n\over m}+1}}\right\rfloor$ and $s_{2}=\lfloor\alpha m\rfloor$. We want to bound the RIP-constant $\delta_{2s_{1},2s_{2}}$ for the $(n+m)\times m$ matrix $\Phi=[A,I]$ when $\alpha$ is sufficiently small. For any $T$ with $|T|=2s_{1}$ and $V$ with $|V|=2s_{2}$, and any $x$ with $\operatorname{supp}(x)\subset T$, any $f$ with $\operatorname{supp}(f)\subset V$, we have

By Lemma 2.4, assuming $\alpha\leq c_{1}(\delta)$, with probability at least $1-2\exp(-c_{2}(\delta)m))$ we have

holds universally for any such $T$ and $x$. Now we we fix $T$ and $V$, and we want to bound $\|P_{V}AP_{T}\|_{2,2}$. By Lemma 2.5, we actually have

with probability at least $1-2\exp(-{\delta^{2}m/2})$. Then with probability at least $1-2\exp(-{{\delta^{2}m}\over 2}){n\choose 2s_{1}}{m\choose 2s_{2}}$, inequality 2.8 holds universally for any $V$ satisfying $|V|=2s_{1}$ and $T$ satisfying $|V|=2s_{2}$. By $2s_{1}\leq 2\alpha{m\over{\log{n\over m}+1}}$, we have $2s_{1}\log({{en}\over{2s_{1}}})\leq\alpha_{1}m$, where $\alpha_{1}$ only depends on $\alpha$ and $\alpha_{1}\rightarrow 0$ as $\alpha\rightarrow 0$, and hence ${n\choose 2s_{1}}\leq({{en}\over{2s_{1}}})^{2s_{1}}\leq\exp(\alpha_{1}m)$. Similarly, because $2s_{2}\leq 2\alpha m$, we have $2s_{2}\log({{em}\over{2s_{2}}})\leq\alpha_{2}m$, where $\alpha_{2}$ only depends on $\alpha$ and $\alpha_{2}\rightarrow 0$ as $\alpha\rightarrow 0$, and hence ${m\choose 2s_{2}}\leq({{em}\over{2s_{2}}})^{2s_{2}}\leq\exp(\alpha_{2}m)$. Therefore, inequality 2.8 holds universally for any such $T$ and $V$ with probability at least $1-2\exp((\delta^{2}/2-\alpha_{1}-\alpha_{2})m)$. Combined with 2.7, we have

holds universally for any such $T$, $U$, $x$ and $f$ which probability at least $1-2\exp(-c_{2}(\delta)m))-2\exp((\delta^{2}/2-\alpha_{1}-\alpha_{2})m)$. By choosing an appropriate $\delta$ and letting $\alpha$ sufficiently small, we have $\delta_{2s_{1},2s_{2}}<1/9$ with probability at least $1-Ce^{-cm}$. Moreover, under the assumption that $\alpha\left({m\over{\log(n/m)+1}}\right)\geq 1$, we have $s_{1}=\left\lfloor\alpha\left({m\over{\log(n/m)+1}}\right)\right\rfloor>0$, $s_{2}=\lfloor\alpha m\rfloor>0$ and ${{1\over 2}\sqrt{{s_{1}}\over{s_{2}}}}<{1\over{\sqrt{\log{n\over m}+1}}}<{2\sqrt{{s_{1}}\over{s_{2}}}}$. Then Theorem 1.1 as a direct corollary of Lemma 2.3

A Proof of Theorem 1.2

To prove Theorem 1.2 we need some supporting lemmas. Because our model of sensing matrix $A$ is the same as in , we will cite some lemmas from it directly.

This Lemma was proved in by matrix Bernstein’s inequality, which is first introduced by . A deep generalization is given in .

(Lemma 2.5 of ) Suppose $A$ is as defined in model 2. Fix $T\subset[n]$ with $|T|=s$. Then $\max_{i\in T^{c}}\|A_{:,T}^{*}A_{:,i}\|_{2}\leq 1$ with high probability provided $s\leq\gamma{m\over{\mu\log n}}$, where $\gamma$ is some absolute constant.

2 A proof of Theorem 1.2

In this part we will give a complete proof of Theorem 1.2 with a powerful technique called ”golfing-scheme” introduced by David Gross in , and later in and . Under the assumption of model 2, we additionally assume $s\leq\alpha{m\over{\mu\log^{2}n}}$ and $m_{b}\leq\beta{m\over\mu}$, where $\alpha$ and $\beta$ are numerical constants whose values will specified later. First we give two useful inequalities. By replacing $A$ with $\sqrt{m\over{m-m_{b}}}A_{B^{c},T}$ in Lemma 3.1 and Lemma 3.2, we have

with high probability provided $s\leq\gamma{{m-m_{b}}\over{\mu\log n}}$. Since $s\leq\alpha{m\over{\mu\log^{2}n}}$ and $m_{b}\leq\beta{m\over\mu}$, both 3.1 and 3.2 hold with high probability provided $\alpha$ and $\beta$ are sufficiently small. We assume (3.1) and (3.2) hold throughout this section. First we prove that the solution $(\hat{x},\hat{f})$ of (1.3) equals $(x,f)$ if we can find an appropriate dual vector $q_{B^{c}}$ satisfying the following requirement. This is actually an “inexact dual vector” of the optimization problem (1.3). This idea was first given explicitly in and , and related to . We give a result similar to .

Then the solution $(\hat{x},\hat{f})$ of (1.3) equals $(x,f)$ provided $\beta$ is sufficiently small and $\lambda<{3\over 2}$.

Proof Set $h=\hat{x}-x$. By $x_{T^{c}}=0$ we have

By $f_{B^{c}}=0$, and $Ax+f=A\hat{x}+\hat{f}$, we have $Ah=f-\hat{f}$ and

Since $\|\hat{x}\|_{1}+\lambda\|\hat{f}\|_{1}\leq\|x\|_{1}+\lambda\|f\|_{1}$, we have

By (3.1), we have $\left\|\sqrt{m\over{m-m_{b}}}A_{B^{c},T}^{*}\right\|_{2,2}\leq\sqrt{3\over 2}$ and the smallest singular value of ${m\over{m-m_{b}}}A_{B^{c},T}^{*}A_{B^{c},T}$ is at least ${1\over 2}$. Therefore,

Plugging this into (3.8), we have$\left({3\over 4}-{1\over 2}\lambda\right)\|h_{T^{c}}\|_{1}+\left({3\over 4}-{{\sqrt{6}}\over 4}\sqrt{m\over{m-m_{b}}}\right)\lambda\|A_{B^{c},:}h\|_{1}\leq 0$. We know ${3\over 4}-{{\sqrt{6}}\over 4}\sqrt{m\over{m-m_{b}}}>0$ when $\beta$ is sufficiently small. Moreover, by the assumption $\lambda<{3\over 2}$, we have $h_{T^{c}}=0$ and $A_{B^{c},:}h=0$. Since $A_{B^{c},:}h=A_{B^{c},T}h_{T}+A_{B^{c},T^{c}}h_{T^{c}}$, we have $A_{B^{c},T}h_{T}=0$. The inequality (3.1) implies that $A_{B^{c},T}$ is injective, so $h_{T}=0$ and $h=h_{T}+h_{T^{c}}=0$, which implies $(\hat{x},\hat{f})=(x,f)$.

Now let’s construct a vector $q_{B^{c}}$ satisfying the requirement (3.3) by choosing an appropriate $\lambda$. Proof (of Theorem 1.2) Set $\lambda={1\over{\sqrt{\log n}}}$. It suffices to construct a $q_{B^{c}}$ satisfying (3.3). Denoting $u=A_{B^{c}.:}^{*}q_{B^{c}}$, we only need to construct a $q_{B^{c}}$ satisfying

Now let’s construct our $q_{B^{c}}$ by the golfing scheme. First we have to write $A_{B^{c},:}$ as a block matrix. We divide $B^{c}$ into $l=\lfloor\log_{2}n+1\rfloor=\lfloor{{\log n}\over{\log 2}}+1\rfloor$ disjoint subsets: $B^{c}=G_{1}\cup...\cup G_{l}$ where $|G_{i}|=m_{i}$. Then we have $\sum_{i=1}^{l}m_{i}=m-m_{b}$ and

We want to mention that the partition of $B^{c}$ is deterministic, not depending on $A$, so $A_{G_{1},:},...,A_{G_{l},:}$ are independent. Noticing $m_{b}\leq\beta{m\over\mu}\leq\beta m$, by letting $\beta$ sufficiently small, we can require

for some absolute constant $C$. Since $s\leq\alpha{m\over{\mu\log^{2}n}}$, we have

Then by Lemma 3.1, replacing $A$ with $\sqrt{m\over{m_{j}}}A_{G_{j},T}$, we have the following inequalities:

with high probability provided $\alpha$ is sufficiently small.

Now let’s give an explicit construction of $q_{B^{c}}$. Define

Then by $u=A_{B^{c},:}^{*}q_{B^{c}}$, we have

Now we will prove our constructed $q_{B^{c}}$ satisfies the desired requirements:

Then by (3.18) and $l=\lfloor\log_{2}n+1\rfloor$, we have $\|p_{l}\|_{2}\leq{1\over{\log n}}({1\over 2})^{l}{9\over 8}\sqrt{s}\leq\left({1\over{\log n}}\right)\left({1\over n}\right)\left({9\over 8}\right)\sqrt{{\alpha m}\over{\mu\log^{2}n}}\leq{1\over{4\sqrt{\log n}}}={\lambda\over 4}$, provided $\alpha$ is sufficiently small.

By (3.15), we have $u_{T^{c}}=\displaystyle\sum\limits_{i=1}^{l}{m\over{m_{i}}}A_{G_{i},T^{c}}^{*}A_{G_{i},T}p_{i-1}$. Recall that $A_{G_{1},:},...,A_{G_{l},:}$ are independent, so by the construction of $p_{i-1}$ we know $A_{G_{i},:}$ and $p_{i-1}$ are independent. Replacing $A$ with $\sqrt{m\over{m_{i}}}A_{G_{i},:}$ in Lemma 3.2, and by the sparsity condition (3.9), we have $\displaystyle\sum\limits_{i=1}^{l}\left\|{m\over{m_{i}}}A_{G_{i},T^{c}}^{*}A_{G_{i},T}p_{i-1}\right\|_{\infty}\leq\displaystyle\sum\limits_{i=1}^{l}{1\over 20}{1\over{\sqrt{s}}}\|p_{i-1}\|_{2}$ with high probability, provided $\alpha$ is sufficiently small. By (3.16), (3.17), (3.18) and (3.19), we have $\|u_{T^{c}}\|_{\infty}\leq\displaystyle\sum\limits_{i=1}^{l}{1\over 20}{1\over{\sqrt{s}}}\|p_{i-1}\|_{2}\leq{1\over 20}{1\over{\sqrt{s}}}2\|p_{0}\|_{2}<{1\over 8}$.

By choosing some numerical constant $C$ and $t=C\sqrt{m\log n}\|w\|_{2}$, we have

with high probability, provided $\alpha$ is sufficiently small. By (3.21) and (3.22), we have

for some numerical constant $C$. When $k\geq 3$, by (3.20), (3.10) and (3.11), we have $\|w\|_{2}\leq({1\over 2})^{k-1}{1\over{\log n}}\sqrt{\mu s}\leq{\sqrt{\alpha m}\over{\log^{2}n}}$. Recalling ${m\over{m_{k}}}\leq C\log n$, by (3.23), we have $\left|{{\sqrt{m}}\over{m_{k}}}w^{*}\left(\textrm{sgn}(x_{T})-\lambda A_{B,T}^{*}\textrm{sgn}(f_{B})\right)\right|\leq C\left({m\over{m_{k}}}\right)\sqrt{\alpha}(\log n)^{-3/2}\leq{\lambda\over 4}$ provided $\alpha$ is sufficiently small. When $k\leq 2$, by (3.20) and (3.10), we have $\|w\|_{2}\leq\sqrt{\mu s}\leq{\sqrt{\alpha m}\over{\log n}}$. Recalling ${m\over{m_{k}}}\leq C$, by (3.23), we have $\left|{{\sqrt{m}}\over{m_{k}}}w^{*}\left(\textrm{sgn}(x_{T})-\lambda A_{B,T}^{*}\textrm{sgn}(f_{B})\right)\right|\leq C\left({m\over{m_{k}}}\right)\sqrt{\alpha}(\log n)^{-1/2}\leq{\lambda\over 4}$ provided $\alpha$ is sufficiently small.

Here we would like to compare our golfing scheme with that in . There are mainly two differences. One is that we have an extra term $\lambda A_{B,:}^{*}\textrm{sgn}(f_{B})$ in the dual vector. To obtain the inequality $\|v_{T^{c}}\|_{\infty}\leq 1/4$, we propose to bound $\|u_{T^{c}}\|_{\infty}$ and $\|\lambda A_{B,:}^{*}\textrm{sgn}(f_{B})\|_{\infty}$ respectively, and this will lead to the extra log factor compared with . Moreover, by using the golfing scheme to construct the dual vector, we need to bound the term $\|q_{B^{c}}\|_{\infty}$, which is not necessary in . This inevitably incurs the random signs assumptions of the signal.

A Proof of Theorem 1.3

In this section, the capital letters $X$, $Y$ etc represent matrices, and the symbols in script font $\mathcal{I}$, $\mathcal{P}_{T}$, etc represent linear operators from a matrix space to a matrix space. Moreover, for any $\Omega_{0}\subset[n]\times[n]$ we have $\mathcal{P}_{\Omega_{0}}M$ is to keep the entries of $M$ on the support $\Omega_{0}$ and to change other entries into zeros. For any $n\times n$ matrix $A$, denote by $\|A\|_{F}$, $\|A\|$, $\|A\|_{\infty}$ and $\|A\|_{*}$ respectively the Frobenius norm, operator norm (the largest singular value), the biggest magnitude of all elements, and the nuclear norm(the sum of all singular values). Similarly to Section 3, instead of denoting them as $C_{1}$, $C_{2}$, …, we just use $C$, whose values change from line to line. Also, we will use the phrase “with high probability” to mean with probability at least $1-Cn^{-c}$, where $C>0$ is a numerical constant and $c=3,4,\text{~{}or~{}}5$ depending on the context.

Model 3.1 is natural and used in , but we will use the following equivalent model for the convenience of proof:

Notice that although $(1_{\{(i,j)\in O\}},1_{\{(i,j)\in\Omega\}})$ depends on $K$, its distribution does not. By the above we know that $(O,\Omega)$ has the same distribution in both models. Therefore in the following we will use Model 3.2 instead. The advantage of using Model 3.2 is that we can utilize $\Gamma^{\prime}$, $\Omega^{\prime}$, $W$, etc. as auxiliaries. In the next section we prove some supporting lemmas which are useful for the proof of the main theorem.

2 Supporting lemmas

(Theorem 4.1 of ) Suppose $\Omega_{0}\sim\text{Ber}(\rho_{0})$. Then with high probability, $\|\mathcal{P}_{T}-\rho_{0}^{-1}\mathcal{P}_{T}\mathcal{P}_{\Omega_{0}}\mathcal{P}_{T}\|\leq\epsilon$, provided that $\rho_{0}\geq C_{0}\,\epsilon^{-2}\,\frac{\mu r\log n}{n}$ for some numerical constant $C_{0}>0$.

The original idea of the proof of this theorem is due to .

(Theorem 3.1 of ) Suppose $Z\in\text{Range}(\mathcal{P}_{T})$ is a fixed matrix, $\Omega_{0}\sim\text{Ber}(\rho_{0})$, and $\epsilon\leq 1$ is an arbitrary constant. Then with high probability $\|(\mathcal{I}-\rho_{0}^{-1}\mathcal{P}_{T}\mathcal{P}_{\Omega_{0}})Z\|_{\infty}\leq\epsilon\|Z\|_{\infty}$ provided that $\rho_{0}\geq C_{0}\,\epsilon^{-2}\,\frac{\mu r\log n}{n}$ for some numerical constant $C_{0}>0$.

(Theorem 6.3 of ) Suppose $Z$ is a fixed matrix, and $\Omega_{0}\sim\text{Ber}(\rho_{0})$. Then with high probability, $\|(\rho_{0}\mathcal{I}-\mathcal{P}_{\Omega_{0}})Z\|\leq C_{0}^{\prime}\sqrt{np\log n}\|Z\|_{\infty}$ provided that $\rho_{0}\leq p$ and $p\geq\,C_{0}\frac{\log n}{n}$ for some numerical constants $C_{0}>0$ and $C_{0}^{\prime}>0$.

Notice that we only have $\rho_{0}=p$ in Theorem 6.3 of . By a very slight modification in the proof (specifically, the proof of Lemma 6.2) we can have $\rho_{0}\leq p$ as stated above.

3 A proof of Theorem 1.3

By Lemma 3.1, we have we have $\|{1\over{(1-2s)\rho}}\mathcal{P}_{T}\mathcal{P}_{\Gamma^{\prime}}\mathcal{P}_{T}-\mathcal{P}_{T}\|\leq{1\over 2}$ and $\|{1\over{\sqrt{(1-2s)\rho}}}\mathcal{P}_{T}\mathcal{P}_{\Gamma^{\prime}}\|\leq\sqrt{3/2}$ with high probability provided $C_{\rho}$ is sufficiently large and $C_{s}$ is sufficiently small. We will assume both inequalities hold all through the paper.

If there exists an $n\times n$ matrix $Y$ obeying

where $\lambda={1\over{\sqrt{n\rho\log n}}}$. Then the solution $(\hat{L},\hat{S})$ to (1.6) satisfies $(\hat{L},\hat{S})=(L,S)$.

Proof Set $H=\hat{L}-L$. The condition $\mathcal{P}_{O}(L)+S=\mathcal{P}_{O}(\hat{L})+\hat{S}$ implies that $\mathcal{P}_{O}(H)=S-\hat{S}$. Then $\hat{S}$ is supported on $O$ because $S$ is supported on $\Omega\subset O$. By considering the subgradient of the nuclear norm at $L$, we have

By the definition of $(\hat{L},\hat{S})$, we have

By the two inequalities above and the fact $\mathcal{P}_{\Gamma^{\prime}}\hat{S}=\mathcal{P}_{\Gamma^{\prime}}(\hat{S}-S)=-\mathcal{P}_{\Gamma^{\prime}}H$, we have

Recall that we assume $\|{1\over{(1-2s)\rho}}\mathcal{P}_{T}\mathcal{P}_{\Gamma^{\prime}}\mathcal{P}_{T}-\mathcal{P}_{T}\|\leq{1\over 2}$ and $\|{1\over{\sqrt{(1-2s)\rho}}}\mathcal{P}_{T}\mathcal{P}_{\Gamma^{\prime}}\|\leq\sqrt{3/2}$ all through the paper. Then

Then $\mathcal{P}_{T^{\perp}}(H)=\mathcal{P}_{\Gamma^{\prime}}H=0$, which implies $\mathcal{P}_{\Gamma^{\prime}}\mathcal{P}_{T}(H)=0$. Since $\mathcal{P}_{\Gamma^{\prime}}\mathcal{P}_{T}$ is injective ($\|{1\over{(1-2s)\rho}}\mathcal{P}_{T}\mathcal{P}_{\Gamma^{\prime}}\mathcal{P}_{T}-\mathcal{P}_{T}\|\leq{1\over 2}$) on $T$, we have $\mathcal{P}_{T}(H)=0$. Then we have $H=0$.

Suppose we can construct $Y$ and $\widetilde{Y}$ satisfying

with high probability provided $C_{\rho}$ is large enough and $C_{s}$ is small enough. Then $\|Z_{j}\|_{F}\leq({1\over 2})^{j}\|Z_{0}\|_{F}$. By the construction of $Z_{j}$, we know that $Z_{j}\in\text{Range}(\mathcal{P}_{T})$ and $Z_{j}=(I-{1\over q}\mathcal{P}_{T}\mathcal{P}_{\Gamma_{j}})Z_{j-1}$. Then similarly, by Lemma 4.2, we have

with high probability provided $C_{\rho}$ is large enough and $C_{s}$ is small enough. Also, by Lemma 4.3 we have

with high probability provided $C_{\rho}$ is large enough and $C_{s}$ is small enough. We first bound $\|Z_{0}\|_{F}$ and $\|Z_{0}\|_{\infty}$. Obviously $\|Z_{0}\|_{\infty}\leq\|UV^{*}\|_{\infty}+\lambda\|\mathcal{P}_{T}\mathcal{P}_{\Omega^{\prime}}(W)\|_{\infty}$. Recall that for any $i,j\in[n]$, we have $\|\mathcal{P}_{T}(e_{i}e_{j}^{*})\|_{\infty}\leq{{2\mu r}\over n}$ and $\|\mathcal{P}_{T}(e_{i}e_{j}^{*})\|_{F}\leq\sqrt{{2\mu r}\over n}$. Moreover, $\mathcal{P}_{\Omega^{\prime}}(W)$ satisfies $(\mathcal{P}_{\Omega^{\prime}}(W))_{;}$ are iid random variables with the distribution

Then with high probability we have $\|\mathcal{P}_{T}\mathcal{P}_{\Omega^{\prime}}(W)\|_{\infty}\leq C\sqrt{\rho{{\mu r\log n}\over n}}(\geq C\sqrt{C_{\rho}{{\mu r\log^{2}n}\over n}{{\mu r\log n}\over n}}>C\sqrt{C_{\rho}}M\log n)$. Then by $\|UV^{*}\|_{\infty}\leq{\sqrt{\mu r}\over n}$ we have $\|Z_{0}\|_{\infty}\leq C{\sqrt{\mu r}\over n}$, which implies $\|Z_{0}\|_{F}\leq n\|Z_{0}\|_{\infty}\leq C{\sqrt{\mu r}}$ . Now we want to prove $Y$ satisfies 4.4 with high probability. Obviously $\mathcal{P}_{\Gamma^{\prime c}}Y=0$. It suffices to prove

provided $C_{\rho}$ is sufficiently large. Third, we have $\|\lambda\mathcal{P}_{T^{\perp}}\mathcal{P}_{\Omega^{\prime}}(W)\|\leq\lambda\|\mathcal{P}_{\Omega^{\prime}}(W)\|$. Notice that $W_{ij}$ is an independent Rademacher sequence independent of $\Omega^{\prime}$. By Lemma 4.3, we have

with high probability provided ${{2s\rho}\over{1-\rho+2s\rho}}\leq p$ and $p\geq C_{0}{{\log n}\over n}$. By Theorem 3.9 of , we have $\|W\|_{\infty}\leq C_{1}\sqrt{n}$ with high probability. Therefore,

By choosing $p={\rho\over{C_{2}}}$ for some appropriate $C_{2}$, we have $\|\mathcal{P}_{\Omega^{\prime}}(W)\|\leq{\sqrt{n\rho\log n}\over 8}$, provided $C_{\rho}$ is large enough and $C_{s}$ is small enough. Fourth,

provided $C_{\rho}$ is sufficiently large.

Notice that in the authors used a very similar golfing scheme. To compare these two methods, we use here a non-uniform sizes golfing scheme to achieve a result with fewer log factors. Moreover, unlike in the authors used both golfing scheme and least square method to construct two parts of the dual matrix, here we only use golfing scheme. Actually the method to construct the dual matrix in cannot be applied directly to our problem when $\rho=O(r\log^{2}n/n)$.

Acknowledgements

I am grateful to my Ph. D. advisor, Emmanuel Candès, for his encouragements and his help in preparing this manuscript.

References