Connections Between Nuclear-Norm and Frobenius-Norm-Based Representations

Xi Peng, Canyi Lu, Yi Zhang, Huajin Tang

Abstract: A lot of works have shown that Frobenius-norm-based representation (FNR) is competitive to sparse representation and nuclear-norm-based representation (NNR) in numerous tasks such as subspace clustering. Despite the success of FNR in experimental studies, less theoretical analysis is provided to understand its working mechanism. In this brief, we fill this gap by building the theoretical connections between FNR and NNR. More specially, we prove that: 1) when the dictionary can provide enough representative capacity, FNR is exactly NNR even though the data set contains the Gaussian noise, Laplacian noise, or sample-specified corruption and 2) otherwise, FNR and NNR are two solutions on the column space of the dictionary.

Bridging the Theory-Practice Gap

In machine learning and computer vision, data points are often represented as linear combinations of other points within a "dictionary." To find the most effective representation, researchers typically rely on Sparse Representation (SR) using the $\ell_1$-norm or Nuclear-norm-based Representation (NNR/LRR) to find low-rank structures.

Frobenius-norm-based Representation (FNR), which uses the $\ell_2$-norm, has often been dismissed as a "naive" alternative because it does not explicitly promote sparsity or low rank. However, empirical studies in face recognition and subspace clustering have shown that FNR is surprisingly competitive and significantly faster. This paper addresses the "theory-practice gap" by providing a rigorous mathematical foundation for why FNR performs so well despite its lack of explicit low-rank guarantees.

Methodology and the Equivalence Theorem

The authors utilize Singular Value Decomposition (SVD) and the Augmented Lagrange Multiplier (ALM) framework to analyze optimization objectives under various conditions, including exact versus relaxed constraints and different noise models (Gaussian, Laplacian, and sample-specific corruptions).

Summary of equivalence between FNR and NNR under different conditions.

The core finding is the Equivalence Theorem: when a dictionary has sufficient representative capacity (i.e., it can span the data), FNR is mathematically identical to NNR. As shown in the summary table above, both methods converge to the same optimal solution $C^*$ in both noiseless and noisy environments when constraints are exact.

A Unified Framework for Representation

The research demonstrates that both FNR and NNR solutions can be expressed in a unified form: $C^* = V \mathcal{P}(\Sigma) V^T$, where $V$ and $\Sigma$ are derived from the SVD of the data. The primary difference between the two methods lies in the specific shrinkage-thresholding operator $\mathcal{P}(\cdot)$ applied to the singular values.

Key insights from this unified view include:

  • Structural Respect: FNR works because it projects data onto the same column space as NNR, naturally respecting the low-rank structure inherent in the data's own subspace.
  • Computational Efficiency: Because FNR is strictly convex, it avoids local minima and can be solved over 100 times faster than NNR in tasks like face recognition, while yielding nearly identical results.

Comparative Analysis of Objective Functions

The paper provides a detailed mapping of various objective functions to their optimal solutions, confirming that the relationship holds across different norm combinations and regularization strategies.

Detailed comparison of objective functions and their corresponding optimal solutions.

As detailed in the table above, whether using the Frobenius norm or the Nuclear norm, the resulting optimal representation $C^*$ maintains the same structural form. In the noise-free case with exact constraints, both methods converge to the shape interaction matrix $C^* = V_r V_r^T$.

Conclusion and Future Directions

This work provides the theoretical justification for the use of FNR in practical applications. By proving that FNR is essentially a computationally efficient version of NNR when the dictionary is sufficiently representative, the authors explain its success in subspace clustering and motion segmentation.

Future work may explore extending this theoretical bridge to Sparse Representation (SR), which relies on different geometric properties ($\ell_1$ vs $\ell_2$ balls), and investigating scenarios where dictionary capacity is highly limited, potentially causing the two methods to diverge.

Summary updated

Abstract

A lot of works have shown that frobenius-norm-based representation (FNR) is competitive to sparse representation and nuclear-norm-based representation (NNR) in numerous tasks such as subspace clustering. Despite the success of FNR in experimental studies, less theoretical analysis is provided to understand its working mechanism. In this brief, we fill this gap by building the theoretical connections between FNR and NNR. More specially, we prove that: 1) when the dictionary can provide enough representative capacity, FNR is exactly NNR even though the data set contains the Gaussian noise, Laplacian noise, or sample-specified corruption and 2) otherwise, FNR and NNR are two solutions on the column space of the dictionary.
BibTeX
@article{peng2016connections,
  author = {Xi Peng and Canyi Lu and Yi Zhang and Huajin Tang},
  title = {{Connections Between Nuclear-Norm and Frobenius-Norm-Based Representations}},
  journal = {IEEE Transactions on Neural Networks and Learning Systems},
  year = {2016},
  doi = {10.1109/tnnls.2016.2608834},
}

Loading related content...

Figure