Robust Recovery of Subspace Structures by Low-Rank Representation

Guangcan Liu; Zhouchen Lin; Shuicheng Yan; Ju Sun; Yong Yu; Yi Ma

Source-linked AI summary

Robust Recovery of Subspace Structures by Low-Rank Representation

Guangcan Liu, Zhouchen Lin, Shuicheng Yan, Ju Sun, Yong Yu, Yi Ma

arXiv:1010.2955v6Oct 14, 2010cs.ITcs.CVcs.LG

TL;DR

Subspace clustering must simultaneously segment approximately subspace-drawn data and correct errors. The paper proposes Low-Rank Representation, proving recovery of subspace structure and robust segmentation under clean, outlier-contaminated, and arbitrarily corrupted data.

Problem
Subspace segmentation must cluster approximately subspace-drawn samples while correcting errors, a central challenge in applications including vision, image processing, and system identification.
Method
Low-Rank Representation seeks the lowest-rank sample representation and supports affinity-based subspace-number estimation and outlier detection.
Results
LRR outperforms PCA and RPCA for subspace segmentation and outlier detection on the Yale-Caltech experiments.
Takeaways & Limitations
LRR provides a framework for recovering subspace structures from corrupted data while simultaneously segmenting samples and correcting errors.
Takeaways & Limitations
The theoretical guarantees require conditions that are not ensured by choosing A = X alone, which may not ensure V0 lies in the required span.

Abstract

from arXiv · show

In this work we address the subspace recovery problem. Given a set of data samples (vectors) approximately drawn from a union of multiple subspaces, our goal is to segment the samples into their respective subspaces and correct the possible errors as well. To this end, we propose a novel method termed Low-Rank Representation (LRR), which seeks the lowest-rank representation among all the candidates that can represent the data samples as linear combinations of the bases in a given dictionary. It is shown that LRR well solves the subspace recovery problem: when the data is clean, we prove that LRR exactly captures the true subspace structures; for the data contaminated by outliers, we prove that under certain conditions LRR can exactly recover the row space of the original data and detect the outlier as well; for the data corrupted by arbitrary errors, LRR can also approximately recover the row space with theoretical guarantees. Since the subspace membership is provably determined by the row space, these further imply that LRR can perform robust subspace segmentation and error correction, in an efficient way.

I. INTRODUCTION … A. Summary of Main Notations

The paper formulates robust subspace clustering as simultaneous error correction and segmentation for samples near a union of subspaces. It introduces Low-Rank Representation (LRR), an autonomous convex method with theoretical recovery guarantees, and situates it among existing segmentation approaches while defining notation for the analysis.

I. INTRODUCTION: Subspace clustering seeks to correct errors and assign approximately sampled data to their respective linear subspaces simultaneously.The problem concerns data drawn approximately from a union of linear subspaces.
I. INTRODUCTION: The paper focuses on sample-specific corruptions and outliers, while giving milder attention to noise and random corruptions.The introduction distinguishes errors such as noise, missed entries, outliers, and corruptions.
I. INTRODUCTION: LRR finds the lowest-rank joint representation of data samples as linear combinations of dictionary bases.Its computational procedure uses nuclear-norm regularization in a convex optimization problem solvable in polynomial time.
I. INTRODUCTION: LRR extends corrupted-data recovery from a single subspace to multiple subspaces without requiring extra clean data.The method is described as autonomous and has been applied to motion segmentation, image segmentation, saliency detection, and face recognition.
II. RELATED WORK: Existing subspace segmentation methods fall into mixture-of-Gaussian, factorization, algebraic, and spectral categories.Spectral approaches learn an affinity matrix and then apply methods such as Normalized Cuts; LRR is included among these methods.
II. RELATED WORK: Factorization methods add regularization for noise robustness but typically produce non-convex optimization problems requiring heuristic algorithms.The cited heuristics include alternating minimization and EM-style procedures.
II. RELATED WORK: GPCA provides algebraic guarantees under conditions but is noise-sensitive and computationally costly, while RAS is practical mainly for low-dimensional data with few subspaces.RAS addresses GPCA’s robustness issue but retains substantial polynomial-fitting difficulty.
A. Summary of Main Notations: The notation section defines matrix indexing and concatenation, vector and matrix norms, supports and projections, spans, and terminology such as row space and affinity degree.Matrices use capital symbols; entries, rows, and columns are indexed with subscripts, and the nuclear norm denotes the sum of singular values.

B. Relations Between Segmentation and Row Space … A. Low-Rank Representation

The paper frames subspace clustering as recovery of the clean data’s row space or true Shape Interaction Matrix, then introduces Low-Rank Representation (LRR) as a dictionary-based rank-minimization model for corrupted observations. LRR generalizes Robust PCA to data drawn from multiple subspaces by preserving their individual structure.

B. Relations Between Segmentation and Row Space: For clean data from independent subspaces, the samples’ subspace membership is determined by the row space of X0.The associated matrix V0V0^T is block-diagonal, with nonzero entries only for sample pairs from the same subspace.
B. Relations Between Segmentation and Row Space: Standard SVD-based segmentation can become inaccurate under outliers and corruptions because VX may differ substantially from V0.The paper shows that LRR can recover V0V0^T even when X is contaminated by outliers.
C. Problem Statement: The clustering objective is to recover the row space of X0, equivalently the true SIM V0V0^T, because this supports segmentation accuracy and error correction.The paper considers clean data, gross sample corruptions, and combined gross corruptions with small Gaussian noise as increasingly practical cases.
C. Problem Statement: The analysis focuses on recovering V0V0^T rather than requiring the subspaces to be independent or explicitly pursuing a block-diagonal matrix.When subspaces have nonempty intersections, V0V0^T need not be strictly block-diagonal, while pairwise disjoint non-independent subspaces can still yield near block-diagonal structure.
IV. LOW-RANK REPRESENTATION FOR MATRIX RECOVERY: The matrix-recovery section abstracts LRR for recovering a matrix from corrupted observations and presents its basic theorems and optimization algorithms.Specific methods and theories for subspace clustering are deferred to Section V.
A. Low-Rank Representation: A direct recovery formulation minimizes rank(D) plus a regularization penalty on E subject to X = D + E.The regularizer can model Gaussian noise, random corruptions, or sample-specific corruptions and outliers through different norms.
A. Low-Rank Representation: Robust PCA uses this formulation for a single low-rank subspace, but it may inaccurately recover data from a union of subspaces because it treats them as one combined subspace.The combined subspace is described as S = Pk i=1Si, without adequately modeling the individual subspaces.
A. Low-Rank Representation: LRR instead minimizes rank(Z) with regularized E subject to X = AZ + E, where A is a dictionary that linearly spans the data space.The optimal representation Z* is the lowest-rank representation of X relative to A; AZ* recovers a low-rank approximation, and A = I reduces LRR to the direct formulation.

B. Analysis on the LRR Problem … C. Recovering Low-Rank Matrices by Convex Optimization

The analysis replaces rank minimization with nuclear-norm convex optimization, whose unique minimizer preserves minimal-rank structure and supports subspace segmentation. The convex recovery formulation models corruptions through appropriate norms and is solved by an inexact ALM procedure, with convergence limitations for three or more blocks.

B. Analysis on the LRR Problem: The nuclear norm replaces the nonconvex rank function, yielding a convex problem whose solution is also a solution to the original rank-minimization problem.This surrogate is introduced because rank minimization is difficult and the original solution may be nonunique.
1) Uniqueness of the Minimizer:: The minimizer of the nuclear-norm problem is uniquely defined in closed form despite the nuclear norm not being strongly convex.The theorem assumes A ≠ 0 and that X = AZ has feasible solutions; A† denotes the pseudoinverse of A.
1) Uniqueness of the Minimizer:: The minimizer Z∗ satisfies rank(Z∗) = rank(X) and is also a minimal-rank solution to the original rank-minimization problem.Thus, the nuclear-norm formulation is a valid surrogate under the stated feasibility assumptions.
2) Block-Diagonal Property of the Minimizer:: For independent subspaces with sufficiently sampled spanning dictionaries, the minimizer is block-diagonal after grouping samples by true subspace membership.The stated sampling condition is rank(A_i) = r_i for each subspace.
2) Block-Diagonal Property of the Minimizer:: Each diagonal block satisfies rank(Z∗_i) = rank(X_i), guaranteeing high within-class homogeneity and enabling subspace membership recovery.The block-diagonal property does not require the data samples to be initially grouped by subspace.
C. Recovering Low-Rank Matrices by Convex Optimization: Low-rank recovery solves a convex model with nuclear-norm regularization and an ℓ2,1 error term for sample-specific corruptions and outliers.The recovered low-rank data can be obtained as AZ∗ or X − E∗; small Gaussian and random corruptions instead motivate ∥E∥2_F and ∥E∥1, respectively.
C. Recovering Low-Rank Matrices by Convex Optimization: The convex recovery problem is implemented with an inexact Augmented Lagrange Multiplier method that alternately updates J, Z, E, and the multipliers.The J update uses Singular Value Thresholding, while the E update has a closed-form columnwise solution.
C. Recovering Low-Rank Matrices by Convex Optimization: Convergence is generally established for exact ALM and studied for inexact ALM with at most two blocks, but remains difficult to ensure with three or more blocks.The formulation uses three blocks, including Z, J, and E.

1) Convergence Properties:

Although Algorithm 1 and its objective are nonsmooth, convergence is guaranteed under sufficient conditions on the dictionary and iteration optimality gaps. The analysis also adopts an upper bound on μ as required by traditional alternating-direction theory, while noting this may not be necessary for some problems.

Convergence conditions: Algorithm 1’s nonsmooth objective makes theoretical convergence difficult to prove, despite the available sufficient guarantees.The convergence discussion therefore relies on conditions from prior theoretical results.
Convergence conditions: Two sufficient conditions guarantee Algorithm 1 convergence: A has full column rank, and the optimality gap decreases monotonically each iteration.These conditions may be sufficient but are not necessarily required.
Convergence conditions: The full-column-rank condition is readily satisfied by converting problem (7) into an equivalent problem where it always holds.The paper states that this conversion is shown in the next subsection.
Parameter convention: The algorithm upper-bounds μ to satisfy traditional alternating-direction convergence theory, although this bound may be unnecessary for particular problems such as RPCA.The RPCA example is attributed to prior analysis.

2) Computational Complexity: … B. Robustness to Outliers and Sample-Specific Corruptions

LRR reduces computation by restricting representations to the row space of the dictionary, while recovering clean-data row spaces exactly and identifying outliers through the learned representation and error matrix.

2) Computational Complexity:: The optimal representation Z* lies in the subspace spanned by the rows of A and can be factorized as Z* = P*Z̃*.P* is computed in advance by orthogonalizing the columns of A^T, yielding an equivalent lower-dimensional optimization problem.
2) Computational Complexity:: Because Z̃* has at most r_A rows, LRR becomes scalable for large n when a low-rank dictionary A is available.With A = X and d ≤ n, the complexity is at most O(d^2n + d^3).
2) Computational Complexity:: Algorithm 1 uses an iteration count n_s controlled by ρ: larger ρ reduces iterations but risks losing optimality.The experiments set ρ = 1.1, producing typically 50–300 iterations.
V. SUBSPACE CLUSTERING BY LRR: The paper applies LRR to recover the original row space from corrupted observations using both theoretical and experimental analyses.This establishes the scope of the subsequent clean-data and corruption-recovery results.
A. Exactness to Clean Data: For clean data, the unique minimizer is Z* = VV^T, which exactly recovers the row space identified by V_0V_0^T.The result assumes X = X_0 and E_0 = 0, with X having skinny SVD UΣV^T.
A. Exactness to Clean Data: Unlike PCA, which is fragile to outliers, LRR is stated to exactly recover the row space of X_0 from data contaminated by outliers.The passage presents this as the theoretical result developed in the following subsection.
B. Robustness to Outliers and Sample-Specific Corruptions: When a fraction of samples lies away from the underlying subspaces, E_0 has sparse column support, motivating the ℓ2,1 norm and the choice A = X.This formulation leads to a convex optimization problem for sample-specific corruptions.
WITH THE COLUMN SPACE OF Z* EXACTLY RECOVERING THE ROW SPACE: The column space of Z* exactly recovers the row space of X_0, while the column supports of E* exactly identify the outlier indices.The formulation uses X itself as the dictionary despite possible errors in the data matrix.

1) Exactness to Outliers: · 2) Robustness to Sample-Specific Corruptions:

LRR exactly recovers the row space and identifies outliers when their fraction is below a sufficient threshold, while remaining empirically effective for sample-specific corruptions. Its recovered column space, rather than coefficient matrix, determines the subspace structure, and heavily corrupted authentic samples may be treated as outliers.

1) Exactness to Outliers:: LRR exactly recovers the row space of the clean data and identifies the indices of outliers when the outlier fraction γ is at most a threshold γ∗.The theorem states existence of γ∗ > 0 under which any minimizer succeeds.
1) Exactness to Outliers:: Any minimizer remains effective for subspace clustering despite the objective being non-strongly convex and potentially having multiple minimizers.The recovered structure comes from the column space of Z∗, not Z∗ itself.
1) Exactness to Outliers:: The success threshold γ∗ is larger when the extrinsic rank r0 is lower and depends on data properties including incoherence.Performance is measured by γ∗, with larger values indicating better performance.
1) Exactness to Outliers:: The theorem’s parameter choice λ = 3/(7∥X∥√(γ∗n)) requires γ ≤ γ∗ as a sufficient, not necessary, condition for success.When γ > γ∗, other λ values may perform better in practice.
2) Robustness to Sample-Specific Corruptions:: For sample-specific corruptions, LRR remains applicable because both these corruptions and outliers produce errors with sparse column supports, although the theorem’s setting is no longer valid.The empirical conclusion I∗ = I0 still holds.
2) Robustness to Sample-Specific Corruptions:: LRR’s recovery error is 0.17, compared with 0.66 for PCA and 0.23 for RPCA using the best parameters.The experiment includes noise, outliers, and sample-specific corruptions.
2) Robustness to Sample-Specific Corruptions:: Authentic samples corrupted heavily enough to become independent of the underlying subspaces are treated as outliers by LRR.The paper presents this as a reasonable manipulation for samples whose corruption changes their effective identity.

C. Robustness in the Presence of Noise, Outliers and Sample-Specific Corruptions

LRR extends to noisy, outlier-contaminated, and sample-specifically corrupted data by using an ℓ2,1 relaxation that accommodates approximately sparse corruption supports. Because exact row-space recovery is generally impossible when all observations are contaminated, the method targets near recovery, with promising empirical results and practical segmentation procedures.

Robustness under noise: The ℓ2,1 norm in formulation (9) handles signals whose column supports are only approximately sparse under noise.Noise makes the column supports of E0 not strictly sparse, but the relaxed norm remains applicable.
Robustness under noise: Exact recovery of the clean row space is unlikely when all observations may be contaminated, so the analysis targets near recovery.The near-recovery objective follows from the possibility that every observation contains contamination.
Theoretical guarantee: Theorem 5.3 provides an error bound for any minimizer of problem (9) when λ > 0.The theorem assumes a d × n data matrix X and clean-data rank r0; the supplied passage introduces the bound but does not include its formula.
Subspace segmentation: Subspace segmentation obtains Z∗ from problem (9), builds an affinity matrix W from its skinny SVD, and applies NCut to form k clusters.Algorithm 2 specifies the sequence: solve for Z∗, compute Z∗ = U∗Σ∗(V∗)T, construct W using (12), and segment the samples.
Empirical performance: LRR produces quite promising results in the presence of noise, outliers, and sample-specific corruptions.Figure 6 reports the method’s performance across these three corruption settings.

D. Algorithms for Subspace Segmentation, Model Estimation and Outlier Detection … 2) Yale-Caltech:

The paper describes an LRR pipeline that segments data, estimates the number of subspaces, and detects outliers using structures derived from the learned representation. Experiments then examine these capabilities on motion and face-image datasets, including a Yale-Caltech combination.

D. Algorithms for Subspace Segmentation, Model Estimation and Outlier Detection: LRR uses U∗(U∗)T, derived from the learned representation, to identify the column space of Z∗ for subspace segmentation.The skinny SVD of Z∗ provides the factors used to construct the segmentation affinity matrix.
1) Segmentation with Given Subspace Number:: The affinity matrix W is processed with spectral clustering, such as Normalized Cuts, to partition samples into a specified number k of clusters.For corrupted data, each column of U∗ is weighted by the singular values in Σ∗; this has no effect when the data is clean because Σ∗ = I.
2) Estimating the Subspace Number k:: The number of subspaces can be estimated from the affinity matrix’s block-diagonal structure by analyzing singular values of its normalized Laplacian.With a strictly block-diagonal W, k equals the number of zero singular values; with a near block-diagonal W, singular values below a threshold are counted using soft thresholding.
3) Outlier Detection:: Outliers can be detected from the minimizer E∗ by identifying its nonzero columns or thresholding approximately sparse column supports.Under the stated assumptions, a data vector is judged an outlier according to whether its corresponding column in E∗ passes the thresholding criterion.
3) Outlier Detection:: Outliers can also be removed by discarding samples whose affinity degrees are zero or close to zero.This affinity-degree strategy is commonly used in spectral-type methods and is described as essentially equivalent in principle to characterizing outliers through E∗.
VI. EXPERIMENTS: The experiments focus on analyzing LRR for subspace segmentation and outlier detection, following its reported use in several applications.Those applications include motion segmentation, image segmentation, face recognition, and saliency detection.
1) Hopkins155:: Hopkins155 contains 156 video sequences represented as datasets with varying subspace numbers, data dimensions, and sample counts.For each sequence, the error level is estimated using a rank-r approximation, with r = 4k because each motion subspace has rank at most 4.
2) Yale-Caltech:: The Yale-Caltech dataset combines Extended Yale Database B and Caltech101 to test LRR under outliers and corruptions.After excluding extreme lighting conditions, Extended Yale Database B contributes 1204 authentic samples approximately drawn from 38 low-rank subspaces.

B. Baselines and Evaluation Metrics … 2) Segmentation Performance:

The paper evaluates LRR against PCA, RPCA, SR, and prior segmentation methods using segmentation error and outlier-detection AUC. On Hopkins155, LRR achieves strong segmentation performance, remains effective across parameter settings, and has comparable efficiency to PCA and RPCA.

B. Baselines and Evaluation Metrics: PCA, RPCA, and prior subspace segmentation methods serve as baselines for evaluating LRR.The study selects PCA and RPCA because of their close connections to LRR and also includes several previous segmentation methods.
1) PCA (i.e., SIM):: PCA applies rank-r SVD approximation to estimate the subspace membership matrix and uses reconstruction residuals for outlier detection.Its estimated membership matrix is derived from VrV_r^T, while residuals Er = X − UrΣrV_r^T support outlier detection.
2) RPCA:: RPCA1 models random corruptions with the ℓ1 norm, whereas RPCA2,1 detects outliers with the ℓ2,1 norm.Both methods use the same segmentation and outlier-detection procedures as PCA, but form Vr from the skinny SVD of D*.
2) RPCA:: The comparison also includes SR and eleven prior segmentation methods, including RANSAC, GPCA, LSA, ALC, SSC, SC, SCC, MSL, LLMC, LBF, and SLBF.SR uses an ℓ2,1-norm formulation with a zero-diagonal constraint and constructs affinity matrix W = |Z*| + |(Z*)^T|.
5) Evaluation Metrics:: Segmentation accuracy is measured by segmentation error, while outlier-detection quality is measured by the area under the ROC curve, or AUC.The paper refers readers to the appendix for further details on both metrics.
1) Choosing the Parameter: For Hopkins155, LRR’s segmentation error ranges from 1.69% to 2.81% for λ from 1 to 6 and from 1.69% to 1.87% for λ from 3 to 5.Choosing the best λ separately for each sequence yields an overall error rate of 0.07%, while experiments use λ = 4.
2) Segmentation Performance:: LRR outperforms PCA and RPCA on Hopkins155 because it directly targets the row space V0V_0^T that determines segmentation.The comparison also reports a 2.03% segmentation error for ℓ1-regularized E, indicating that errors in this database tend to be sample-specific.
2) Segmentation Performance:: LRR has PCA- and RPCA-comparable running-time efficiency and the same theoretical complexity as RPCA, although its optimization requires more iterations.LRR also correctly predicts the true subspace number for 121 sequences at τ = 0.08, with mean absolute error 0.25.

3) Performance of Estimating Subspace Number: … VII. CONCLUSION AND FUTURE WORK

LRR performs competitively or better than prior methods for subspace-number estimation, segmentation, and outlier detection, while jointly supporting error correction. The paper concludes that dictionary learning, parameter selection, and robustness to more complex corruptions remain important challenges.

4) Comparing to State-of-the-art Methods:: 4) Comparing to State-of-the-art Methods: A convex formulation incorporating hidden data unifies subspace segmentation and feature extraction, achieving a 0.85% error rate.The formulation is min Z,L,E ∥Z∥∗+∥L∥∗+λ∥E∥1 subject to X = XZ + LX + E.
4) Comparing to State-of-the-art Methods:: 4) Comparing to State-of-the-art Methods: Subspace segmentation remains unresolved despite several methods achieving error rates below 3% on Hopkins155.The paper identifies estimating LRR’s parameter λ and handling datasets with more noise, outliers, and corruptions as difficult problems.
D. Results on Yale-Caltech:: D. Results on Yale-Caltech: LRR outperforms PCA and RPCA in both subspace segmentation and outlier detection on the Yale-Caltech dataset.The test identifies 609 non-face outliers and segments 1204 face images into 38 clusters; images are resized to 20 × 20 pixels.
D. Results on Yale-Caltech:: D. Results on Yale-Caltech: LRR is more sensitive to λ on Yale-Caltech because the dataset contains outliers and corrupted images, unlike the lower-noise Hopkins155 dataset.The parameter study varies λ from 0.06 to 0.22.
D. Results on Yale-Caltech:: D. Results on Yale-Caltech: LRR decomposes images into a low-rank principal-feature component and a sparse error component, whose residual may contain useful information such as eyes and salient objects.The visualization uses a data matrix of size 8064 × 1813 with images resized to 96×84.
VII. CONCLUSION AND FUTURE WORK: VII. CONCLUSION AND FUTURE WORK: LRR identifies subspace structures from corrupted data by simultaneously segmenting samples and correcting errors, extending RPCA from one subspace to multiple subspaces.The paper also describes LRR as a generalization of Shape Interaction Matrix.
VII. CONCLUSION AND FUTURE WORK: VII. CONCLUSION AND FUTURE WORK: Future work includes learning dictionaries, extending proofs beyond A = X, selecting λ under varied errors, and addressing dense noise, outliers, and corruptions.Exact row-space recovery requires a dictionary condition involving V0, which choosing A = X satisfies for outliers but may not satisfy under other errors.

APPENDIX … UMV T

The appendix defines matrix, subspace, SVD, space, and affinity terminology, then proves Theorem 4.1 through nuclear-norm lemmas culminating in a unique closed-form minimizer.

1) Block-Diagonal Matrix:: A matrix is block-diagonal when row and column permutations can transform it into block-diagonal form.This is expressed by the existence of permutation matrices P1 and P2 such that P1MP2 is block-diagonal.
2) Union and Sum of Subspaces:: The appendix defines unions and directed sums of subspaces, and characterizes independence through trivial intersections with sums of the remaining subspaces.For low-rank subspaces in high-dimensional spaces, independence is described as roughly equivalent to pairwise disjointness.
4) Full SVD and Skinny SVD:: The appendix distinguishes full and skinny SVDs, retaining only positive singular values in the rank-r skinny form M = U_rΣ_rV_r^T.In the skinny SVD, U_r and V_r consist of the first r columns of the full-SVD factors.
6) Column Space and Row Space:: For a skinny SVD M = UΣV^T, U and V provide orthonormal bases for the column and row spaces, whose projections are UU^T and VV^T.The appendix also defines affinity degree as the number of samples connected to a sample through nonzero entries of a symmetric affinity matrix.
1) Proof of Theorem 4.1:: The proof of Theorem 4.1 relies on three lemmas, including nuclear-norm invariance under multiplication by matrices with orthogonal columns.The first lemma states ∥M∥_* = ∥UMV^T∥_* under the stated orthogonality conditions.
UMV T: Lemma 7.3 establishes that Z* = UMV^T is the unique minimizer of the stated nuclear-norm optimization problem.The proof shows both optimality and uniqueness, with equality forcing the additional components to vanish.
UMV T: Lemma 7.3 provides closed-form solutions for a class of nuclear-norm minimization problems and simplifies the proof of Theorem 4.1.Applying the lemma yields a unique minimizer for problem (5), further simplified to Z* = A^T U(U^TAA^TU)^−1U^TX.

2) Proof of Corollary 4.1:

The proof establishes that the constructed solution Z∗ has the same rank as X and is optimal for problem (4) because every feasible solution has rank at least rank(X).

Rank argument: rank(Z∗) = rank(X), establishing rank equality for the constructed solution.The proof explicitly derives rank(Z∗) = rank(X).
Rank argument: Every feasible solution Z to problem (5) satisfies rank(Z) ≥ rank(AZ) = rank(X).This lower bound follows from feasibility and the identity AZ = X.
Optimality: Therefore, Z∗ is also optimal for problem (4).Its rank matches the lower bound attained by every feasible solution.

3) Proof of Theorem 4.2: … 2) Receiver Operator Characteristic:

The proof constructs a block-diagonal feasible restriction of the optimizer and uses independence, nuclear-norm comparison, and uniqueness to establish block structure and rank preservation. The evaluation section then describes efficient cluster-label assignment and ROC/AUC-based outlier-detection assessment.

3) Proof of Theorem 4.2:: The lemma lowers the objective at any solution to the value of its block-diagonal restriction, yielding a simple route to Theorem 4.2.The construction forms W from the optimizer Z∗ of problem (5).
3) Proof of Theorem 4.2:: For each data vector, independence of the subspaces forces the off-block component AQ to vanish.Writing Q = Z∗−W, both [AQ]:,j and [X]:,j−[AW]:,j lie in the same subspace, while [AQ]:,j also lies in the direct sum of the others.
3) Proof of Theorem 4.2:: The block-diagonal restriction W is feasible, and nuclear-norm comparison plus uniqueness imply that Z∗ itself is block-diagonal.The proof obtains ∥Z∗∥∗≥∥W∥∗ and concludes Z∗=W.
3) Proof of Theorem 4.2:: Each diagonal block Z∗i is the unique minimizer of the corresponding nuclear-norm problem subject to Xi = AiJ.This follows from uniqueness of the global minimizer.
3) Proof of Theorem 4.2:: The diagonal-block rank equals the rank of the corresponding data block: rank(Z∗i) = rank(Xi).The equality is obtained by applying Corollary 4.1.
4) Proof of Theorem 4.3:: Problem (9) has the feasible candidate (V V T, 0), where UΣV T is the skinny SVD of X.Convexity is then used in the proof.
5) Proof of Theorem 5.3:: The proof bounds the optimizer’s nuclear-norm objective by rank(X) and further by min(d, n), while an additional term yields min(d, n) + r0.The displayed bounds include ∥Z∗∥∗+ λ∥E∗∥ ≤ rank(X) ≤ min(d, n) and ∥Z∗∥∗+ r0 ≤ min(d, n) + r0.
C. Evaluation Metrics: Segmentation evaluation assigns cluster labels by local search over label vectors; its complexity is O(k), and ROC evaluates outlier detection through thresholded true- and false-positive rates.The ROC curve plots true positives rate against false positive rate, while the area under the curve, AUC, evaluates quality.