Source-linked AI summary
Connections Between Nuclear Norm and Frobenius Norm Based Representations
Xi Peng, Canyi Lu, Zhang Yi, Huajin Tang
TL;DR
FNR has shown competitive empirical performance, but its operating mechanism has received less theoretical analysis. This paper derives connections between FNR and NNR, showing exact equivalence under sufficient dictionary capacity and related column-space solutions otherwise.
Problem
FNR has demonstrated effectiveness experimentally, but fewer theoretical studies explain its relationship with NNR.
Method
The paper analyzes FNR and NNR through their norm-based objectives, singular-value decompositions, and shrinkage-thresholding operators.
Results
With enough dictionary capacity, FNR is equivalent to NNR despite Gaussian, Laplacian, or sample-specific corruption; otherwise, both are solutions on the dictionary’s column space.
Takeaways & Limitations
The results unify FNR and NNR within a theoretical framework that identifies their shared solution structure and equivalence conditions.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
FNR has demonstrated competitive performance, but its effectiveness lacked a comparable theoretical explanation. This paper connects FNR and NNR by analyzing when their optimization problems are equivalent or yield related solutions.
- Background: NNR represents a data set through nuclear-norm minimization, while FNR uses a Frobenius-norm-based objective.Different noise models motivate ℓ2,1-, ℓ1-, or Frobenius-norm penalties.
- Motivation: FNR has performed competitively with sparse and nuclear-norm representations across recognition, subspace learning, feature selection, and clustering tasks.Its objective is strictly convex, avoiding local-minimum issues.
- Contribution: The paper proves that FNR equals NNR when the dictionary has enough representative capacity, including Gaussian, Laplacian, and sample-specific corruption.With limited capacity, the two methods instead produce solutions in the dictionary’s column space.
- Contribution: Both formulations have solutions expressed through singular-value decomposition and shrinkage-thresholding operators.Their difference is characterized by the choice of shrinkage-thresholding operator.
- Background: When the dictionary exactly reconstructs the input without corruption, prior results imply equivalence between NNR and FNR.The paper extends this connection to more complex corrupted-data settings.
III. CONNECTIONS BETWEEN NUCLEAR NORM AND FROBENIUS NORM BASED REPRESENTATION
The paper analyzes FNR and NNR through singular-value decompositions. Their optimal representations share a common form, with equivalence depending on dictionary capacity and data conditions.
- III. CONNECTIONS BETWEEN NUCLEAR NORM AND FROBENIUS NORM BASED REPRESENTATION: Optimal FNR and NNR solutions have the form C* = VP(Σ)VT, where P(·) is a shrinkage-thresholding operator.The data matrix is decomposed using its singular-value decomposition.
- III. CONNECTIONS BETWEEN NUCLEAR NORM AND FROBENIUS NORM BASED REPRESENTATION: FNR and NNR are solutions on the column space of the dictionary and become identical in some situations.The analysis covers exact and relaxed constraints as well as corrupted and uncorrupted data.
- III. CONNECTIONS BETWEEN NUCLEAR NORM AND FROBENIUS NORM BASED REPRESENTATION: The exact constraint is associated with dictionaries having enough representative capacity, whereas limited capacity leads to a relaxed constraint.The paper considers Gaussian, Laplacian, and sample-specific corruption in these settings.
A. Exact Constraint and Uncorrupted Data
The paper frames its connection analysis around self-expression and prior results for uncorrupted data with dictionaries capable of representing the inputs. This setting establishes the baseline equivalence later extended to corrupted cases.
- A. Exact Constraint and Uncorrupted Data: The analysis focuses on self-expression because nearly all NNR methods are developed under that setting.
- A. Exact Constraint and Uncorrupted Data: Prior work established the relevant result for uncorrupted data when the dictionary has enough representative capacity.The cited table summarizes connections between nuclear- and Frobenius-norm formulations.
i (C)) BASED REPRESENTATION IN THE CASE
For noise-free data, the paper establishes matching optimal solutions for NNR and FNR under an exact constraint, with the solution expressed through the data matrix’s singular structure.
- Setting: The analysis is framed for the noise-free and Gaussian-noise situations using the singular values of C and the full SVD D = UΣVT.The passages define the singular-value notation and identify the SVD used in the analysis.
- Exact constraint: Under the exact constraint, NNR has a unique minimizer derived from the skinny SVD of the data matrix.The cited passages identify the skinny SVD and the corresponding unique minimizer, though the displayed formula is fragmented.
- Exact constraint: The Frobenius-norm formulation also yields a unique solution based on the skinny SVD of the uncorrupted data matrix.The section introduces the Frobenius-norm result and specifies that the data are uncorrupted.
- Equivalence: NNR and FNR share the same optimal solution VrVT, also known as the shape interaction matrix.The equivalence is stated through the common solution VrVT, with the shape-interaction interpretation supplied separately.
B. Exact Constraint and Data Corrupted by Gaussian Noise
With an exact constraint and Gaussian noise, the paper shows that FNR and NNR have the same minimizer form, despite differences in the threshold parameter selected by their objectives.
- Gaussian-noise setting: Under Gaussian noise modeled with the Frobenius norm, the two formulations have the same minimizer in the form VkVkT.The result is stated for D = D0 + E with D0 = D0C, where the Gaussian-noise error is represented through the Frobenius norm.
- NNR solution: NNR’s solution is associated with the top k singular values and singular vectors of the data matrix.Theorem 3 identifies k through an objective-dependent minimization and uses the corresponding leading singular components.
- FNR solution: Theorem 4 formulates the corresponding optimal solution using a clean data set, errors, and the full SVD of D.The theorem explicitly introduces D0 and E as the clean data and errors, respectively.
- Comparison: The values of k selected by the two theorems can differ slightly, but this does not affect the equivalence conclusion.The paper attributes the difference to the user-specified λ and a constant term in the objective function.
C. Relaxed Constraint and Uncorrupted Data
For relaxed constraints with uncorrupted data, the paper rewrites both NNR and FNR solutions as singular-vector shrinkage operations, revealing a shared spectral framework.
- Setting: The relaxed-constraint analysis considers an uncorrupted dictionary with limited representative capacity.This section explicitly focuses on the limited-capacity setting and defines the objective functions for comparison.
- FNR solution: FNR admits a solution form based on shrinkage applied to the right singular vectors of D.The paper contrasts this form with the usual expression (DT D + γI)^−1DT D.
- NNR solution: NNR’s relaxed-constraint solution is characterized by a partition of singular components according to the threshold 1/√γ.The singular components are divided into sets with σi above or below the threshold.
- Unified form: Theorem 6 likewise expresses the optimal solution through a shrinkage-thresholding operator Pγ(Σ), with γ controlling the shrinkage.The theorem defines γ as a balanced factor and applies the operator to the diagonal entries of Σ.
D. Relax Constraint and Data Corrupted by Gaussian Noise
For relaxed constraints with Gaussian-corrupted data and limited dictionary capacity, FNR and NNR remain unified by solutions in the column space of D, although their scaling factors differ.
- NNR solution: Theorem 7 gives the NNR solution through singular components partitioned according to thresholded quantities ωi.The matrices U, Ω, and V are partitioned using whether ωi exceeds 1/√γ.
- FNR solution: Theorem 8 gives the corresponding optimal solutions using the skinny SVD of D and diagonal entries from Σr and Ωr.The cited passages identify the skinny SVD and the roles of σi and ωi.
- Comparison: Both methods obtain solutions from the column space of D, but they differ in the scaling factor used.For uncorrupted data they truncate trivial coefficients, whereas under corruption they scale self-expressive coefficients through shrinkage.
E. Exact Constraint and Data Corrupted by Laplacian Noise
For Laplacian-noise data under the exact constraint, the paper formulates nuclear- and Frobenius-norm representations with ℓ1 noise modeling and solves them using ALM. Their optimal updates are identical, yielding the same minimizer.
- The Laplacian-noise models use nuclear- or Frobenius-norm penalties with an ℓ1 error term under D = D0 + E and D0 = D0C.
- Because D0 is unknown and the ℓ1 norm lacks a closed-form solution, both formulations are solved with the augmented Lagrange multiplier method.
- The iterative solution uses singular-vector components and shrinkage-thresholding updates within the ALM procedure.
- Under ALM, the NNR and FNR update rules are identical, so they lead to the same minimizer.
F. Exact Constraint and Data Corrupted by Sample-specified Noise
For sample-specified corruption, the paper models outliers with an ℓ2,1 error penalty and compares nuclear- and Frobenius-norm formulations. Their solutions share the same form, differing only in the threshold parameter under the relaxed constraint.
- Sample-specified corruption is modeled with an ℓ2,1 norm for the error term in both NNR and FNR formulations.
- The column-wise operator Qϵ is used to compute the relevant optimal updates for the corrupted data.
- The optimal solutions for FNR and NNR have the same form under the sample-corruption analysis.
- For the relaxed constraint, the distinction between the two solutions is the value of the threshold parameter γ.
IV. DISCUSSIONS
FNR and NNR have the same solution form and therefore the same computational complexity under matched settings. Existing studies indicate that FNR can be faster, comparable, or better depending on the application and dictionary reconstruction capacity.
- FNR and NNR share the same solution form, so their computational complexities are equal under the same setting.
- O(m2n + n3) is required for SVD-based processing when inputs are clean or contaminated by Gaussian noise.
- O(tnm2 + tn3) is required when inputs contain Laplacian noise or sample-specified corruption, because SVD is obtained iteratively.
- In face recognition, FNR achieves comparable performance with over hundred times speedup, while other tasks depend on whether the dictionary exactly reconstructs the input.
V. CONCLUSION
The paper establishes theoretical connections between FNR and NNR across exact and relaxed constraints and several corruption settings. With sufficient dictionary capacity they coincide; otherwise, they are distinct solutions in the dictionary’s column space.
- Under the exact constraint, FNR is exactly NNR even with Gaussian noise, Laplacian noise, or sample-specified corruption.
- Under the relaxed constraint, FNR and NNR are two solutions on the column space of the inputs, differing only in thresholding parameter γ.
- The work connects convex nuclear-norm optimization with strictly convex Frobenius-norm optimization in matrix space.