Connections Between Nuclear Norm and Frobenius Norm Based Representation

Xi Peng, Canyi Lu, Zhang Yi, 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 paper, 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, 2) otherwise, FNR and NNR are two solutions on the column space of the dictionary.

Introduction

In the realm of computer vision and machine learning, representation learning is a fundamental task, often involving the projection of data into a new space to facilitate processing. Three primary methodologies have dominated this field: Sparse Representation (SR), Low-Rank Representation (LRR/NNR), and Frobenius-norm based Representation (FNR). While NNR, which minimizes the sum of singular values, enjoys a robust theoretical foundation in compressive sensing, empirical evidence frequently shows that the simpler FNR—minimizing the square root of the sum of squares of all entries—performs remarkably well. In many practical scenarios, FNR is not only faster but also more accurate than NNR, a result that has long puzzled researchers who viewed the nuclear norm as a more sophisticated tool for capturing low-rank structures.

Theoretical Framework

This research addresses the theoretical void by employing Singular Value Decomposition (SVD) and the method of Lagrange multipliers to analyze the optimal solutions of NNR and FNR. The authors investigate several scenarios, including exact constraints with uncorrupted data, Gaussian noise ($L_2$ norm), and Laplacian noise or sample-specific corruption ($L_1$ or $L_{2,1}$ norms).

The core finding is that both methods yield an optimal solution $C^*$ that resides within the column space of the dictionary. Specifically, the solution takes the form $V P(\Sigma) V^T$, where $V$ is derived from the SVD of the data, and $P(\cdot)$ represents a shrinkage-thresholding operator.

Summary of equivalence conditions between NNR and FNR under various noise and constraint scenarios.

Key Insights: The Equivalence of Norms

The paper establishes a "Unified Framework," demonstrating that NNR and FNR are essentially variants of the same underlying process. A pivotal discovery is that when the dictionary possesses sufficient representative capacity, FNR is mathematically identical to NNR, even in the presence of significant noise.

The distinction between the two norms does not lie in a fundamental difference between "rank-seeking" and "energy-minimizing" behaviors. Instead, it is determined by the specific shrinkage-thresholding operator applied to the singular values. This insight explains why FNR can achieve comparable performance to NNR in tasks like feature extraction and image clustering while offering a significant computational advantage.

Detailed mapping of objective functions to their optimal solutions and corresponding shrinkage operators.

Practical Implications

The theoretical equivalence has profound practical consequences. Because FNR involves a strictly convex optimization problem, it avoids local minima and can be solved significantly faster than NNR. In face recognition tasks, FNR has been shown to achieve up to a 100x speedup over NNR while maintaining similar accuracy levels. While both methods share a computational complexity of $O(m^2n + n^3)$ due to the SVD, FNR requires far fewer iterations in practice compared to the complex solvers (like the Augmented Lagrange Multiplier method) typically used for NNR.

Conclusion

By establishing a theoretical bridge between the nuclear norm and the Frobenius norm, this work clarifies why FNR is such a potent tool in practice. It extends the principles of compressive sensing—traditionally focused on $L_0$ and $L_1$ norm equivalence—to the relationship between $L_1$ (nuclear norm) and $L_2$ (Frobenius norm) in matrix space. This foundation paves the way for more efficient representation learning algorithms that leverage the simplicity of the Frobenius norm without sacrificing the structural benefits of the nuclear norm.

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 paper, 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, 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 Zhang Yi and Huajin Tang},
  title = {{Connections Between Nuclear Norm and Frobenius Norm Based Representation}},
  journal = {IEEE Transactions on Neural Networks and Learning Systems},
  year = {2016},
  doi = {10.1109/tnnls.2016.2608834},
}

Loading related content...

Figure