Distributed Low-rank Subspace Segmentation

Introduction

Visual data, though innately high dimensional, often reside in or lie close to a union of low-dimensional subspaces. These subspaces might reflect physical constraints on the objects comprising images and video (e.g., faces under varying illumination or trajectories of rigid objects ) or naturally occurring variations in production (e.g., digits hand-written by different individuals ). Subspace segmentation techniques model these classes of data by recovering bases for the multiple underlying subspaces . Applications include image clustering , segmentation of images, video, and motion , and affinity graph construction for semi-supervised learning .

One promising, convex formulation of the subspace segmentation problem is the low-rank representation (LRR) program of Liu et al. :

Much of the computational burden in solving LRR stems from the nuclear norm penalty, which is known to encourage low-rank solutions, so one might hope to leverage the large body of past work on parallel and distributed matrix factorization to improve the scalability of LRR. Unfortunately, these techniques are tailored to optimization problems with losses and constraints that decouple across the entries of the input matrix. This decoupling requirement is violated in the LRR problem due to the ${\mathbf{M}}={\mathbf{M}}{\mathbf{Z}}+{\mathbf{S}}$ constraint of Eq. (1), and this non-decomposable constraint introduces new algorithmic and analytic challenges that do not arise in decomposable matrix factorization problems.

To address these challenges, we develop, analyze, and evaluate a provably accurate divide-and-conquer approach to large-scale subspace segmentation that specifically accounts for the non-decomposable structure of the LRR problem. Our contributions are three-fold:

Algorithm: We introduce a parallel, divide-and-conquer approximation algorithm for LRR that is suitable for large-scale subspace segmentation problems. Scalability is achieved by dividing the original LRR problem into computationally tractable and communication-free subproblems, solving the subproblems in parallel, and combining the results using a technique from randomized matrix approximation. Our algorithm, which we call DFC-LRR, is based on the principles of the Divide-Factor-Combine (DFC) framework for decomposable matrix factorization but can cope with the non-decomposable constraints of LRR.

Analysis: We characterize the segmentation behavior of our new algorithm, showing that DFC-LRR maintains the segmentation guarantees of the original LRR algorithm with high probability, even while enjoying substantial speed-ups over its namesake. Our new analysis features a significant broadening of the original LRR theory to treat the richer class of LRR-type subproblems that arise in DFC-LRR. Moreover, since our ultimate goal is subspace segmentation and not matrix recovery, our theory guarantees correctness under a more substantial reduction of problem complexity than the work of (see Sec. 3.2 for more details).

Applications: We first present results on face clustering and synthetic subspace segmentation to demonstrate that DFC-LRR achieves accuracy comparable to LRR in a fraction of the time. We then propose and validate a novel application of the LRR methodology to large-scale graph-based semi-supervised learning. While LRR has been used to construct affinity graphs for semi-supervised learning in the past , prior attempts have failed to scale to the sizes of real-world datasets. Leveraging the favorable computational properties of DFC-LRR, we propose a scalable strategy for constructing such subspace affinity graphs. We apply our methodology to a variety of computer vision tasks – multimedia event detection, concept detection, and image tagging – demonstrating an order of magnitude improvement in speed and accuracy that exceeds the state of the art.

The remainder of the paper is organized as follows. In Section 2 we first review the low-rank representation approach to subspace segmentation and then introduce our novel DFC-LRR algorithm. Next, we present our theoretical analysis of DFC-LRR in Section 3. Section 4 highlights the accuracy and efficiency of DFC-LRR on a variety of computer vision tasks. We present subspace segmentation results on simulated and real-world data in Section 4.1. In Section 4.2 we present our novel application of DFC-LRR to graph-based semi-supervised learning problems, and we conclude in Section 5.

Divide-and-Conquer Segmentation

In this section, we review the LRR approach to subspace segmentation and present our novel algorithm, DFC-LRR.

The LRR approach of seeks to recover the row space of ${\mathbf{L}}_{0}$ by solving the convex optimization problem presented in Eq. (1). Importantly, the LRR solution comes with a guarantee of correctness: the column space of $\hat{{\mathbf{Z}}}$ is exactly equal to the row space of ${\mathbf{L}}_{0}$ whenever certain technical conditions are met (see Sec. 3 for more details).

Moreover, as we will show in this work, LRR is also well-suited to the construction of affinity graphs for semi-supervised learning. In this setting, the goal is to define an affinity graph in which nodes correspond to data points and edge weights exist between nodes drawn from the same subspace. LRR can thus be used to recover the block-sparse structure of the graph’s affinity matrix, and these affinities can be used for semi-supervised label propagation.

2 Divide-Factor-Combine LRR (DFC-LRR)

We now present our scalable divide-and-conquer algorithm, called DFC-LRR, for LRR-based subspace segmentation. DFC-LRR extends the principles of the DFC framework of to a new non-decomposable problem. The DFC-LRR algorithm is summarized in Algorithm 1, and we next describe each step in further detail. D step - Divide input matrix into submatrices: DFC-LRR randomly partitions the columns of ${\mathbf{M}}$ into $t$ $l$-column submatrices, $\{{\mathbf{C}}_{1},\ldots,{\mathbf{C}}_{t}\}$. For simplicity, we assume that $t$ divides $n$ evenly. F step - Factor submatrices in parallel: DFC-LRR solves $t$ subproblems in parallel. The $i$th LRR subproblem is of the form

where the input matrix ${\mathbf{M}}$ is used as a dictionary but only a subset of columns is used as the observations.An alternative formulation involves replacing both instances of ${\mathbf{M}}$ with ${\mathbf{C}}_{i}$ in Eq. (1). The resulting low-rank estimate $\hat{\mathbf{Z}}_{i}$ would have dimensions $l\times l$, and the C step of DFC-LRR would compute a low-rank approximation on the block-diagonal matrix diag($\hat{\mathbf{Z}}_{1},\hat{\mathbf{Z}}_{2},\ldots,\hat{\mathbf{Z}}_{t}$). A typical LRR algorithm can be easily modified to solve Eq. (2) and will return a low-rank estimate $\hat{\mathbf{Z}}_{i}$ in factored form. C step - Combine submatrix estimates: DFC-LRR generates a final approximation ${\hat{{\mathbf{Z}}}^{proj}}$ to the low-rank LRR solution $\hat{{\mathbf{Z}}}$ by projecting $[\hat{\mathbf{Z}}_{1},\ldots,\hat{\mathbf{Z}}_{t}]$ onto the column space of $\hat{\mathbf{Z}}_{1}$. This column projection technique is commonly used to produce randomized low-rank matrix factorizations and was also employed by the DFC-Proj algorithm of . Runtime: As noted in , many state-of-the-art solvers for nuclear-norm regularized problems like Eq. (1) have $\Omega(mnk_{M})$ per-iteration time complexity due to the rank-$k_{M}$ truncated SVD required on each iteration. DFC-LRR reduces this per-iteration complexity significantly and requires just O$(mlk_{C_{i}})$ time for the $i$th subproblem. Performing the subsequent column projection step is relatively cheap computationally, since an LRR solver can return its solution in factored form. Indeed, if we define $k^{\prime}\triangleq\max_{i}k_{C_{i}}$, then the column projection step of DFC-LRR requires only O$(mk^{\prime 2}+lk^{\prime 2})$ time.

Theoretical Analysis

Despite the significant reduction in computational complexity, DFC-LRR provably maintains the strong theoretical guarantees of the LRR algorithm. To make this statement precise, we first review the technical conditions for accurate row space recovery required by LRR.

The LRR analysis of Liu et al. relies on two key quantities, the rank of the clean data matrix ${\mathbf{L}}_{0}$ and the coherence of the singular vectors ${\mathbf{V}}_{L_{0}}$. We combine these properties into a single definition:

Intuitively, when the coherence $\mu$ is small, information is well-distributed across the rows of a matrix, and the row space is easier to recover from outlier corruption. Using these properties, Liu et al. established the following recovery guarantee for LRR.

In other words, LRR can exactly recover the row space of ${\mathbf{L}}_{0}$ even when a constant fraction $\gamma^{*}$ of the columns has been corrupted by outliers. As the rank $r$ and coherence $\mu$ shrink, $\gamma^{*}$ grows allowing greater outlier tolerance.

2 High Probability Subspace Segmentation

Our main theoretical result shows that, with high probability and under the same conditions that guarantee the accuracy of LRR, DFC-LRR also exactly recovers the row space of ${\mathbf{L}}_{0}$. Recall that in our independent subspace setting accurate row space recovery is tantamount to correct segmentation of the columns of ${\mathbf{L}}_{0}$. The proof of our result, which generalizes the LRR analysis of to a broader class of optimization problems and adapts the DFC analysis of , can be found in the appendix.

Fix any failure probability $\delta>0$. Under the conditions of Thm, 2, let ${\hat{{\mathbf{Z}}}^{proj}}$ be a solution returned by DFC-LRR. Then there exists a constant $\gamma^{*}$ (depending on $\mu$ and $r$) for which the column space of ${\hat{{\mathbf{Z}}}^{proj}}$ exactly equals the row space of ${\mathbf{L}}_{0}$ whenever $\lambda=3/(7{\|{{\mathbf{M}}}\|}\sqrt{\gamma^{*}l})$ for each DFC-LRR subproblem, $\gamma\leq\gamma^{*}$, and $t=n/l$ for

Thm. 3 establishes that, like LRR, DFC-LRR can tolerate a constant fraction of its data points being corrupted and still recover the correct subspace segmentation of the clean data points with high probability. When the number of datapoints $n$ is large, solving LRR directly may be prohibitive, but DFC-LRR need only solve a collection of small, tractable subproblems. Indeed, Thm. 3 guarantees high probability recovery for DFC-LRR even when the subproblem size $l$ is logarithmic in $n$. The corresponding reduction in computational complexity allows DFC-LRR to scale to large problems with little sacrifice in accuracy.

Notably, this column sampling complexity is better than that established by in the matrix factorization setting: we require O$(r\log n)$ columns sampled, while requires in the worst case $\Omega(n)$ columns for matrix completion and $\Omega((r\log n)^{2})$ for robust matrix factorization.

Experiments

We now explore the empirical performance of DFC-LRR on a variety of simulated and real-world datasets, first for the traditional task of robust subspace segmentation and next for the more complex task of graph-based semi-supervised learning. Our experiments are designed to show the effectiveness of DFC-LRR both when the theory of Section 3 holds and when it is violated. Our synthetic datasets satisfy the theoretical assumptions of low rank, incoherence, and a small fraction of corrupted columns, while our real-world datasets violate these criteria.

For all of our experiments we use the inexact Augmented Lagrange Multiplier (ALM) algorithm of as our base LRR algorithm. For the subspace segmentation experiments, we set the regularization parameter to the values suggested in previous works , while in our semi-supervised learning experiments we set it to $1/\sqrt{\max{(m,n)}}$ as suggested in prior work.http://perception.csl.illinois.edu/matrix-rank In all experiments we report parallel running times for DFC-LRR, i.e., the time of the longest running subproblem plus the time required to combine submatrix estimates via column projection. All experiments were implemented in Matlab. The simulation studies were run on an x$86$-$64$ architecture using a single $2.60$ Ghz core and $30$GB of main memory, while the real data experiments were performed on an x$86$-$64$ architecture equipped with a 2.67GHz 12-core CPU and 64GB of main memory.

We first aim to verify that DFC-LRR produces accuracy comparable to LRR in significantly less time, both in synthetic and real-world settings. We focus on the standard robust subspace segmentation task of identifying the subspace associated with each input datapoint.

In our first experiments we fix $k=3$, $m=1500$, $r=5$, and $n_{s}=200$, set the regularizer to $\lambda=0.2$, and vary the fraction of outliers. We measure with what frequency LRR and DFC-LRR are able to recover of the row space of ${\mathbf{X}}_{0}$ and identify the outlier columns in ${\mathbf{S}}$, using the same criterion as defined in .Success is determined by whether the oracle constraints of Eq. (8) in the Appendix are satisfied within a tolerance of $10^{-4}$. Figure 1(a) shows average performance over $10$ trials. We see that DFC-LRR performs quite well, as the gaps in the phase transitions between LRR and DFC-LRR are small when sampling $10\%$ of the columns (i.e., $t=10$) and are virtually non-existent when sampling $25\%$ of the columns (i.e., $t=4$).

Figure 1(b) shows corresponding timing results for the accuracy results presented in Figure 1(a). These timing results show substantial speedups in DFC-LRR relative to LRR with a modest tradeoff in accuracy as denoted in Figure 1(a). Note that we only report timing results for values of $\gamma$ for which DFC-LRR was successful in all $10$ trials, i.e., for which the success rate equaled $1.0$ in Figure 1(a). Moreover, Figure 1(c) shows timing results using the same parameter values, except with a fixed fraction of outliers ($\gamma=0.1$) and a variable number of samples in each subspace, i.e., $n_{s}$ ranges from $75$ to $1000$. These timing results also show speedups with minimal loss of accuracy, as in all of these timing experiments, LRR and DFC-LRR were successful in all trials using the same criterion defined in and used in our phase transition experiments of Figure 1(a).

1.2 Face Clustering

We next demonstrate the comparable quality and increased performance of DFC-LRR relative to LRR on real data, namely, a subset of Extended Yale Database B,http://vision.ucsd.edu/~leekc/ExtYaleDatabase a standard face benchmarking dataset. Following the experimental setup in , $640$ frontal face images of $10$ human subjects are chosen, each of which is resized to be $48\times 42$ pixels and forms a 2016-dimensional feature vector. As noted in previous work , a low-dimensional subspace can be effectively used to model face images from one person, and hence face clustering is a natural application of subspace segmentation. Moreover, as illustrated in Figure 2, a significant portion of the faces in this dataset are “corrupted” by shadows, and hence this collection of images is an ideal benchmark for robust subspace segmentation.

As in , we use the feature vector representation of these images to create a $2016\times 640$ dictionary matrix, ${\mathbf{M}}$, and run both LRR and DFC-LRR with the parameter $\lambda$ set to $0.15$. Next, we use the resulting low-rank coefficient matrix $\hat{{\mathbf{Z}}}$ to compute an affinity matrix ${\mathbf{U}}_{\hat{Z}}{\mathbf{U}}_{\hat{Z}}^{\top}$, where ${\mathbf{U}}_{\hat{Z}}$ contains the top left singular vectors of $\hat{{\mathbf{Z}}}$. The affinity matrix is used to cluster the data into $k=10$ clusters (corresponding to the $10$ human subjects) via spectral embedding (to obtain a $10$D feature representation) followed by $k$-means. Following , the comparison of different clustering methods relies on segmentation accuracy. Each of the $10$ clusters is assigned a label based on majority vote of the ground truth labels of the points assigned to the cluster. We evaluate clustering performance of both LRR and DFC-LRR by computing segmentation accuracy as in , i.e., each cluster is assigned a label based on majority vote of the ground truth labels of the points assigned to the cluster. The segmentation accuracy is then computed by averaging the percentage of correctly classified data over all classes.

Figures 3(a) and 3(b) show the computation time and the segmentation accuracy, respectively, for LRR and for DFC-LRR with varying numbers of subproblems (i.e., values of $t$). On this relatively-small data set ($n=640$ faces), LRR requires over $10$ minutes to converge. DFC-LRR demonstrates a roughly linear computational speedup as a function of $t$, comparable accuracies to LRR for smaller values of $t$ and a quite gradual decrease in accuracy for larger $t$.

2 Graph-based Semi-Supervised Learning

Graph representations, in which samples are vertices and weighted edges express affinity relationships between samples, are crucial in various computer vision tasks. Classical graph construction methods separately calculate the outgoing edges for each sample. This local strategy makes the graph vulnerable to contaminated data or outliers. Recent work in computer vision has illustrated the utility of global graph construction strategies using graph Laplacian or matrix low-rank based regularizers. L1 regularization has also been effectively used to encourage sparse graph construction . Building upon the success of global construction methods and noting the connection between subspace segmentation and graph construction as described in Section 2.1, we present a novel application of the low-rank representation methodology, relying on our DFC-LRR algorithm to scalably yield a sparse, low-rank graph (SLR-graph). We present a variety of results on large-scale semi-supervised learning visual classification tasks and provide a detailed comparison with leading baseline algorithms.

We adopt the following three large-scale benchmarks:

Columbia Consumer Video (CCV) Content Detectionhttp://www.ee.columbia.edu/ln/dvmm/CCV/: Compiled to stimulate research on recognizing highly-diverse visual content in unconstrained videos, this dataset consists of $9317$ YouTube videos over $20$ semantic categories (e.g., baseball, beach, music performance). Three popular audio/visual features (5000-D SIFT, 5000-D STIP, and 4000-D MFCC) are extracted.

MED12 Multimedia Event Detection: The MED12 video corpus consists of $\mathtt{\sim}150$K multimedia videos, with an average duration of $2$ minutes, and is used for detecting 20 specific semantic events. For each event, $130$ to $367$ videos are provided as positive examples, and the remainder of the videos are “null” videos that do not correspond to any event. In this work, we keep all positive examples and sample $10$K null videos, resulting in a dataset of $13,876$ videos. We extract six features from each video, first at sampled frames and then accumulated to obtain video-level representations. The features are either visual (1000-D sparse-SIFT, 1000-D dense-SIFT, 1500-D color-SIFT, 5000-D STIP), audio (2000-D MFCC), or semantic features (2659-D CLASSEME ).

NUS-WIDE-Lite Image Tagging: NUS-WIDE is among the largest available image tagging benchmarks, consisting of over $269$K crawled images from Flickr that are associated with over $5$K user-provided tags. Ground-truth images are manually provided for $81$ selected concept tags. We generate a lite version by sampling $20$K images. For each image, 128-D wavelet texture, 225-D block-wise LAB-based color moments and 500-D bag of visual words are extracted, normalized and finally concatenated to form a single feature representation for the image.

2.2 Graph Construction Algorithms

The three graph construction schemes we evaluate are described below. Note that we exclude other baselines (e.g., NNLRS , LLE graph , L1-graph ) due to either scalability concerns or because prior work has already demonstrated inferior performance relative to the SPG algorithm defined below .

$k$NN-graph: We construct a nearest neighbor graph by connecting (via undirected edges) each vertex to its $k$ nearest neighbors in terms of $l_{2}$ distance in the specified feature space. Exponential weights are associated with edges, i.e., w_{ij}=\operatorname{exp}\mathopen{}\mathclose{{}\left(-d_{ij}^{2}/\sigma^{2}}\right), where $d_{ij}$ is the distance between $x_{i}$ and $x_{j}$ and $\sigma$ is an empirically-tuned parameter .

SPG: Cheng et al. proposed a noise-resistant L1-graph which encourages sparse vertex connectedness, motivated by the work of sparse representation . Subsequent work, entitled sparse probability graph (SPG) enforced positive graph weights. Following the approach of , we implemented a variant of SPG by solving the following optimization problem for each sample:

where $\mathbf{x}$ is a feature representation of a sample and $\mathbf{D}_{x}$ is the basis matrix for ${\mathbf{x}}$ constructed from its $n_{k}$ nearest neighbors. We use an open-source toolhttp://sparselab.stanford.edu to solve this non-negative Lasso problem.

2.3 Experimental Design

For each benchmarking dataset, we first construct graphs by treating sample images/videos as vertices and using the three algorithms outlined in Section 4.2.2 to create (sparse) weighted edges between vertices. For fair comparison, we use the same parameter settings, namely $\alpha=0.05$ and $n_{k}=500$ for both SPG and SLR-graph. Moreover, we set $k=40$ for $k$NN-graph after tuning over the range $k=10$ through $k=60$.

We then use a given graph structure to perform semi-supervised label propagation using an efficient label propagation algorithm that enjoys a closed-form solution and often achieves the state-of-the-art performance. We perform a separate label propagation for each category in our benchmark, i.e., we run a series of $20$ binary classification label propagation experiments for CCV/MED12 and $81$ experiments for NUS-WIDE-Lite. For each category, we randomly select half of the samples as training points (and use their ground truth labels for label propagation) and use the remaining half as a test set. We repeat this process $20$ times for each category with different random splits. Finally, we compute Mean Average Precision (mAP) based on the results on the test sets across all runs of label propagation.

2.4 Experimental Results

We first performed experiments using the CCV benchmark, the smallest of our datasets, to explore the tradeoff between computation and accuracy when using DFC-LRR as part of our proposed SLR-graph. Figure 4(a) presents the time required to run SLR-graph with LRR versus DFC-LRR with three different numbers of subproblems ($t=5,10,15$), while Figure 4(b) presents the corresponding accuracy results. The figures show that DFC-LRR performs comparably to LRR for smaller values of $t$, and performance gradually degrades for larger $t$. Moreover, DFC-LRR is up to two orders of magnitude faster and achieves superlinear speedups relative to LRR.We restricted the maximum number of internal LRR iterations to $500$ to ensure that LRR ran to completion in less than two days. Given the scalability issues of LRR on this modest-sized dataset, along with the comparable accuracy of DFC-LRR, we ran SLR-graph exclusively with DFC-LRR ($t=10$) for our two larger datasets.

Table 1 summarizes the results of our semi-supervised learning experiments using the three graph construction techniques defined in Section 4.2.2. The results show that our proposed SLR-graph approach leads to significant performance gains in terms of mAP across all benchmarking datasets for the vast majority of features. These results demonstrate the benefit of enforcing both low-rankedness and sparsity during graph construction. Moreover, conventional low-rank oriented algorithms, e.g., would be computationally infeasible on our benchmarking datasets, thus highlighting the utility of employing DFC’s divide-and-conquer approach to generate a scalable algorithm.

Conclusion

Our primary goal in this work was to introduce a provably accurate algorithm suitable for large-scale low-rank subspace segmentation. While some contemporaneous work also aims at scalable subspace segmentation, this method offers no guarantee of correctness. In contrast, DFC-LRR provably preserves the theoretical recovery guarantees of the LRR program. Moreover, our divide-and-conquer approach achieves empirical accuracy comparable to state-of-the-art methods while obtaining linear to superlinear computational gains, both on standard subspace segmentation tasks and on novel applications to semi-supervised learning. DFC-LRR also lays the groundwork for scaling up LRR derivatives known to offer improved performance, e.g., LatLRR in the setting of standard subspace segmentation and NNLRS in the graph-based semi-supervised learning setting. The same techniques may prove useful in developing scalable approximations to other convex formulations for subspace segmentation, e.g., .

References

Appendix A Proof of Theorem 3

Our proof of Thm. 3 rests upon three key results: a new deterministic recovery guarantee for LRR-type problems that generalizes the guarantee of , a probabilistic estimation guarantee for column projection established in , and a probabilistic guarantee of showing that a uniformly chosen submatrix of a $(\mu,r)$-coherent matrix is nearly $(\mu,r)$-coherent. These results are presented in Secs. A.1, A.2, and A.3 respectively. The proof of Thm. 3 follows in Sec. A.4.

In what follows, the unadorned norm ${\|{\cdot}\|}$ represents the spectral norm of a matrix. We will also make use of a technical condition, introduced by Liu et al. to ensure that a corrupted data matrix is well-behaved when used as a dictionary:

A matrix ${\mathbf{M}}={\mathbf{L}}_{0}+{\mathbf{S}}_{0}$ is $\beta$-RWD if

A larger value of $\beta$ corresponds to improved recovery properties.

Thm. 1 of analyzes LRR recovery under the constraint $\mathbf{O}={\mathbf{D}}{\mathbf{Z}}+{\mathbf{S}}$ when the observation matrix $\mathbf{O}$ and the dictionary ${\mathbf{D}}$ are both equal to the input matrix ${\mathbf{M}}$. Our next theorem provides a comparable analysis when the observation matrix is a column submatrix of the dictionary.

and let $(\hat{\mathbf{Z}},\hat{\mathbf{S}})$ be a solution to the problem

with $\lambda=3/(7{\|{{\mathbf{M}}}\|}\sqrt{\gamma^{*}l})$. If $\gamma\leq\gamma^{*}$, then the column space of $\hat{\mathbf{Z}}$ equals the row space of ${\mathbf{L}}_{0}$.

The proof of Thm. 5 can be found in Sec. B.

A.2 Analysis of Column Projection

The following lemma, due to , shows that, with high probability, column projection exactly recovers a $(\mu,r)$-coherent matrix by sampling a number of columns proportional to $\mu r\log n$.

exactly with probability at least $1-\delta$.

A.3 Conservation of Incoherence

The following lemma of shows that, with high probability, ${\mathbf{L}}_{0,i}$ captures the full rank of ${\mathbf{L}}_{0}$ and has coherence not much larger than $\mu$.

A.4 Proof of DFC-LRR Guarantee

Recall that, under Alg. 1, the input matrix ${\mathbf{M}}$ has been partitioned into column submatrices $\{{\mathbf{C}}_{1},\dots,{\mathbf{C}}_{t}\}$. Let $\{{\mathbf{C}}_{0,1},\dots,{\mathbf{C}}_{0,t}\}$ and $\{{\mathbf{S}}_{0,1},\dots,{\mathbf{S}}_{0,t}\}$ be the corresponding partitions of ${\mathbf{L}}_{0}$ and ${\mathbf{S}}_{0}$, let $s_{i}\triangleq\gamma_{i}l$ be the size of the column support of ${\mathbf{S}}_{0,i}$ for each index $i$, and let $(\hat{\mathbf{Z}}_{i},\hat{\mathbf{S}}_{i})$ be a solution to the $i$th DFC-LRR subproblem.

For each index $i$, we further define $A_{i}$ as the event that ${\mathbf{C}}_{0,i}$ is $(4\mu/(1-\gamma_{i}),r)$-coherent, $B_{i}$ as the event that $s_{i}\leq\gamma^{*}l$, and $G({\mathbf{Z}})$ as the event that the column space of the matrix ${\mathbf{Z}}$ is equal to the row space of ${\mathbf{L}}_{0}$. Under our choice of $\gamma^{*}$, Thm. 5 implies that $G(\hat{\mathbf{Z}}_{i})$ holds when $A_{i}$ and $B_{i}$ are both realized. Hence, when $A_{i}$ and $B_{i}$ hold for all indices $i$, the column space of $\hat{\mathbf{Z}}=[\hat{\mathbf{Z}}_{1},\dots,\hat{\mathbf{Z}}_{t}]$ precisely equals the row space of ${\mathbf{L}}_{0}$, and the median rank of $\{\hat{\mathbf{Z}}_{1},\dots,\hat{\mathbf{Z}}_{t}\}$ equals $r$.

shows that, given $A_{i}$ and $B_{i}$ for all indices $i$, ${\hat{{\mathbf{Z}}}^{proj}}$ equals $\hat{\mathbf{Z}}$ with probability at least $1-\delta/4$. To establish $G({\hat{{\mathbf{Z}}}^{rp}})$ with probability at least $1-\delta$, it therefore remains to show that

by our assumption that $l\geq cr\mu\log^{2}(4n/\delta)/(\gamma^{*}-\gamma)^{2}\geq\log(4t/\delta)/[2(\gamma^{*}-\gamma)^{2}]$.

each submatrix ${\mathbf{C}}_{0,i}$ is $(2\mu/(1-\gamma),r)$-coherent with probability at least $1-\delta/(4n)\geq 1-\delta/(4t)$. A second application of Hoeffding’s inequality for the hypergeometric further implies that

since $l\geq cr\mu\log(4n/\delta)/(\gamma^{*}-\gamma)^{2}\geq\log(4t/\delta)/[2(1-\gamma)^{2}]$. Hence, {\mathbf{P}}\mathopen{}\mathclose{{}\left({A_{i}^{c}}}\right)\leq\delta/(2t).

Appendix B Proof of Theorem 5

Our proof of Thm. 5 will parallel Thm. 1 of . We begin by introducing two oracle constraints that would guarantee the desired outcome if satisfied.

Under the assumptions of Thm. 5, suppose that ${\mathbf{C}}={\mathbf{M}}{\mathbf{Z}}+{\mathbf{S}}$ for some matrices $({\mathbf{Z}},{\mathbf{S}})$. If $({\mathbf{Z}},{\mathbf{S}})$ additionally satisfy the oracle constraints

then the column space of ${\mathbf{Z}}$ equals the row space of ${\mathbf{L}}_{0}$.

B.2 Conditions for Optimality

To this end, we derive sufficient conditions for solving Eq. 4 and moreover show that if any solution to Eq. 4 satisfies the oracle constraints of Eq. 8, then all solutions do.

Under the assumptions of Thm. 5, suppose that ${\mathbf{C}}={\mathbf{M}}{\mathbf{Z}}+{\mathbf{S}}$ for some matrices $({\mathbf{Z}},{\mathbf{S}})$. If there exists a matrix ${\mathbf{Q}}$ satisfying

${\mathcal{P}}_{T({\mathbf{Z}})}({\mathbf{M}}^{\top}{\mathbf{Q}})={\mathbf{U}}_{Z}{\mathbf{V}}_{Z}^{\top}$

${\|{{\mathcal{P}}_{T({\mathbf{Z}})^{\bot}}({\mathbf{M}}^{\top}{\mathbf{Q}})}\|}<1$

${\mathcal{P}}_{\mathcal{I}_{0}}({\mathbf{Q}})=\lambda\mathcal{B}({\mathbf{S}})$

${\|{{\mathcal{P}}_{\mathcal{I}_{0}^{c}}({\mathbf{Q}})}\|}_{2,\infty}<\lambda.$

then $({\mathbf{Z}},{\mathbf{S}})$ is a solution to Eq. 4. If, in addition, ${\mathcal{P}}_{\mathcal{I}_{0}}({\mathbf{Z}}^{+}{\mathbf{Z}})=\mathbf{0}$, and $({\mathbf{Z}},{\mathbf{S}})$ satisfy the oracle constraints of Eq. 8, then all solutions to Eq. 4 satisfy the oracle constraints of Eq. 8.

Proof The proof of this theorem is identical to that of [18, Thm. 3] which establishes the same result when the observation ${\mathbf{C}}$ is replaced by ${\mathbf{M}}$. ∎ It remains to construct a feasible pair $({\mathbf{Z}},{\mathbf{S}})$ satisfying the oracle constraints and ${\mathcal{P}}_{\mathcal{I}_{0}}({\mathbf{Z}}^{+}{\mathbf{Z}})=\mathbf{0}$ and a dual certificate ${\mathbf{Q}}$ satisfying the conditions of Thm. 9.

B.3 Constructing a Dual Certificate

To this end, we consider the oracle problem:

Let ${\mathbf{Y}}$ be the binary matrix that selects the columns of ${\mathbf{C}}$ from ${\mathbf{M}}$. Then $({\mathbf{P}}_{L_{0}^{\top}}{\mathbf{Y}},{\mathbf{S}}_{0,i})$ is feasible for this problem, and hence an optimal solution $({\mathbf{Z}}^{*},{\mathbf{S}}^{*})$ must exist. By explicitly constructing a dual certificate ${\mathbf{Q}}$, we will show that $({\mathbf{Z}}^{*},{\mathbf{S}}^{*})$ also solves the LRR subproblem of Eq. 4.

We will need a variety of lemmas paralleling those developed in . Let

Let $\hat{\mathbf{H}}=\mathcal{B}({\mathbf{S}}^{*})$. Then

Proof The proof is identical to that of Lem. 9 of . ∎

$\psi\leq\lambda^{2}{\|{{\mathbf{M}}}\|}^{2}\gamma l$.

Proof The proof is identical to that of Lem. 10 of , save for the size of $\mathcal{I}_{0}$, which is now bounded by $\gamma l$. ∎ Note that under the assumption $\lambda\leq 3/(7{\|{{\mathbf{M}}}\|}\sqrt{\gamma l})$, we have $\psi\leq 1/4$.

If $\psi<1$, then ${\mathcal{P}}_{\mathcal{I}_{0}}(({\mathbf{Z}}^{*})^{+}{\mathbf{Z}}^{*})={\mathcal{P}}_{\mathcal{I}_{0}}({\mathbf{P}}_{\bar{V}})=\mathbf{0}$.

Lem. 12 of is unchanged in our setting. The next lemma parallels Lem. 13 of .

${\|{{\mathcal{P}}_{\mathcal{I}_{0}^{c}}(\bar{\mathbf{V}}^{\top})}\|}_{2,\infty}\leq\sqrt{\frac{\mu r}{(1-\gamma)l}}$

and therefore that ${\mathcal{P}}_{\mathcal{I}_{0}^{c}}({\mathbf{V}}_{Z^{*}}^{\top})$ is of full row rank. The remainder of the proof is identical to that of Lem. 13 of , save for the coherence factor of $(1-\gamma)l$ in place of $(1-\gamma)n$. ∎

where the first relation follows from Lem. 11. Our final theorem parallels Thm. 4 of .

then ${\mathbf{Q}}$ satisfies the conditions in Thm. 9.

Proof The proof of property $\mathbf{S3}$ requires a small modification. Thm. 4 of establishes that ${\mathcal{P}}_{\mathcal{I}_{0}}({\mathbf{Q}})=\lambda{\mathbf{P}}_{M}\hat{\mathbf{H}}$. To conclude that ${\mathcal{P}}_{\mathcal{I}_{0}}({\mathbf{Q}})=\lambda\hat{\mathbf{H}}$, we note that ${\mathbf{S}}_{i}^{*}={\mathbf{C}}-{\mathbf{M}}{\mathbf{Z}}^{*}$ and that the column space of ${\mathbf{C}}$ contains the column space of ${\mathbf{M}}$ by assumption. Hence, ${\mathbf{P}}_{M}{\mathbf{S}}_{i}^{*}={\mathbf{S}}_{i}^{*}$ and therefore ${\mathcal{P}}_{\mathcal{I}_{0}}({\mathbf{Q}})=\lambda{\mathbf{P}}_{M}\hat{\mathbf{H}}=\lambda\hat{\mathbf{H}}$.

The proofs of properties $\mathbf{S4}$ and $\mathbf{S5}$ are unchanged except for the dimensionality factor which changes from $n$ to $l$. ∎

Finally, Lem. 14 of guarantees that the preconditions of Thm. 15 are met under our assumptions on $\lambda,\gamma^{*},$ and $\gamma$.