PaperlayerView exact revision on arXiv

Source-linked AI summary

Fixed-Rank Representation for Unsupervised Visual Learning

Risheng Liu, Zhouchen Lin, Fernando De la Torre, Zhixun Su

arXiv:1203.2210v2cs.CVmath.NA

TL;DR

Existing unsupervised visual-learning methods can be computationally expensive and may yield degenerate solutions with insufficient data sampling. This paper proposes fixed-rank representation (FRR), a factorized framework for robust subspace clustering and feature extraction. The authors show that FRR can recover multiple-subspace structure, including memberships under suitable insufficient-sampling conditions, while avoiding iterative SVD computation.

  • Problem

    Insufficient sampling can cause existing subspace-clustering methods to produce degenerate solutions, while their optimization can be computationally expensive.

  • Method

    FRR factorizes the representation into two low-rank matrices, adds a sparse regularizer for noise and outliers, and extends to feature extraction through transposed FRR.

  • Results

    FRR reveals multiple-subspace structure and can identify subspace memberships under suitable insufficient-sampling conditions, while avoiding SVD computation.

  • Takeaways & Limitations

    FRR provides a unified framework for robust unsupervised visual learning that covers subspace clustering and feature extraction.

Abstract

from arXiv · show

Subspace clustering and feature extraction are two of the most commonly used unsupervised learning techniques in computer vision and pattern recognition. State-of-the-art techniques for subspace clustering make use of recent advances in sparsity and rank minimization. However, existing techniques are computationally expensive and may result in degenerate solutions that degrade clustering performance in the case of insufficient data sampling. To partially solve these problems, and inspired by existing work on matrix factorization, this paper proposes fixed-rank representation (FRR) as a unified framework for unsupervised visual learning. FRR is able to reveal the structure of multiple subspaces in closed-form when the data is noiseless. Furthermore, we prove that under some suitable conditions, even with insufficient observations, FRR can still reveal the true subspace memberships. To achieve robustness to outliers and noise, a sparse regularizer is introduced into the FRR framework. Beyond subspace clustering, FRR can be used for unsupervised feature extraction. As a non-trivial byproduct, a fast numerical solver is developed for FRR. Experimental results on both synthetic data and real applications validate our theoretical analysis and demonstrate the benefits of FRR for unsupervised visual learning.

I. INTRODUCTION

Existing unsupervised visual-learning methods use sparsity or rank minimization for subspace clustering, but can be computationally costly and fragile under corrupted or insufficiently sampled data. The paper proposes fixed-rank representation (FRR), which factorizes the representation, supports subspace clustering and feature extraction, and avoids iterative SVD computation.

  • Limitations of existing methods: SSC constructs an affinity graph from individually sparsest representations, lacking a global structural constraint and potentially degrading under gross corruption.
  • Limitations of existing methods: SSC’s connectivity assumption holds only for 2- and 3-dimensional subspaces, so it may over-segment higher-dimensional subspaces.
  • Limitations of existing methods: LRR can reveal true clustering for independent subspaces with sufficient sampling, but nuclear-norm minimization typically requires SVD at every iteration.
  • Limitations of existing methods: With insufficient observations, LRR and SSC may produce degenerate solutions that significantly degrade clustering, while latent-variable remedies make optimization more complex.
  • Fixed-rank representation: FRR parameterizes the representation as a product of two low-rank matrices, and under suitable conditions identifies subspace memberships even with insufficient sampling.
  • Fixed-rank representation: FRR avoids SVD computation and can be applied efficiently to large-scale problems; its transposed form extends the framework to unsupervised feature extraction related to PCA.

II. A REVIEW OF PREVIOUS WORK

Subspace clustering assigns data points drawn from multiple subspaces to their respective subspaces. The reviewed methods analyze this problem in the noise-free case using the data matrix and its compact SVD.

  • The data are modeled as points sampled from a union of subspaces, with each subspace contributing a collection of data points.
  • Subspace clustering aims to cluster data points into their respective subspaces.
  • The review covers SSC and LRR as approaches for solving the subspace-clustering problem.
  • The analysis first considers noise-free data and uses the compact SVD and rank of the data matrix.

A. Sparse Subspace Clustering (SSC)

SSC represents each point using other points from its subspace and builds a graph for clustering, whereas LRR uses a low-rank criterion. These approaches face numerical, computational, and insufficient-sampling limitations.

  • Sparse Subspace Clustering (SSC): SSC seeks sparse representation coefficients so each point is expressed as a combination of other points in the same subspace.
  • Sparse Subspace Clustering (SSC): SSC forms an undirected graph from the representation coefficients and applies NCut to obtain clustering.
  • Sparse Subspace Clustering (SSC): The l1-norm SSC models can only be solved numerically.
  • Low-Rank Representation (LRR): LRR extends sparsity from one-dimensional representations to matrix representations and uses nuclear-norm minimization as a surrogate for rank minimization.
  • Low-Rank Representation (LRR): LRR has a closed-form block-diagonal solution, but its computation still cannot completely avoid SVD.
  • Limitations: Insufficient observations can make LRR or SSC produce degenerate solutions that significantly degrade clustering performance.
  • Motivation: This motivates seeking a lower-rank representation in the row space that can reveal subspace memberships despite insufficient sampling.

B. The Basic Model

FRR minimizes representation complexity through a fixed-rank factorization, yielding globally optimal solutions with a rank-controlled objective. Under clean, independent-subspace conditions, its solution has block structure, while lower-rank factors address insufficient sampling.

  • Model: FRR minimizes the Frobenius norm of a representation while jointly optimizing a fixed-rank factorization.
  • Solution Properties: The globally optimal solution is not necessarily unique, although choosing the first k columns of V_X worked well empirically on tested data.
  • Model: The factorized formulation is non-convex because its minimizer is not unique.
  • Theorem 1: For any fixed m ≤ r_X, the proposed solution is globally optimal and has minimum objective value r_X − m.
  • Structure: Under independent subspaces and clean data, a globally optimal solution has block-diagonal representation with k blocks.
  • Structure: Each block corresponds to one subspace and has rank equal to that subspace's dimension.
  • Insufficient Sampling: The basic optimal representation can degenerate under insufficient sampling, but the factor product L*R* remains spanned by the row space of X and motivates a lower-rank clustering representation.
  • Constraints: Column normalization is not always guaranteed in real situations, so the method explicitly enforces column-sum constraints.

D. Sparse Regularization for Corruptions

FRR is extended to corrupted data by adding a sparse corruption term and balancing it against the representation objective. The resulting framework constructs an affinity graph and applies NCut for clustering.

  • Robust Model: The corruption-robust FRR model adds an error term E to represent corruptions.
  • Robust Model: A parameter μ balances the representation objective against the sparse corruption penalty.
  • Robust Model: The l2,1 norm is used to characterize corruptions because it can identify outlier indices and remove small noise.
  • Algorithm: The algorithm takes data points sampled from k subspaces as input.
  • Algorithm: The clustering procedure solves the FRR optimization problem, constructs an affinity matrix from Z* or L*R*, and applies NCut.

IV. EXTENDING FRR FOR FEATURE EXTRACTION

FRR extends beyond subspace clustering to unsupervised feature extraction by recovering the data column space. A robust TFRR variant adds an explicit corruption term for noisy data.

  • FRR can also be applied to unsupervised feature extraction.
  • Feature extraction recovers the data set’s column space by solving a transposed FRR formulation.
  • For noisy data, robust TFRR introduces an explicit corruption term into the objective and constraint.

A. Relationship to Principal Component Analysis

The paper connects TFRR to PCA and develops an ADM-type solver for FRR-related models. The solver alternates variable updates while exploiting projection and factorization structure for computational efficiency and stability.

  • Relationship to Principal Component Analysis: TFRR can formulate PCA, whose optimal projection is formed by the first m left singular vectors of X.
  • Relationship to Principal Component Analysis: The PCA-related optimization has minimum objective value r_X − m.
  • The ADM-type solver handles FRR-related models by alternating updates of L, R, Z, and E while updating Lagrange multipliers.
  • Although the augmented problem is not jointly convex, it is convex in each variable when the others are fixed, enabling the iteration scheme.
  • The solver reduces computational cost by exploiting equivalent factor products and avoiding unnecessary matrix inversions.
  • Projection computation uses QR factorization, which is generally more stable than solving normal equations.

VI. EXPERIMENTAL RESULTS

Experiments compare FRR with state-of-the-art methods for subspace clustering and feature extraction, using an ADM-based implementation and controlled computational settings.

  • The experiments evaluate FRR against state-of-the-art algorithms on subspace clustering and feature extraction.
  • Experiments were run on a notebook computer with an Intel Core i7 CPU at 2.00 GHz and 6GB of memory.
  • The implementation uses an ADM-type algorithm with specified inputs, initialization, update, convergence-check, and output steps.
  • Subspace-clustering experiments compare FRR strategies based on Z and LR with SIM, RANSAC, LSA, SSC, and LRR.

1) Synthetic Data:

Synthetic and real-data experiments examine FRR under insufficient sampling, motion segmentation, and image classification settings. LR-based FRR is more robust to insufficient sampling, while FRR variants perform strongly and efficiently on real tasks.

  • Synthetic Data: With at most 30 samples per subspace versus intrinsic dimension 50, the optimal Z degenerates, whereas LR reveals the multiple-subspace structure.
  • Synthetic Data: Z’s clustering accuracy is sampling-sensitive and reaches only around 80% at p = 30, while LR achieves almost perfect results across the generated data.
  • Motion Segmentation: On Hopkins155, SSC, LRR, and FRR outperform other methods for motion segmentation.
  • Motion Segmentation: FRR1 outperforms LRR on real data, attributed to the normalization constraint in its formulation.
  • Motion Segmentation: FRR2 outperforms all other methods in the reported comparison, with LR performing better than the general Z representation.
  • Motion Segmentation: FRR achieves the highest computational efficiency because its iterations completely avoid SVD computation.

B. Feature Extraction and Outlier Detection

TFRR extracts intrinsic facial features while suppressing image errors and non-facial outliers, improving classification and enabling accurate outlier detection.

  • Feature extraction: TFRR learns a mapping P from high-dimensional observations to low-dimensional features, with new features computed as y = Px.Two strategies use P = Z (TFRR1) or an orthogonal basis P = orth(LR) (TFRR2).
  • Classification results: TFRR1 and TFRR2 significantly outperform the baseline and PCA, while TFRR2 outperforms all compared methods.The comparison includes Raw data, PCA, LPP, and NPE.
  • Robust feature recovery: TFRR-based methods recover intrinsic facial features and remove illumination, occlusion, and non-facial outliers.The intrinsic features are represented in ZX, while small errors and outliers are represented by E and removed.
  • Outlier detection: The error term E identifies non-facial outliers because their column l2 norms are larger than those of facial samples.A sample is classified as an outlier when ∥[E]i∥2 ≥ γ.
  • Outlier detection: With γ = 2.2, outlier detection accuracy reaches 98.68% for 40 × 20 + 257 data and 99.19% for 80 × 20 + 257 data.Accuracy is computed as the percentage of correctly identified outliers.

VII. CONCLUSIONS

The paper proposes FRR for robust unsupervised visual learning and shows that it can recover subspace structure and support feature extraction. It also identifies open problems involving basis selection, dimension determination, and extensions to supervised settings.

  • Contributions: FRR is a framework for robust unsupervised visual learning that reveals multiple subspace structure even with insufficient observations.The paper proves this capability for subspace clustering.
  • Contributions: Transposed FRR successfully recovers the column space and can therefore be applied to feature extraction.This extends the framework beyond subspace clustering.
  • Future work: Future work includes deeper analysis of LR, efficient basis selection for subspace clustering, and dimension determination for feature extraction.These issues are stated as unresolved directions.
  • Future work: The paper also proposes applying FRR to supervised and semi-supervised learning.These settings are identified as future extensions.
Loading 1203.2210v2…