PaperlayerView exact revision on arXiv

Source-linked AI summary

LoomSC: Scalable Deep Subspace Clustering with Projector Factorization and Exact Spectral Reduction

Nairouz Mrabah, Youssef Melki, Mohamed Bouguessa, Riadh Ksantini, Shakeeb Murtaza, Tehseen Zia

arXiv:2610.10266v1cs.CVcs.AI

TL;DR

Dense self-expression matrices and full-affinity spectral clustering constrain the scalability of subspace clustering. LoomSC jointly learns latent representations and a projector self-representation, then exactly reduces the normalized spectral problem. It reports strong benchmark results and synthetic scaling to 500,000 samples.

  • Problem

    Dense self-expression and full-affinity spectral clustering create separate sample-scale computational bottlenecks for subspace clustering.

    Source: §I · p. 1

  • Method

    LoomSC jointly learns latent features and a projector self-representation, using a nonnegative quadratic affinity and exact spectral reduction without forming the full affinity or sample Laplacian.

    Source: §V · p. 14

  • Results

    6.66 percentage points: LoomSC’s mean accuracy exceeds the highest baseline mean across five image-clustering benchmarks, and it ranks first or second in all 15 dataset–metric comparisons.

    Source: §I · p. 2

  • Takeaways & Limitations

    Compact self-expression combines strong clustering quality with scalability across representation learning and spectral assignment.

    Source: §IV · p. 8, §V · p. 14

Abstract

from arXiv · show

Dense self-expression matrices and full-affinity spectral clustering limit the scalability of subspace clustering. We introduce the Latent Orthogonal Optimization Model for Subspace Clustering (LoomSC), a framework that addresses both bottlenecks through projector factorization and exact spectral reduction. Motivated by the spectral structure of least-squares regression, LoomSC jointly learns latent features and a projector self-representation through two thin factors. Alternating Procrustes and least-squares updates preserve the sample factor's orthogonality while keeping the coefficient matrix implicit. We construct a nonnegative quadratic affinity that preserves the projector's support. An exact feature map then reduces its normalized spectral problem to an eigenproblem whose dimension depends only on the factor width. Neither the full affinity nor the sample Laplacian needs to be formed. Our analysis quantifies the projector approximation and identifies conditions for subspace preservation and within-subspace connectivity. For fixed dimensions and iteration budgets, the complete pipeline has linear time and memory complexity in the number of samples. Across five image-clustering benchmarks, LoomSC ranks first or second in all 15 dataset-metric comparisons against 9 state-of-the-art baselines. Its mean accuracy exceeds the highest baseline mean by 6.66 percentage points. Synthetic experiments scale to 500,000 samples while maintaining at least 99.8% accuracy.

I. INTRODUCTION

LoomSC targets both dense self-expression and full-affinity spectral bottlenecks while jointly adapting the representation and self-expression directions. It uses thin factors and a reduced spectral problem to retain pairwise relations without forming sample-level matrices.

I. INTRODUCTION

  • Dense coefficients require O(n^2) storage, while full-affinity spectral clustering adds a separate bottleneck that faster coefficient estimation alone cannot remove.LoomSC’s stated goal is to retain pairwise self-expression and normalized spectral clustering without dense sample-level matrices at either stage.Source: §I · pp. 1–2

A. Scalable subspace clustering:

  • Representative-based and structured-graph methods compact clustering, but supplied-feature reconstruction or fixed representatives can limit adaptation of the image representation.LoomSC instead learns the representation and latent self-expression directions together; its related-work discussion distinguishes this integration from factorization alone.Source: §I · p. 2, A. Scalable subspace clustering · p. 3

I. INTRODUCTION

  • LoomSC represents self-expression with two thin factors and orthogonality-preserving Procrustes and least-squares updates, keeping the coefficient matrix implicit.Its analysis quantifies the projector approximation to LSR and identifies conditions for subspace preservation and within-subspace connectivity.Source: §I · p. 2
  • A nonnegative quadratic affinity preserves the projector’s support, and an exact feature map reduces normalized spectral clustering to an eigenproblem sized by factor width.The reduction avoids forming the full affinity or sample Laplacian; for fixed dimensions and iteration budgets, the complete pipeline has linear time and memory complexity in n.Source: §I · p. 2
  • 6.66 percentage points: LoomSC’s mean accuracy exceeds the highest baseline mean, and it ranks first or second in all 15 dataset–metric comparisons across five image-clustering benchmarks.Synthetic experiments reach 500,000 samples while maintaining at least 99.8% accuracy throughout the tested range.Source: §I · p. 2

B. Deep subspace clustering:

Prior deep subspace-clustering methods jointly learn features and self-expression but retain sample-to-sample coefficient matrices or full-affinity spectral inference. LoomSC replaces these with a prescribed-width projector approximation and thin-factor optimization.

B. Deep subspace clustering:

  • Unlike deep self-expression methods that retain sample-to-sample matrices, LoomSC uses two thin factors with dimensions controlled by a prescribed factor width.PRO-DSC supports mini-batch training, but its full-set spectral inference still constructs pairwise coefficients and retains quadratic matrix storage.Source: B. Deep subspace clustering · p. 3

III. LOOMSC

  • The projector approaches the LSR representation as regularization becomes small relative to the positive data spectrum.The spectral motivation is that LSR directions with eigenvalues close to one can be approximated by retaining their subspace with projector weights of one.Source: A. A Projector Approximation Motivated… · p. 4

A. A Projector Approximation Motivated by LSR

  • For a fixed width m, retaining the first m eigenvectors gives the closest rank-m projector among projectors formed from the eigenvectors of X⊤X.The approximation replaces retained LSR eigenvalues with 1 and discards the remaining directions; setting m to the full rank recovers the row-space projector, but can require costly singular-subspace computation and O(nr) storage.Source: A. A Projector Approximation Motivated… · p. 4
  • LoomSC’s two-factor updates use thin matrix products and an n × m Procrustes problem, avoiding repeated recomputation of the dominant subspace as learned features evolve.The full coefficient matrix remains implicit.Source: A. A Projector Approximation Motivated… · p. 5

B. Learning a Latent Representation

LoomSC couples an auto-encoder’s reconstruction objective with a compact latent self-representation. Its two thin factors separate latent directions from sample coefficients and connect the learned model to dominant spectral directions.

B. Learning a Latent Representation

  • The auto-encoder reconstruction objective retains information about observed samples, while the projector objective imposes complementary subspace structure on the learned latent representation.For image inputs, convolutional features are flattened into the latent representation and the decoder reconstructs the input.Source: B. Learning a Latent Representation · p. 5

C. Self-Expression Through Two Thin Factors

  • The two-factor model separates latent directions in L from sample coefficients in P, enabling simple block updates using thin matrices.For a fixed latent matrix, an optimal P spans a dominant right-singular subspace when m is no larger than the latent rank; at or above that rank, the projector can contain the row space and reconstruct Z exactly.Source: C. Self-Expression Through Two Thin… · p. 5

D. Alternating Optimization

LoomSC alternates network and thin-factor updates, preserving the sample factor’s orthogonality while adapting latent features to the full dataset. Chunked gradient accumulation controls activation memory without changing the full-data objective.

D. Alternating Optimization

  • Chunked gradients are accumulated before one network update, reducing activation memory without changing the full-data objective.Afterward, the encoder recomputes Z before P and L are updated.Source: D. Alternating Optimization · p. 5
  • The sample factor update solves an orthogonal Procrustes problem using a thin product and preserves the constraint P⊤P = I_m.For fixed Z and L, the update uses the thin SVD of Z⊤L.Source: D. Alternating Optimization · p. 6
  • With Z and P fixed, L is updated from the current latent samples and coefficients, so both factors adapt using the full dataset.The update is L ← ZP.Source: D. Alternating Optimization · p. 6
  • For fixed Z, each factor update minimizes its objective block, and repeated updates produce a nonincreasing objective sequence converging to a finite limit.The outer procedure also updates network parameters and refreshes Z between factor updates.Source: D. Alternating Optimization · p. 6

E. Subspace Structure of the Learned Projector

Under stated span and factor-width conditions, the learned projector separates subspaces and can connect samples within each subspace. LoomSC then converts projector coefficients into a support-preserving nonnegative affinity and solves the normalized spectral problem through a reduced feature-space eigenproblem.

E. Subspace Structure of the Learned Projector

  • If latent samples span a direct sum, m equals its dimension, m < n, and the fixed-Z objective attains its minimum, the projector is block diagonal by subspace.Within each subspace, its nonzero off-diagonal coefficients form a connected graph when the samples cannot be partitioned into two nonempty sets with spans forming a direct sum.Source: E. Subspace Structure of the Learned… · p. 6

F. Scalable Spectral Clustering from the Learned Factors

  • Squaring projector coefficients gives nonnegative affinities while preserving their zero pattern, so subspace separations encoded by the projector remain in the graph.The affinity is also invariant to an orthogonal change of basis in P.Source: F. Scalable Spectral Clustering from… · p. 6
  • An exact feature map represents the affinity with q = m(m + 1)/2 features per sample, reducing normalized spectral clustering to a q-dimensional eigenproblem without forming the affinity or sample Laplacian.The reduced problem supplies at least k positive eigenvalues when k ≤ m; k is the embedding dimension, while q is the reduced spectral dimension.Source: F. Scalable Spectral Clustering from… · pp. 6–7
  • Retaining the eigenvalue-one modes preserves component indicators when the affinity graph has k connected components, and row normalization maps each component to a distinct embedding point.The procedure applies k-means to the normalized rows of the k-dimensional embedding.Source: F. Scalable Spectral Clustering from… · p. 7

G. Complete Algorithm and Computational Complexity

The complete algorithm combines representation learning, factor updates, and spectral assignment using compact operations. For fixed dimensions and iteration budgets, its time and memory scale linearly with the number of samples.

G. Complete Algorithm and Computational Complexity

  • The direct spectral implementation forms a q × q reduced matrix at O(nq²) cost and eigendecomposes it in O(q³), where q = m(m + 1)/2.Recovering the k-dimensional sample embedding costs O(nqk).Source: G. Complete Algorithm and… · p. 8
  • The implicit spectral implementation avoids explicitly forming G and evaluates its operator as needed, with cost depending on eigensolver iterations and basis size.This avoids storing the dense q × q matrix and is preferred when q is large.Source: G. Complete Algorithm and… · p. 8
  • The resident-data memory bound is linear in n, with additional reduced-eigensolver storage of O(q² + qk) for direct reduction or O(qs_eig + qk) for the implicit solver.Quadratic feature rows need not be stored.Source: G. Complete Algorithm and… · p. 8
  • For fixed dimensions, architecture, factor width, cluster count, and iteration budgets, LoomSC has linear time and memory complexity in n.The factor width is a chosen model parameter, so neither phase requires estimating data rank.Source: G. Complete Algorithm and… · p. 8

IV. RESULTS AND DISCUSSION

The evaluation compares LoomSC with nine baselines on five image-clustering benchmarks using ACC, NMI, and ARI. The setup uses a shared LoomSC architecture and optimization schedule across datasets, while the comparison includes methods with different representation-learning and scalability profiles.

IV. RESULTS AND DISCUSSION

  • The evaluation covers five image-clustering benchmarks: Extended YaleB, ORL, UMIST, COIL-100, and a balanced Fashion-MNIST subset.The datasets contain 2,432, 400, 575, 7,200, and 5,000 samples, respectively.Source: §IV · p. 8
  • Nine baselines span scalable non-deep methods and full-affinity references, including deep PRO-DSC, whose published spectral inference still processes pairwise coefficients over the clustering set.LoomSC combines deep representation learning with factorized self-expression and spectral assignment; its complete pipeline is linear in n under fixed architecture, dimensions, factor width, and iteration budgets.Source: §IV · p. 8
  • LoomSC uses the same architecture and optimization hyperparameters across datasets, with 5,000 pretraining epochs and 5,000 joint-training epochs.The factor width is m = 380; spectral embedding dimension is set to k, followed by k-means.Source: §IV · pp. 8–9
  • Clustering quality is reported as ACC, NMI, and ARI percentages, with higher values indicating better clustering and repeated-run means and standard deviations over three seeds where available.The synthetic experiments also report CONN, for which higher values are preferred.Source: §IV · p. 9

A. Clustering quality

LoomSC ranks first or second in all 15 dataset–metric comparisons, while combining strong clustering quality with measured runtime advantages. Synthetic experiments retain high accuracy as sample counts grow to 500,000.

A. Clustering quality

  • 6.66 points: LoomSC’s mean ACC exceeds the highest baseline mean, and it ranks first or second in all 15 dataset–metric comparisons.Its mean NMI and ARI exceed the highest corresponding baseline means by 4.09 and 10.02 points.Source: A. Clustering quality · p. 9
  • On all five datasets, LoomSC has higher ACC than every scalable non-deep baseline, with gains of 3.98–8.17 points over the strongest method in that group.Against the best ACC among LMVSC, SGL, and S5C, gains reach 23.92 points on ORL and 72.32 points on EYaleB.Source: A. Clustering quality · p. 9

B. Computational efficiency

  • Table IV reports that LoomSC lies on the empirical ACC–runtime Pareto frontier for every benchmark among the evaluated implementations.Its measured mean runtimes are 0.239 s on ORL, 0.203 s on UMIST, 2.240 s on EYaleB, 9.008 s on Fashion-MNIST, and 25.311 s on COIL-100.Source: Table IV · p. 10, B. Computational efficiency · p. 10

A. Clustering quality

  • Across five datasets, LoomSC improves over PRO-DSC by an average of 11.08 ACC points, 6.72 NMI points, and 13.28 ARI points.PRO-DSC nevertheless attains the highest scores on UMIST and COIL-100, where LoomSC ranks second on all three metrics.Source: A. Clustering quality · p. 10

B. Computational efficiency

  • LoomSC avoids full-affinity storage in both representation learning and spectral inference by retaining thin factors and reducing spectral computation to q = m(m + 1)/2 dimensions.For fixed factor width, q is independent of sample count; linear time and memory bounds hold under fixed dimensions and iteration budgets.Source: B. Computational efficiency · p. 10

C. Scalability Analysis

  • Across tested sampling densities, LoomSC maintains 99%–100% ACC and 0.68–0.75 connectivity; with 30 samples per subspace, it reaches 99% ACC versus about 85% for SDSNet.With 50 samples per subspace, its ACC is 100% versus about 87% for SDSNet; at the largest size it runs in 39 s versus 143 s in both CPU and GPU panels.Source: C. Scalability Analysis · pp. 10–11, Figure 1 · p. 11
  • From 1,000 to 500,000 samples, LoomSC maintains at least 99.8% ACC; runtime rises from about 57 s at 50,000 samples to 362 s at 500,000.The reported design has linear sample-dependent work under fixed dimensions and iteration budgets, supporting increased dataset size without a corresponding accuracy loss.Source: C. Scalability Analysis · pp. 11–12, Figure 2 · p. 12
  • Figure 3 tracks relative Frobenius change between successive affinity iterates on synthetic and real datasets as a diagnostic of sample-relationship stability.The measure is the change norm divided by the previous iterate’s norm, rather than a measure of matrix scale alone.Source: Figure 3 · p. 12

D. Convergence of the Affinity Matrix

The learned affinities stabilize during training and retain class- or subspace-aligned structure across the illustrated datasets. LoomSC also reports strong benchmark results and scaling to large synthetic datasets.

D. Convergence of the Affinity Matrix

  • Synthetic affinity changes fall to a few 10^-3 within roughly 100 outer iterations and approach 10^-3 by the run’s end across six sampling densities.The terminal scales remain similar as samples per subspace increase from 30 to 1,000.Source: D. Convergence of the Affinity Matrix · p. 12
  • UMIST falls below 10^-3 after about 100 iterations; Fashion-MNIST has temporary excursions and EYaleB settles around a few 10^-3.Together, the real-data curves show rapid reduction in update magnitude followed by sustained small changes.Source: D. Convergence of the Affinity Matrix · p. 12

E. Affinity-matrix structure

V. CONCLUSION

  • For fixed dimensions and iteration budgets, LoomSC has linear time and memory complexity in sample count and avoids forming the full affinity or sample Laplacian.The analysis also identifies conditions for projector approximation, subspace-membership preservation, and within-subspace connectivity.Source: §V · p. 14
  • Across five image-clustering benchmarks, LoomSC achieves the highest average ACC, NMI, and ARI; synthetic runs retain at least 99.8% accuracy through 500,000 samples.Source: §V · p. 14

APPENDIX A SPECTRAL ANALYSIS OF THE LSR APPROXIMATION

The appendix relates the least-squares-regression solution to a row-space projector, then establishes optimality and descent properties for the factor updates.

APPENDIX A SPECTRAL ANALYSIS OF THE LSR APPROXIMATION

  • Along each row-space eigenvector, the LSR normal equation gives (β_j + 2λ)τ_j = β_j, while the solution has eigenvalue zero on the orthogonal complement.The LSR solution and the projector share eigenvectors on the row space, allowing their spectral difference to be quantified.Source: Appendix A · p. 16

APPENDIX B PROOFS FOR THE FACTOR MODEL

  • With P fixed, L = ZP is the unique least-squares minimizer; with L fixed, the Procrustes update is globally optimal.When Z⊤L is rank deficient, zero singular directions are included and different orthonormal completions can yield different minimizers.Source: Appendix B · p. 16
  • When m equals the rank of Z, every global minimizer yields the unique row-space projector C = Z†Z, although its orthonormal basis P is nonunique.For m greater than the rank, range(P) also includes extra directions orthogonal to the row space.Source: Appendix B · p. 16
  • Each exact block update cannot increase the fixed-Z objective, whose successive values are nonnegative and therefore converge.Source: Appendix B · p. 16

APPENDIX C SUBSPACE PRESERVATION AND CONNECTIVITY

The appendix gives conditions under which the row-space projector preserves subspaces and connects samples within them, then states properties of the quadratic affinity and reduced spectral embedding.

APPENDIX C SUBSPACE PRESERVATION AND CONNECTIVITY

  • At a global fixed-Z optimum with m equal to the latent rank, the projector preserves subspaces when the subspaces form a direct sum.The proof identifies the projector with the row-space projector and uses the block structure of the subspace representation.Source: Appendix C · p. 16
  • A class’s full row-space projector graph is connected exactly when every nonempty partition A, B satisfies rank(ZA) + rank(ZB) > r_a.A singleton containing a nonzero sample is connected and satisfies the condition vacuously.Source: Appendix C · p. 16
  • Under the stated assumptions, positive row rescaling and entrywise squaring preserve off-diagonal support, so the affinity has exactly k connected components.Every diagonal entry is positive when all samples are nonzero.Source: Appendix C · pp. 16–17

APPENDIX D PROPERTIES OF THE QUADRATIC AFFINITY AND SPECTRAL

  • If the active affinity graph has exactly k components, the exact row-normalized embedding gives one distinct row per component, and exact k-means recovers them up to label permutation.Source: Appendix D · p. 17
  • The reduced operator maps the affinity’s spectral problem to an implicit factor-space operator, avoiding explicit sample-level operations.The passage establishes the implicit operator identity.Source: Appendix D · p. 17

APPENDIX E IMPLEMENTATION CONVENTIONS

The implementation appendix specifies initialization, optimizer conventions, factor and spectral accuracy checks, and final clustering procedures.

APPENDIX E IMPLEMENTATION CONVENTIONS

  • The implementation uses squared-distance k-means++ seeding to select m distinct columns for L, with uniform fallback when the denominator is zero.Source: Appendix E · pp. 17–18
  • Adam uses zero initial moments and no added weight-decay penalty; its gradient comes from the pretraining or joint-training objective, respectively.Source: Appendix E · p. 18
  • Factor updates check the residual ∥P⊤P − I_m∥F, while spectral computation retains the analytical mode and checks eigenpair tolerances.The iteration budget or working precision is increased as needed to meet the spectral criteria.Source: Appendix E · p. 18
  • Final clustering uses recorded k-means++ restarts and bounded Lloyd steps, repairs empty clusters, and retains the run with minimum within-cluster sum of squares.Source: Appendix E · p. 18

APPENDIX F COMPLEXITY COMPARISON WITH BASELINES

Appendix F compares the time and representation-storage complexity of LoomSC with baseline methods. It attributes LoomSC’s scalability to avoiding explicit n × n matrices and retaining linear sample-size scaling under fixed dimensions and solver budgets.

APPENDIX F COMPLEXITY COMPARISON WITH BASELINES

  • For sparse graphs, partial eigensolvers retain the benefit of sparse affinities, while a dense graph has ω = O(n²).The comparison defines ω as the cost of one matrix–vector product and counts the common final k-means cost once for the complete pipeline.Source: Appendix F · p. 18
  • Regression-baseline bounds include S5C’s selection and per-sample restricted-regression costs, while explicit assembly and storage of the full coefficient matrix remain quadratic in n.EnSC and A-DSSC retain solver-dependent costs; support-restricted transport is linear in eact per evaluation.Source: Appendix F · p. 18
  • Table V reports time and principal representation-storage bounds rather than total working memory, with fixed optimization budgets suppressed and spectral budgets retained.Its two time columns are additive, and the common final k-means cost is added once.Source: Appendix F · pp. 18–19, Table V · p. 19
  • For fixed m and solver budgets, LoomSC’s learned factors and exact q-dimensional spectral reduction scale linearly with n without forming either n × n matrix.For LoomSC, q = m(m + 1)/2, and quadratic feature rows can be generated as needed rather than storing an n × q matrix.Source: Appendix F · p. 19
  • LMVSC, SGL, and S5C also scale linearly in sample size under fixed budgets, while EnSC and SSC-OMP still scan the full dataset as their dictionary.SSSC has explicit Rdropρn² dependence; PRO-DSC uses mini-batches for training but retains quadratic full-affinity spectral storage.Source: Appendix F · pp. 18–19
Loading 2610.10266v1…