Research map / Learning theory and algorithms / Matrix and tensor methods
Multi-Subspace Matrix Recovery from Permuted Data
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PMSDR, a four-stage pipeline (outlier detection, subspace reconstruction, outlier classification, unsupervised-sensing matrix recovery) to recover multi-subspace matrices whose columns are partially permuted, with theory for the classification step.
Problem
Recovering a matrix whose columns lie in a union of low-dimensional subspaces when some columns are corrupted by entry permutations, a setting existing methods (robust PCA, single-subspace permuted recovery) do not handle.
Approach
Decompose the task into outlier detection (provable self-representation matrix), SSC-based subspace clustering with SVD bases, an iterative residual-elimination classifier that assigns each permuted outlier to its subspace with theoretical guarantees, and UPCA-style unlabeled sensing for recovery.
Key results
- On Hopkins-155, PMSDR achieves median matrix recovery error 0.013 (2 subspaces) and 0.012 (3 subspaces), versus 0.046 and 0.047 for vanilla RPCA.
- On synthetic data with 5 subspaces, PMSDR runs in 4.3 s versus 9.9 s for RKPCA and 698.8 s for MRUC.
- On Extended Yale B with 10 subjects, outlier classification error with ground-truth bases is 0.025 (median 0.025) and with reconstructed bases 0.100, per the reported table.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| augment RPCA with PMSDR | RPCA · Hopkins-155, 2 subspaces | recovery error: 0.046 -> 0.040 | Helped |
| augment RPCA with PMSDR | RPCA · Hopkins-155, 3 subspaces | recovery error: 0.047 -> 0.043 | Helped |
| augment RKPCA with PMSDR | RKPCA · Hopkins-155, 2 subspaces | recovery error: 0.009 -> 0.053 | Hurt |
| augment RKPCA with PMSDR | RKPCA · Hopkins-155, 3 subspaces | recovery error: 0.008 -> 0.047 | Hurt |
| augment SSC with PMSDR | SSC · Hopkins-155, 2 subspaces | recovery error: 0.087 -> 0.091 | Hurt |
| augment SSC with PMSDR | SSC · Hopkins-155, 3 subspaces | recovery error: 0.100 -> 0.101 | Hurt |
| augment MRUC with PMSDR | MRUC · Hopkins-155, 2 subspaces | recovery error: 0.066 -> 0.048 | Helped |
| augment MRUC with PMSDR | MRUC · Hopkins-155, 3 subspaces | recovery error: 0.085 -> 0.056 | Helped |
| use estimated rank 3 or 4 instead of ground-truth rank 5 (ablation) | PMSDR · Synthetic data, 3 and 10 subspaces | recovery error: 0.1330 -> 0.8827; 0.1372 -> 0.9164 | Hurt |
| use estimated rank 6 or 7 instead of ground-truth rank 5 (ablation) | PMSDR · Synthetic data, 3 and 10 subspaces | recovery error: 0.1330 -> 0.1405; 0.1372 -> 0.1951; 0.1330 -> 0.2193; 0.1372 -> 0.2226 | Hurt |
| increase the subspace dimension from r=3 to r=15 (ablation) | PMSDR · Synthetic data, 2, 5, and 10 subspaces | recovery error: 0.0916 -> 0.7053; 0.0847 -> 0.7685; 0.1024 -> 0.8441 | Hurt |
Surprising findings
- Vanilla RKPCA outperforms PMSDR-augmented RKPCA-S on Hopkins-155 with 2 and 3 subspaces, the paper notes RKPCA gains little from the pipeline.
Limitations
- Restricted to partially shuffled data; fully shuffled columns need a preprocessing step such as MRUC.
- Handles only linear/affine subspaces; nonlinear extension left to future work.
- Outlier classification depends on accurate basis estimation, and clustering error from SSC degrades reconstructed-basis performance.
Experimental setup
Datasets: Extended Yale B Hopkins-155 educational student scores dataset medical tumor dataset synthetic data
Benchmarks: Extended Yale B Hopkins-155 synthetic permuted multi-subspace data educational and medical de-anonymization data
Metrics: outlier classification error matrix recovery error (normalized Frobenius) permutation error ratio runtime
Baselines: RPCA RKPCA SSC MRUC UPCA
Builds on: UPCA sparse subspace clustering robust PCA provable self-representation matrix MRUC
Closest papers by meaning
- Subspace Recovery from Heterogeneous Data with Non-isotropic Noise (NeurIPS 2022 · similarity 0.87)
- Unlabeled Principal Component Analysis (NeurIPS 2021 · similarity 0.87)
- Fast recovery from a union of subspaces (NeurIPS 2016 · similarity 0.86)
- Fast exact recovery of noisy matrix from few entries: the infinity norm approach (NeurIPS 2025 · similarity 0.85)
- A Subspace-Constrained Tyler's Estimator and its Applications to Structure from Motion (CVPR 2024 · similarity 0.84)
- Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.