More Algorithms for Provable Dictionary Learning

Sanjeev Arora, Aditya Bhaskara, Rong Ge, Tengyu Ma

Introduction

Provable guarantees for dictionary learning have seemed difficult because the obvious math programming formulation is nonconvex: both $A$ and the $x$ ’s are unknown. Even when the dictionary $A$ is known, it is in general NP-hard to get the sparse combination $x$ given worst-case $y$ [DMA97]. This problem of decoding $x$ given $Ax$ with full knowledge of $A$ is called sparse recovery or sparse regression, and is closely related to compressed sensing. For many types of dictionary $A$ , sparse recovery was shown to be tractable even on worst-case $y$ , starting with such a result for incoherent matrices by Donoho and Huo [DH01]. However in most early works $x$ was constrained to be $\sqrt{n}$ -sparse, until Candes, Romberg and Tao [CRT06] showed how to do sparse recovery even when the sparsity is $\Omega(n)$ , assuming $A$ satisfies the restricted isometry property (RIP) (which random matrices do).

But dictionary learning itself (recovering $A$ given samples $y$ ) has proved much harder and heuristic algorithms are widely used. Lewicki and Sejnowski [LS00] designed the first one, which was followed by the method of optimal directions (MOD) [EAHH99] and K-SVD [AEB06]. See [Aha06] for more references. However, until recently there were no algorithms that provably recovers the correct dictionary. Recently Spielman et al. [SWW12] gave such an algorithm for the full rank case (i.e., $m=n$ ) and the unknown feature vector $x$ is $\sqrt{n}$ -sparse. However, in practice overcomplete dictionaries ( $m>n$ ) are preferred. Arora et al. [AGM13] gave the first provable learning algorithm for overcomplete dictionaries that runs in polynomial-time; they required $x$ to be $n^{1/2-\epsilon}$ -sparse (roughly speaking) and $A$ to be incoherent. Independently, Agarwal et al. [AAN13] gave a weaker algorithm that also assumes $A$ is incoherent and allows $x$ to be $n^{1/4}$ -sparse. Thus all three of these recent algorithms cannot handle sparsity more than $\sqrt{n}$ , and this is a fundamental limitation of the technique: they require two random $x,x^{\prime}$ to intersect in no more than $O(1)$ coordinates with high probability, which fails to hold when sparsity $\gg\sqrt{n}$ . Since sparse recovery (where $A$ is known) is possible even up to sparsity $\Omega(n)$ , this raised the question whether dictionary learning is possible in that regime. In this paper we will refer to feature vectors with sparsity $n/poly(\log n)$ as slightly-sparse, since methods in this paper do not seem to allow density higher than that.

In our recent paper on deep learning ([ABGM13], Section 7) we showed how to solve dictionary learning in this regime for dictionaries which are adjacency matrices of random weighted sparse bipartite graphs; these are known to allow sparse recovery albeit with a slight twist in the problem definition [Ind08, JXHC09, BGI+08]. Since real-life dictionaries are probably not random, this raises the question whether dictionary learning is possible in the slightly sparse case for other dictionaries. The current paper gives quasipolynomial-time algorithms for learning more such dictionaries. The running time is quasipolynomial time because it uses limited enumeration (similarly, e.g., to algorithms for learning gaussian mixtures). Now we discuss this class of dictionaries.

Some of our discussion below refers to nonnegative dictionary learning, which constrains matrices $A$ and hidden vector $x$ to have nonnegative entries. This is a popular variant proposed by Hoyer [Hoy02], motivated again partly by the neural analogy. Algorithms like NN-K-SVD [AEB05] were then applied to image classification tasks. This version is also related to nonnegative matrix factorization [LS99], which has been observed to lead to factorizations that are usually sparser and more local than traditional methods like SVD.

Now we discuss what versions of dictionary learning make more sense than others. For exposition purposes we refer to the coordinates of the hidden vector $x$ as features, and those of the visible vector $y=Ax$ as pixels, even though the discussion applies to more than just computer vision. Dictionary learning as defined here —which is the standard definition—assumes that features’ effect on the pixels add linearly.

But, the problem definition is somewhat arbitrary. On the one hand one could consider more general (and nonlinear) versions of this problem —for instance in vision, dictionary learning is part of a system that has to deal with occlusions among objects that may hide part of a feature, and to incorporate the fact that features may be present with an arbitrary translation/rotation. On the other hand, one could consider more specific versions that place restrictions on the dictionary, since not all dictionaries may make sense in applications. We consider this latter possibility now, with the usual caveat that it is nontrivial to cleanly formalize properties of real-life instances.

One reasonable property of real-life dictionaries is that each feature does not involve most pixels. This implies that column vectors of $A$ are relatively sparse. Thus matrices with RIP property —at least if they are dense— do not seem a good matchBy contrast, in the usual setting of compressed sensing, the matrix provides a basis for making measurements, and its density is a nonissue..

Another intuitive property is that features are individually recoverable, which means, roughly speaking, that to an observer who knows the dictionary, the presence of a particular feature should not be confusable with the effects produced by the usual distribution of other features (this is an average-case condition, since $x$ satisfies stochastic assumptions). In particular, one should be able to detect its presence by looking only at the pixels it would affect.

Thus it becomes clear that not all matrices that allow sparse recovery are of equal interests. The paper of Arora et al. [AGM13] restricts attention to incoherent matrices, where the columns have pairwise inner product at most $\mu/\sqrt{n}$ where $\mu$ is small, like $\mbox{poly}(\log n)$ . These make sense on both the above counts. First, they can have fairly sparse columns. Secondly they satisfy $A^{T}A\approx I$ , so given $Ax$ one can take its inner product with the $i$ th column $A_{i}$ to roughly determine the extent to which feature $i$ is present. But incoherent matrices restrict sparsity to $O(\sqrt{n})$ , so one is tempted by RIP matrices but, as mentioned, their columns are fairly dense. Furthermore, RIP matrices were designed to allow sparse recovery for worst-case feature vectors whereas in dictionary learning these are stochastic. As mentioned, sparse random graphs (with random edges weights in $$) check all the right boxes (and were handled in our recent paper on deep learning) but require positing that the dictionary has no structure. The goal in the current paper is to move beyond random graphs.

Let us try to formulate the property that features are individually recoverable. We hope this definition and discussion will stimulate further work (similar, we hope, to Dasgupta’s formalization of separability for gaussian mixtures [Das99]). Let us assume that the coordinates of $x$ are pairwise independent. Then the presence of the $i$ th feature (i.e., $x_{i}\neq 0$ ) changes the conditional distribution of those pixels involved in $A_{i}$ , the $i$ th column of $A$ . Features are said to be individually recoverable if this change in conditional distribution is not obtainable from other combinations of features that arise with reasonable probability. This statistical property is hard to work with and below we suggest some (possibly too strong) combinatorial properties of the support of $A$ that imply it. Better formalizations seem quite plausible and are left for future work.

Definitions and Results

The $j$ th column of $A$ is denoted by $A_{j}$ , the $i$ th row of $A$ by $A^{(i)}$ , and the entries of $A$ are denoted by $A^{(i)}_{j}$ .

For ease of exposition we first describe our learning algorithm for nonnegative dictionaries (i.e., $A^{(i)}_{j}\geq 0$ , for all $i\in[n],j\in[m]$ ) and then in Section 4 describe the generalization to the general case. Note that the subcase of nonnegative dictionaries is also of practical interest.

(Every feature has significant effect on pixels) There are at least $d$ edges with weights larger than $\sigma$ for every feature $j$ . That is, the degree of $G_{\sigma}$ on the feature side is always larger than $d$ .

(Low pairwise intersections among features) In $G_{\tau}$ the neighborhood of each feature (that is, $\{i\in[n]:A^{(i)}_{j}\geq\tau\}$ ) has intersection up to $d/10$ (with total weight $<d\sigma/10$ ) with each of at most $o(1/\sqrt{\rho})$ other features, and intersection at most $\kappa$ with the neighborhood of each remaining features. Here $\tau$ is $O_{\theta}(1/\log n)$ as explained below and $\kappa=O_{\theta}(d/\log^{2}n)$ .

Guideline through notation: We will think of $\sigma\leq 1$ as a small constant, $\Lambda\geq 1$ a constant, and $\Delta$ a sufficiently large constant which is used to control the assumption. Let $\theta=(\sigma,\Lambda,\Delta)$ and we use the notation $O_{\theta}(\cdot)$ to hide the dependencies of $\sigma,\Lambda,\Delta$ . Also, we think of $m$ as not much larger than $n$ , $\rho<1/\mbox{poly}(\log n)$ , and $d\ll n$ . The normalization assumption implies (for all practical purposes in the algorithm) that $md\rho\in[n/\Lambda,n/\tau]$ . We typically think of $d$ as $1/\rho$ , hence a running time of $m^{d}$ would be bad (though it is unclear a priori how to even achieve that).

Precisely, for our algorithms to work, we need $d\geq\Delta\Lambda\log^{2}n/\sigma^{2}$ , $\tau=O(\sigma^{4}/\Delta\Lambda^{2}\log n)=O_{\theta}(1/\log n)$ and $\kappa=O(\sigma^{8}d\nicefrac{{}}{{\log^{2}n\Delta^{2}\Lambda^{6}}})=O_{\theta}(d/\log^{2}n)$ for some sufficiently large constant $\Delta$ and the density $\rho=o(\sigma^{5}\nicefrac{{}}{{\Lambda^{6.5}\log^{2.5}n}})=o_{\theta}(1/\log^{2.5}n)$ . Note that if $G_{\tau}$ were like a random graph (i.e. if features affect random sets of $d$ pixels) when $d^{2}\ll n$ , the pairwise intersection $\kappa$ between the neighborhoods of two features in $G_{\tau}$ would be $O(1)$ . However, we allow these intersections to be $\kappa=O_{\theta}(d/\log^{2}n)$ .

Now we give a stronger version of Assumption 2 which will allow a stronger algorithm.

In $G_{\tau}$ , the pairwise intersection of the neighborhoods of any two features $j,k$ is less than $\kappa$ , where $\tau=O_{\theta}(1/\log n)$ and $\kappa=O_{\theta}(d/\log^{2}n)$ .

The algorithm can only learn the real-valued matrix approximately. Two dictionaries are close if they satisfy the following definition:

Under Assumptions 1 and 2, when $\rho=o(\sigma^{5}/\Lambda^{6.5}\log^{2.5}n)=o_{\theta}(1/\log^{2.5}n)$ , Algorithm 2 runs in $n^{O(\Lambda\log^{2}n/\sigma^{4})}$ time, uses $\mbox{poly}(n)$ samples and outputs a matrix that is $o(\rho)$ -equivalent to the true dictionary $A$ . Furthermore, under Assumptions 1 and 2’ the same algorithm returns a dictionary that is $n^{-C}$ -equivalent to the true dictionary, while using $n^{4C+3}$ samples, where $C$ is a large constant depending on $\Delta$ . Recall that $\Delta$ is a sufficiently large constant that controls the parameters of the assumptions.

2 Dictionaries with negative entries

When the edges can be both positive and negative, it is no longer valid to assume the expectation of $y_{i}$ ’s are equal to $1$ . Instead, we choose a different normalization: the variances of $y_{i}$ ’s are 1. We still assume magnitude of edge weights are at most $\Lambda$ , and that features don’t overlap a lot as described in Assumption 1 and 2. We also need one more assumption to bound the variance contributed by the small entries.

The degree of $G_{\sigma}$ on side of $x$ is always larger than $2d$ .

In $G_{\tau}$ , the pairwise intersection of the neighborhoods of any two features $j,k$ is less than $\kappa$ ,where $\tau=O_{\theta}(1/\log n)$ and $\kappa=O_{\theta}(d/\log^{2}n)$ .

(small entries of $A$ don’t cause large effects) $\rho||A^{(i)}_{\leq\tau}||_{2}^{2}\leq\gamma$ , where $A^{(i)}_{\leq\delta}$ be the vector that only contains the entries of $A^{(i)}$ that are at most $\delta$ , and $\gamma=\sigma^{4}\nicefrac{{}}{{2\Delta\Lambda^{2}\log n}}$ .

Note that Assumption G1 differs from Assumption 1 by a constant factor 2 just to simplify some notations later. Assumption G2’ is the same as before.

This assumption G3 intuitively says that for each $y_{i}=\sum_{k}A^{(i)}_{k}x_{k}$ , the smaller $A^{(i)}_{k}$ ’s should not contribute too much to the variance of $y_{i}$ . This is automatically satisfied for nonnegative dictionaries because there can be no cancellations. Notice that this assumption is talking about rows of matrix $A$ (corresponding to pixels), whereas the earlier assumptions talk about columns of $A$ (corresponding to features). Also, consider $\tau$ to be the smallest number between what is required by Assumption G2’ and G3.

In term of parameters, we still need $d\geq\Delta\Lambda\log^{2}n/\sigma^{2}$ , and $\kappa=O(\sigma^{8}d/\log^{2}n\Delta^{2}\Lambda^{6})$ $=O(d/\log^{2}n)$ . As before $\Delta$ is a large enough constant.

Under Assumptions G1, G2’ and G3, when $\rho=o(\sigma^{5}/\Lambda^{6.5}\log^{2.5}n)=o_{\theta}(1/\log^{2.5}n)$ there is an algorithm that runs in $n^{O(\Delta\Lambda\log^{2}n/\sigma^{2})}$ time, uses $n^{4C+5}m$ samples and outputs a matrix that is $n^{-C}$ -equivalent to the true dictionary $A$ , where $C$ is a constant depending on $\Delta$ .

The algorithm and the proof of Theorem 2 are sketched in Section 4.

Nonnegative Dictionary Learning

Recall that dictionary learning seems hard because both $A$ and $x$ are unknown. To get around this problem, previous works (e.g. [AGM13]) try to extract information about the assignment $x$ without first learning $A$ (but assuming nice properties of $A$ ). After finding $x$ , recovering $A$ becomes easy. In [AGM13] the unknown $x$ ’s were recovered via an overlapping clustering procedure. The procedure relies on incoherence of $A$ , as when $A$ is incoherent it is possible to test whether the support of $x^{1}$ , $x^{2}$ intersect. This idea fails when $x$ is only slightly sparse, because in this setting the supports of $x^{1},x^{2}$ always have a large intersection.

Our algorithm here relies on correlation among pixels. The key observation is: if the $j$ th bit in $x$ is 1, then $Ax=A_{j}+\sum_{k\neq j}A_{k}x_{k}$ . Pixels with high values in $A_{j}$ tend to be elevated above their mean values (recall $A$ is nonnegative). At first it is unclear how this simultaneous elevation can be spotted, since $A_{j}$ is unknown and these elevations/correlations among pixels are much smaller than the standard deviation of individual pixels. Therefore we look for local regions —small subsets of pixels— in $A_{j}$ where this effect is significant in the aggregate (i.e., sum of pixel values), and can be used to consistently predict the value of $x_{j}$ . These are called the signature sets (see Definition 2). If we can identify signature sets, they can give us a good estimation of whether the feature $x_{j}$ is present.

Since the signature sets are small, in quasi-polynomial time we can afford to enumerate all sets of that size, and check if the pixels in these sets are likely to be elevated together. However, this does not solve the problem, because there can be many sets —called correlated sets below— that show similar correlations and look similar to signature sets. It is hard to separate signature sets from other correlated sets when the size of the set is small. This leads to the next idea: try to expand a signature set by first estimating the corresponding column of $A$ , and then picking large entries in that column. The resulting sets are called expanded signature sets; these have size $d$ (and hence could not have been found by exhaustive guessing alone). If the set being expanded is indeed a signature set, this expansion process can correctly estimate the column of $A$ . We give algorithms that can find expanded signature sets, and using these sets we can get a rough estimation for the matrix $A$ . Finally, we also give a procedure that leverages the individually recoverable properties of the features, and refines the solution to be inverse polynomially equivalent to the true dictionary.

The high level algorithm is described in Algorithm 2 (the concepts such as correlated sets, and empirical bias are defined later). To simplify the proof the algorithm description uses Assumption 2’; we summarize later (in Section 3.4) what changes with Assumption 2.

The main algorithm has three main steps. Section 3.1 explains how to test for correlated sets and expand a set (1-2 in Algorithm 2); Section 3.2 shows how to find expanded signature sets and a rough estimation of $A$ (3-6 in Algorithm 2); finally Section 3.3 shows how to refine the solution and get $\hat{A}$ that is inverse polynomially equivalent to $A$ (7-10 in Algorithm 2).

We consider a set $T$ of size $t=\Omega(\mbox{poly}\log n)$ (to be specified later), and denote by $\beta_{T}$ the random variable representing the sum of all pixels in $T$ , i.e., $\beta_{T}=\sum_{i\in T}y_{i}$ . We can expand $\beta_{T}$ as

Let $\beta_{j,T}=\left(\sum_{i\in T}A^{(i)}_{j}\right)$ be the contribution of $x_{j}$ to the sum $\beta_{T}$ , then $\beta_{T}$ is just

Now we make this precise by defining such set $T$ with only one large coefficient $\beta_{k,T}$ as signature sets.

A set $T$ of size $t$ is a signature set for $x_{j}$ , if $\beta_{j,T}\geq\sigma t$ , and for all $k\neq j$ , the contribution $\beta_{k,T}\leq\sigma^{2}t\nicefrac{{}}{{\Delta\log n}}$ . Here $\Delta$ is a large enough constant.

The following lemma formalizes the earlier intuition that if $T$ is a signature set for $x_{j}$ , then a large $\beta_{T}$ is highly correlated with the event $x_{j}=1$ .

$\Pr[E_{1}]+n^{-2C}\geq\Pr[E_{2}]\geq\Pr[E_{1}]-n^{-2C}$ .

$\Pr[E_{2}|E_{1}]\geq 1-n^{-2C}$ , and $\Pr[E_{2}|E_{1}^{c}]\leq n^{-2C}$ .

where $C$ is a large constant depending $\Delta$ .

Part (2) immediately follows: if $x_{j}=1$ , then $\beta_{T}<t+0.9\sigma t$ iff the sum deviates from its expectation by more than $\sigma t/20$ , which happens with probability $<n^{-2C}$ . So also if $x_{j}=0$ , $E_{2}$ occurs with probability $<n^{-2C}$ .

This then implies part (1), since the probability of $E_{1}$ is precisely $\rho$ .

Combining the (1) and (2), and using Bayes’ rule $\Pr[E_{1}|E_{2}]=\Pr[E_{2}|E_{1}]\Pr[E_{1}]/\Pr[E_{2}]$ , we obtain (3).

Thus if we can find a signature set for $x_{j}$ , we would roughly know the samples in which $x_{j}=1$ . The following lemma shows that assuming the low pairwise assumptions among features, there exists a signature set for every feature $x_{j}$ .

Suppose $A$ satisfies Assumptions 1 and 2, let $t=\Omega(\Lambda\Delta\log^{2}n/\sigma^{2})$ , then for any $j\in[n]$ , there exists a signature set of size $t$ for node $x_{j}$ .

We show the existence by probabilistic method. By Assumption 1, node $x_{j}$ has at least $d$ neighbors in $G_{\sigma}$ . Let $T$ be a uniformly random set of $t$ neighbors of $x_{j}$ in $G_{\sigma}$ . Now by the definition of $G_{\sigma}$ we have $\beta_{j,T}\geq\sigma t$ .

Using a bound on intersection size (Assumption 2’) followed by Chernoff bound, we show that $T$ is a signature set with good probability. For $k\neq j$ , let $f_{k,T}$ be the number of edges from $x_{k}$ to $T$ in graph $G_{\tau}$ . Then we can upperbound $\beta_{k,T}$ by $t\tau+f_{k,T}\Lambda$ since all edge weights are at most $\Lambda$ and there are at most $f_{j,T}$ edges with weights larger than $\tau$ . Using simple Chernoff bound and union bound, we know that with probability at least $1-1/n$ , for all $k\neq j$ , $f_{k,T}\leq 4\log n$ . Therefore $\beta_{k,T}\leq t\tau+f_{k,T}\Lambda\leq\sigma^{2}t/(\Delta\log n)$ for $t\geq\Omega(\Lambda\Delta\log^{2}n/\sigma^{2})$ , and $\tau=O(\sigma^{2}\nicefrac{{}}{{\Delta\log n}})$ .

Although signature sets exist for all $x_{j}$ , it is difficult to find them; even if we enumerate all subsets of size $t$ , it is not clear how to know when we found a signature set. Thus we first look for “correlated” sets, which are defined as follows:

It follows easily (Lemma 3) that signature sets must be correlated sets.

If $T$ of size $t$ is a signature set for $x_{j}$ , and $t=\omega(\sqrt{\log n})$ , then $T$ is a correlated set.

Although signature sets are all correlated sets, the other direction is far from true. There can be many correlated sets that are not signature sets . A simple counterexample would be that there are $j$ and $j^{\prime}$ such that both $\beta_{j,T}$ and $\beta_{j^{\prime},T}$ are larger than $\sigma t$ . This kind of counterexample seems inevitable for any test on a set $T$ of polylogarithmic size.

2 Identify Expanded Signature Sets

The following notion of empirical bias is a more precise way (compared to correlated set) to measure the simultaneous elevation effect.

The key lemma in this part shows the expanded set with largest empirical bias must be an expanded signature set:

We make the arguments above precise by the following claims. First, we shall show there cannot be too many large coefficients $\beta_{j,D}$ for any set $D$ of size $d$ (although we only apply the claim on expanded sets).

This implies that $|K_{large}|\leq O(\Delta\Lambda^{3}\log n/\sigma^{4})$ , when $\kappa=O(\sigma^{8}d\nicefrac{{}}{{\Delta^{2}\Lambda^{6}\log^{2}n}})$ . Note that any subset of $K_{large}$ also satisfies equation (3), thus we don’t have to worry about the other range of the solution of (3)

Now we have found expanded signature sets, we can then apply Algorithm 1 (but with threshold $0.6\sigma d$ instead of $0.9\sigma d$ ) on that to get an estimation.

Combining the two parts, we know the number of samples that is in $E_{1}\oplus E_{2}$ (the symmetric difference between $E_{1}$ and $E_{2}$ ) is bounded by $\rho N\cdot o(\sigma/\sqrt{\Lambda\log n})$ . Also, with high probability $(1-n^{-C})$ all the samples have entries bounded by $O(\sqrt{\Lambda\log n})$ by Bernstein’s inequality (variance of $y_{i}$ is bounded by $\sum_{j}\rho(A^{(i)}_{j})^{2}\leq\max_{j}A^{(i)}_{j}\sum_{j}\rho A^{(i)}_{j}\leq\Lambda$ ). Notice that this is a statement of the entire sample independent of the set $T$ , so we do not need to apply union bound over all expanded signature sets.

The previous lemma looks very similar to the lemma for signature sets, however, the benefit is we know how to find a set that is guaranteed to be expanded signature set! So we can iteratively find all expanded signature sets.

The proof is almost identical to Lemma 8.

3 Getting an Equivalent Dictionary

In the final step, we look at all the large entries in the column $A_{j}$ , and use them to identify whether feature $x_{j}$ is 1 or 0. The ability to do this justifies the individually recoverable property of the dictionary.

By Assumption 2, for any $k\neq j$ , the number of edges in $G_{\tau}$ between $k$ and $S_{j}$ is bounded by $\kappa$ , so $\beta_{k,S_{j}}\leq\tau\left|S_{j}\right|+\kappa\Lambda\leq\sigma^{2}\left|S_{j}\right|/\Delta\log n$ .

Since $S_{j}$ has a unique large coefficient $\beta_{j,S_{j}}$ , and the rest of the coefficients are much smaller, when $\Delta$ is large enough, and $N\geq n^{4C+\delta}/\rho^{3}$ we know $\hat{A}_{j}$ is entry-wise $n^{-2C}/\log n$ close to $A_{j}$ (this is using the same argument as in Lemma 6). We shall show this is enough to proof $n^{-C}$ -equivalence between $\hat{A}$ and $A$ .

The proof is an easy application of Bernstein’s inequality (see Appendix A.1).

We now formally write down the steps in the algorithm.

4 Working with Assumption 2

In order to assume Assumption 2 instead of 2’, we need to change the definition of signature sets to allow $o(1/\sqrt{\rho})$ “moderately large” ( $\sigma t/10$ ) entries. This makes the definition look similar to expanded signature sets. Such signature sets still exist by similar probabilistic argument as in Lemma 4. Lemma 7 and Claims 9 and 10 can also be adapted.

Finally, for Lemma 14, the guarantee will be weaker (there can be $o(1/\sqrt{\rho})$ moderately large coefficients). The algorithm will only estimate $x_{j}$ incorrectly if at least $6$ such coefficients are “on” (has the corresponding $x_{j}$ being 1), which happens with less than $o(\rho^{3})$ probability. By argument similar to Lemma 6 and Lemma 14 we get the first part of Theorem 1.

General Case

With minor modifications, our algorithm and its analysis can be adapted to the general case in which the matrix $A$ can have both positive and negative entries.

We follow the outline from the non-negative case, and look at sets $T$ of size $t$ . The quantities $\beta_{T}$ and $\beta_{j,T}$ are defined exactly the same as in Section 3.1. Additionally, let $\nu_{T}$ be the standard deviation of $\beta_{T}$ , and let $\nu_{-j,T}$ be the standard deviation of $\beta_{T}-\beta_{j,T}x_{j}$ . That is,

The definition of signature sets requires an additional condition to take into account the standard deviations.

A set $T$ of size $t$ is a signature set for $x_{j}$ , if for some large constant $\Delta$ , we have: (a) $|\beta_{j,T}|\geq\sigma t$ , (b) for all $k\neq j$ , the contribution $|\beta_{k,T}|\leq\sigma^{2}t/(\Delta\log n)$ , and additionally, (c) $\nu_{-j,T}\leq\sigma t/\sqrt{\Delta\log n}$ .

In the nonnegative case the additional condition $\nu_{-j,T}\leq\sigma t/\sqrt{\Delta\log n}$ was automatically implied by nonnegativity and scaling. Now we use Assumption G3 to show there exist $T$ in which (c) is true along with the other properties. To do that, we prove a simple lemma which lets us bound the variance (the same lemma is also used in other places).

Let $T$ be a set of size $t$ and $S$ be an arbitrary subset of features, and consider the sum $\beta_{S,T}=\sum_{j\in S}\beta_{j,T}x_{j}$ . Suppose for each $j\in S$ , the number of edges from $j$ to $T$ in graph $G_{\tau}$ is bounded by $W$ . Then the variance of $\beta_{S,T}$ is bounded by $2tW+2t^{2}\gamma$ .

The idea is to split the weights $A^{(i)}_{j}$ into the big and small ones (threshold being $\tau$ ). Intuitively, on one hand, the contribution to the variance from large weights is bounded above because the number of such large edges in bounded by $W$ . On the other hand, by assumption (3), the total variance of small weights is less than $\gamma$ , which implies that the contribution of small weight to the variance is also bounded. Formally, we have

In the fourth line we used Cauchy-Schwarz inequality and in the last step, we used Assumption G3 about the total variance due to small terms being small, as well as the normalization of the variance in each pixel.

Suppose $A$ satisfies our assumptions for general dictionaries, and let $t=\Omega(\Lambda\Delta\log^{2}n/\sigma^{2})$ . Then for any $j\in[n]$ , there exists a general signature set of size $t$ for node $x_{j}$ (as in Definition 7).

As before, we use the probabilistic method. Suppose we fix some $j$ . By Assumption G1, in $G_{\sigma}$ , node $x_{j}$ has either at least $d$ positive neighbors or $d$ negative ones. W.l.o.g., let us assume there are $d$ negative neighbors. Let $T$ be uniformly random subset of size $t$ of these negative neighbors. By definition of $G_{\sigma}$ , we have $\beta_{j,T}\leq-\sigma t$ .

For $k\neq j$ , let $f_{k,T}$ be the number of edges from $x_{k}$ to $T$ in graph $G_{\tau}$ . Using the same argument as in the proof of Lemma 4, we have $f_{k,T}\leq 4\log n$ w.h.p. for all such $k\neq j$ . Thus $|\beta_{k,T}|\leq t\tau+f_{k,T}\Lambda\leq\sigma^{2}t/(\Delta\log n)$ . Thus it remains to bound $\nu_{-j,T}$ .

We could apply Lemma 15 with $W=4\log n\geq f_{k,T}$ , and $S=[m]\setminus\{j\}$ on set $T$ : we get $\nu_{-j,T}^{2}\leq 2tW+2t^{2}\gamma$ . Recall that $\gamma=\sigma^{2}\nicefrac{{}}{{3\Delta^{2}\log n}}$ and thus $\nu_{-j,T}\leq\sigma t\nicefrac{{}}{{\sqrt{\Delta\log n}}}$ .

The proof of Lemma 3 now follows in the general case (here we will use the variance bound (c) in the general definition of signature sets), except that we need to redefine event $E_{2}$ to handle the negative case. For completeness, we state the general version of Lemma 3 in Appendix A.2. As before, signature sets give a great idea of whether $x_{j}=1$ .

Let us now define correlated sets: here we need to consider both positive and negative bias

Our earlier definitions of expanded signature sets and bias can also be adapted naturally:

Let us now intuitively describe why the analog of Lemma 8 holds in the general case. We provides the formal statement and the proof in Appendix A.2

The main lemma in the nonnegative case, which shows that Algorithm 1 roughly recovers a column, is Lemma 11. The proof uses the property that signature sets are elevated “almost iff” the $x_{j}=1$ to conclude that we get a good approximation to one of the columns. We have seen that this also holds in the general case, and since the rest of the argument deals only with the magnitudes of the entries, we conclude that we can roughly recover a column also in the general case. Let us state this formally.

Once we have all the entries which are $>\sigma/2$ in magnitude, we can use the ‘refinement’ trick of Lemma 13 to conclude that we can recover the entries.

When the number of samples is at least $n^{4C+3}m$ , the matrices $A$ and $\hat{A}$ are entry-wise $n^{-2C}m^{-1/2}$ close. Further, the two dictionaries are $n^{-C}$ -equivalent.

The first part of the proof (showing entry-wise closeness) is very similar to Lemma 6. In order to show $n^{-C}$ equivalent, notice when the entries are very close this just follows from Bernstein’s inequality, with variance bounded by $n^{-4C}m^{-1}\cdot m$ . In Section 3 we do not just use this bound, because we want to be able to also handle the case when the entrywise error is only inverse polylog (for Assumption 2).

References

Appendix A Full Proofs

In this section we give the omitted proofs.

Let us focus on the $i$ th row of $A-\hat{A}$ and denote it by $w$ . Then we have $\lVert w\rVert_{1}\leq\lVert A\rVert_{1}+\lVert\hat{A}\rVert_{1}\leq O(1/\rho)$ . Now consider the random variable $Z=\sum_{j}w_{j}x_{j}$ , where $x_{j}$ are i.i.d. Bernoulli r.v.s with probability $\rho$ of being $1$ . Then by Bernstein’s inequality (Theorem 23), we have

Since $|w_{j}|<\delta$ for all $j$ , we can bound the variance as $\rho\cdot\sum_{j}w_{j}^{2}\leq\delta\rho\cdot\sum_{j}|w_{j}|\leq 2\delta$ .

Thus setting $t=(4\delta\log n)^{1/2}$ (notice that this is the $t$ in Bernstein’s inequality, not the same as the size of signature sets), we obtain an upper bound of $1/\text{poly}(n)$ on the probability.

A.2 Missing Lemmas and Proofs of Section 4