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

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

cs.CVOct 7, 2026

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

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

Organizations: École de technologie supérieure (ÉTS), Montréal, QC, Canada · University of Bahrain (UOB), Kingdom of Bahrain · Université du Québec à Montréal (UQAM), Montréal, QC, Canada · COMSATS University Islamabad, Islamabad, Pakistan

Abstract

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.

Figures & tables

			Non-deep methods								Deep methods
Dataset	$n$	$k$	EnSC	SSC-OMP	LMVSC	SGL	S 5 C	LSR	A-DSSC	SSSC	PRO-DSC	LoomSC
Fashion-MNIST	5,000	10	61.35 $\pm$ 0.00	56.19 $\pm$ 1.36	59.18	54.47 $\pm$ 0.36	54.62 $\pm$ 1.99	59.52 $\pm$ 0.00	39.01 $\pm$ 2.20	42.01 $\pm$ 1.70	52.12 $\pm$ 2.92	65.33 $\pm$ 1.79
ORL	400	40	78.00 $\pm$ 1.59	73.75 $\pm$ 0.82	55.25 $\pm$ 0.00	62.25 $\pm$ 0.00	42.50 $\pm$ 0.00	82.50 $\pm$ 0.00	50.75 $\pm$ 0.00	46.50 $\pm$ 1.54	52.00 $\pm$ 7.91	86.17 $\pm$ 2.01
UMIST	575	20	72.52 $\pm$ 0.00	67.70 $\pm$ 0.00	60.62 $\pm$ 0.00	65.00 $\pm$ 0.00	40.87 $\pm$ 0.00	58.26 $\pm$ 0.00	52.52 $\pm$ 0.00	21.16 $\pm$ 1.31	81.39 $\pm$ 1.58	80.00 $\pm$ 2.19
EYaleB	2,432	38	88.19 $\pm$ 0.00	80.84 $\pm$ 1.34	21.50 $\pm$ 0.00	21.50 $\pm$ 0.00	22.41 $\pm$ 0.00	96.26 $\pm$ 0.00	61.88 $\pm$ 0.00	25.11 $\pm$ 2.27	77.63 $\pm$ 0.73	94.73 $\pm$ 1.26
COIL-100	7,200	100	67.50 $\pm$ 0.69	59.46 $\pm$ 0.00	49.50 $\pm$ 0.00	49.26 $\pm$ 0.00	42.04 $\pm$ 0.00	61.10 $\pm$ 0.00	48.57 $\pm$ 0.00	13.81 $\pm$ 1.31	82.31 $\pm$ 0.30	74.64 $\pm$ 1.34

TABLE I: Clustering quality — ACC (%) on the five benchmarks. Higher is better. Mean

\pm

standard deviation over three seeds where available. Bold indicates the largest mean in each row.

	Non-deep methods								Deep methods
Dataset	EnSC	SSC-OMP	LMVSC	SGL	S 5 C	LSR	A-DSSC	SSSC	PRO-DSC	LoomSC
Fashion-MNIST	60.29 $\pm$ 0.88	57.93 $\pm$ 0.41	64.37 $\pm$ 0.63	62.51 $\pm$ 0.42	54.82 $\pm$ 2.33	63.33 $\pm$ 0.00	53.83 $\pm$ 1.00	46.88 $\pm$ 0.45	56.45 $\pm$ 3.08	63.91 $\pm$ 0.82
ORL	89.25 $\pm$ 0.07	84.54 $\pm$ 0.37	74.53 $\pm$ 0.00	78.24 $\pm$ 0.00	64.76 $\pm$ 0.00	90.07 $\pm$ 0.00	77.93 $\pm$ 0.00	66.84 $\pm$ 1.34	71.71 $\pm$ 5.39	91.76 $\pm$ 0.88
UMIST	87.06 $\pm$ 0.00	63.61 $\pm$ 0.53	62.49 $\pm$ 0.00	56.84 $\pm$ 0.00	56.72 $\pm$ 0.00	75.40 $\pm$ 0.00	66.01 $\pm$ 0.00	32.89 $\pm$ 1.40	90.02 $\pm$ 0.20	87.83 $\pm$ 1.44
EYaleB	74.31 $\pm$ 0.03	83.17 $\pm$ 0.55	13.37 $\pm$ 0.00	6.44 $\pm$ 0.00	37.92 $\pm$ 0.00	95.44 $\pm$ 0.00	75.61 $\pm$ 0.00	34.24 $\pm$ 2.42	82.38 $\pm$ 0.91	95.47 $\pm$ 0.43
COIL-100	90.95 $\pm$ 0.02	57.11 $\pm$ 0.16	74.69 $\pm$ 0.00	74.54 $\pm$ 0.00	68.03 $\pm$ 0.00	85.21 $\pm$ 0.00	74.31 $\pm$ 0.00	37.80 $\pm$ 1.08	95.75 $\pm$ 0.05	90.95 $\pm$ 0.41

TABLE II: Clustering quality — NMI (%) on the five benchmarks. Higher is better. Mean

\pm

standard deviation over three seeds. Bold indicates the largest mean in each row.

	Non-deep methods								Deep methods
Dataset	EnSC	SSC-OMP	LMVSC	SGL	S 5 C	LSR	A-DSSC	SSSC	PRO-DSC	LoomSC
Fashion-MNIST	43.21 $\pm$ 1.04	42.00 $\pm$ 0.16	45.35 $\pm$ 0.87	42.75 $\pm$ 0.22	40.27 $\pm$ 1.50	46.53 $\pm$ 0.00	22.24 $\pm$ 1.29	19.41 $\pm$ 1.49	37.76 $\pm$ 4.07	51.89 $\pm$ 1.43
ORL	69.50 $\pm$ 0.55	60.22 $\pm$ 0.74	39.22 $\pm$ 0.00	47.60 $\pm$ 0.00	22.66 $\pm$ 0.00	74.10 $\pm$ 0.00	21.49 $\pm$ 0.00	15.32 $\pm$ 4.98	35.55 $\pm$ 8.75	78.05 $\pm$ 2.67
UMIST	66.91 $\pm$ 0.00	34.81 $\pm$ 0.47	32.12 $\pm$ 0.00	25.19 $\pm$ 0.00	26.63 $\pm$ 0.00	46.89 $\pm$ 0.00	22.99 $\pm$ 0.00	1.07 $\pm$ 0.31	79.36 $\pm$ 0.65	75.55 $\pm$ 2.69
EYaleB	19.67 $\pm$ 0.06	53.91 $\pm$ 5.11	1.87 $\pm$ 0.00	-0.40 $\pm$ 0.00	13.65 $\pm$ 0.00	92.19 $\pm$ 0.00	21.67 $\pm$ 0.00	2.16 $\pm$ 0.31	64.15 $\pm$ 1.28	91.76 $\pm$ 0.90
COIL-100	61.38 $\pm$ 1.84	21.98 $\pm$ 0.13	43.00 $\pm$ 0.00	43.93 $\pm$ 0.00	35.05 $\pm$ 0.00	54.03 $\pm$ 0.00	7.84 $\pm$ 0.00	1.59 $\pm$ 0.04	80.63 $\pm$ 1.28	66.60 $\pm$ 0.66

TABLE III: Clustering quality — ARI (%) on the five benchmarks. Higher is better. Mean

\pm

standard deviation over three seeds. Bold indicates the largest mean in each row.

		Non-deep methods								Deep methods
Dataset	$n$	EnSC	SSC-OMP	LMVSC	SGL	S 5 C	LSR	A-DSSC	SSSC	PRO-DSC	LoomSC
Fashion-MNIST	5,000	3219.752 $\pm$ 46.948	5.447 $\pm$ 0.681	16.965 $\pm$ 0.179	17.203 $\pm$ 0.219	8.280 $\pm$ 1.000	6.260 $\pm$ 0.157	35.612 $\pm$ 0.584	2231.314 $\pm$ 69.877	563.338 $\pm$ 1.392	9.008 $\pm$ 0.987
ORL	400	7.953 $\pm$ 0.514	1.856 $\pm$ 0.058	0.929 $\pm$ 0.031	0.958 $\pm$ 0.003	7.440 $\pm$ 0.419	0.049 $\pm$ 0.001	0.699 $\pm$ 0.005	7.084 $\pm$ 0.183	102.797 $\pm$ 2.671	0.239 $\pm$ 0.089
UMIST	575	24.366 $\pm$ 26.899	0.498 $\pm$ 0.012	1.086 $\pm$ 0.033	1.263 $\pm$ 0.043	10.249 $\pm$ 4.946	0.077 $\pm$ 0.002	1.026 $\pm$ 0.027	9.774 $\pm$ 1.423	78.689 $\pm$ 0.172	0.203 $\pm$ 0.003
EYaleB	2,432	43.843 $\pm$ 0.398	12.666 $\pm$ 0.975	9.124 $\pm$ 0.063	9.221 $\pm$ 0.083	471.768 $\pm$ 24.647	2.389 $\pm$ 0.542	13.918 $\pm$ 0.132	2286.421 $\pm$ 94.488	313.648 $\pm$ 2.670	2.240 $\pm$ 0.581
COIL-100	7,200	50.858 $\pm$ 1.523	1319.586 $\pm$ 164.863	21.421 $\pm$ 0.143	22.498 $\pm$ 0.390	4709.568 $\pm$ 169.023	49.888 $\pm$ 5.451	175.328 $\pm$ 1.551	2409.599 $\pm$ 245.492	7443.627 $\pm$ 4.992	25.311 $\pm$ 9.976

TABLE IV: Measured wall-clock time (s). Lower is better. Bold indicates the smallest mean in each row.

Panel of Figure 5 — Fig. 1: Synthetic-data comparison with ten subspaces and $n_{i}$ samples per subspace. Panels show (a) ACC, (b) connectivity, (c) CPU runtime, and (d) GPU runtime. “Ours” denotes LoomSC.

Fig. 2: Synthetic-data scalability from

1{,}000

500{,}000

samples: (a) runtime and (b) clustering accuracy. The horizontal-axis symbol

N

denotes the total sample count

n

. The reference curves indicate linear and quadratic growth. “Ours” denotes LoomSC.

Fig. 3: Relative Frobenius change

\|A_{t}-A_{t-1}\|_{F}/\|A_{t-1}\|_{F}

on (a) synthetic datasets with ten subspaces and (b) real datasets. Here,

A_{t}

denotes the affinity matrix in ( 24 ) at outer iteration

t

, and

n_{i}

is the number of samples in synthetic subspace

i

Panel of Figure 8 — Fig. 4: Learned sample relations on a ten-class EYaleB subset at epochs $10$ , $100$ , and $500$ . Class boundaries are overlaid.

Panel of Figure 9 — Fig. 5: Learned sample relations on a ten-class ORL subset at epochs $10$ , $100$ , and $500$ . Class boundaries are overlaid.

Panel of Figure 10 — Fig. 6: Learned sample relations on synthetic data with ten subspaces at epochs $10$ , $100$ , and $500$ . Subspace boundaries are overlaid.

Panel of Figure 11 — Fig. 7: Learned sample relations on synthetic data with ten subspaces and increasing total sample count at epoch $500$ . Subspace boundaries are overlaid.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Method	Deep	Representation / affinity learning	Spectral computation	Matrix storage
LMVSC [ 15 ]	No	$nd_{x}m+nm^{3}$	$nm^{2}+m^{3}$	$nm$
SGL [ 16 ]	No	$nd_{x}m+nm^{3}$	$nm^{2}+m^{3}$ a	$nm$
S 5 C [ 29 ]	No	$n(d_{x}m+c_{\ell_{1}})$	$\mathcal{C}_{\mathrm{sp}}(n,nm)$	$nm$
EnSC [ 19 ]	No	$n^{2}d_{x}+nc_{\mathrm{EN}}$	$\mathcal{C}_{\mathrm{sp}}(n,ns)$	$ns$
SSC-OMP [ 18 ]	No	$n^{2}d_{x}s$	$\mathcal{C}_{\mathrm{sp}}(n,ns)$	$ns$
A-DSSC [ 22 ]	No	$\mathcal{C}_{C}+\mathcal{C}_{\mathrm{chk}}+e_{\mathrm{act}}$	$\mathcal{C}_{\mathrm{sp}}(n,e_{\mathrm{act}})$	$\mathcal{M}_{C}+e_{\mathrm{act}}$

Appendix

TABLE V: Time and representation-storage complexity of the compared methods. All entries are inside

O(\cdot)

. The two time columns are additive, with the common final

k

-means cost added once. Fixed optimization budgets are suppressed. Spectral budgets are included through ( 55 ). The last column counts the principal coefficient, factor, and affinity matrices, not total working memory. Bounds are obtained from the original algorithms under the implementation conventions stated below.

Explore similar work

Nonlinear mixture model motivated subspace clustering
Jun 28, 2026Ivica KoprivaSubspace Mixture Models
Division of Computing and Data Science, Ruđer Bošković Instute, Zagreb, Croatia
Online Supervised Dimension Reduction with Random Features: Diagnostics and Computational Trade-offs
Sep 17, 2026Zhenlin Yao, Wei XiongPrincipal Component Analysis Subspace
School of Statistics University of International Business and Economics Beijing, China
Efficient Clustering with Provable Guardrails for LLM Inference at Scale
Jul 22, 2026Longshaokan Wang, Wai Tsang Keung, Punit Ghodasara +3Clustering LLM Inference Optimization
Amazon

Jun 28, 2026, cs.LGJ/K move · Enter open · S save

Nonlinear mixture model motivated subspace clustering

Ivica Kopriva

Division of Computing and Data Science, Ruđer Bošković Instute, Zagreb, Croatia

Subspace Mixture Models Nonnegative Matrix Factorization Speech Separation

Open paper AskPDF arXiv

We derive the linear union-of-subspaces (UoS) model for subspace clustering (SC) from the nonlinear mixture model (NMM) used in blind source separation (BSS) to represent a D-dimensional observation vector as an unknown multivariate nonlinear mapping of C latent variables. Assuming the mapping is differentiable up to an unknown order K, we approximate NMM by a K-th order Taylor expansion, yielding a model equivalent to the linear UoS framework underlying SC. This establishes that: (i) the smoothness order K corresponds to the unknown subspace dimension d; (ii) KC equals the number of anchors; and (iii) the sparsity of the representation vector equals K (i.e., d). These relationships enable estimation of bounds on subspace dimension, and that is validated on six benchmark datasets using five established SC algorithms. Established theoretical results are important for post-processing of self-representation matrices estimated by SC algorithms.

Abstract

Explore similar work

Nonlinear mixture model motivated subspace clustering

Online Supervised Dimension Reduction with Random Features: Diagnostics and Computational Trade-offs

Efficient Clustering with Provable Guardrails for LLM Inference at Scale