Fast Randomized Singular Value Thresholding for Low-Rank Optimization.

Area of Science:

• Numerical Analysis
• Computer Vision
• Optimization

Background:

• Rank minimization is crucial for many machine learning tasks.
• Nuclear Norm Minimization (NNM) and Weighted NNM (WNNM) are common approaches.
• Singular Value Thresholding (SVT) is an iterative method used to solve these problems, but it is computationally expensive due to repeated Singular Value Decomposition (SVD).

Purpose of the Study:

• To develop a faster and accurate approximation method for SVT.
• To reduce the computational cost associated with SVD in iterative rank minimization algorithms.
• To maintain the convergence properties of NNM/WNNM algorithms while improving speed.

Main Methods:

• Propose Fast Randomized SVT (FRSVT) to approximate SVT.
• Avoid direct SVD computation by extracting an approximate basis from a compressed matrix.
• Utilize range propagation for faster basis extraction in each iteration.
• Analyze the theoretical relationship between SVD approximation bounds and NNM convergence.

Main Results:

• FRSVT significantly reduces computational cost compared to standard SVT.
• Theoretical analysis confirms the impact of SVD approximation on NNM.
• Empirical results demonstrate that FRSVT rarely compromises algorithm convergence.
• The method's efficiency and accuracy are validated on computer vision problems like subspace clustering and image alignment.

Conclusions:

• FRSVT offers an efficient and accurate alternative to traditional SVT for rank minimization.
• The proposed method accelerates convergence of NNM/WNNM without substantial loss of accuracy.
• FRSVT is a practical solution for computationally intensive computer vision applications requiring rank minimization.