A Block Lanczos with Warm Start Technique for Accelerating Nuclear Norm Minimization Algorithms
Recent years have witnessed the popularity of using rank minimization as a regularizer for various signal processing and machine learning problems. As rank minimization problems are often converted to nuclear norm minimization (NNM) problems, they have to be solved iteratively and each iteration requires computing a singular value decomposition (SVD). Therefore, their solution suffers from the high computation cost of multiple SVDs. To relieve this issue, we propose using the block Lanczos method to compute the partial SVDs, where the principal singular subspaces obtained in the previous iteration are used to start the block Lanczos procedure. To avoid the expensive reorthogonalization in the Lanczos procedure, the block Lanczos procedure is performed for only a few steps. Our block Lanczos with warm start (BLWS) technique can be adopted by different algorithms that solve NNM problems. We present numerical results on applying BLWS to Robust PCA and Matrix Completion problems. Experimental results show that our BLWS technique usually accelerates its host algorithm by at least two to three times.
Code (0)
등록된 구현이 없습니다.
Tasks
Matrix CompletionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
BOLT: Block-Orthonormal Lanczos for Trace estimation of matrix functions
Efficient matrix trace estimation is essential for scalable computation of log-determinants, matrix norms, and distributional divergences. In many large-scale applications, the matrices involved are too large to store or…
subspace methodsSGDR: Stochastic Gradient Descent with Warm Restarts
Restart techniques are common in gradient-free optimization to deal with multimodal functions. Partial warm restarts are also gaining popularity in gradient-based optimization to improve the rate of convergence in accele…
EEGElectroencephalogram (EEG)Stochastic OptimizationTurboADMM: A Structure-Exploiting Parallel Solver for Multi-Agent Trajectory Optimization
Multi-agent trajectory optimization with dense interaction networks require solving large coupled QPs at control rates, yet existing solvers fail to simultaneously exploit temporal structure, agent decomposition, and ite…
Generative flow-based warm start of the variational quantum eigensolver
Hybrid quantum-classical algorithms like the variational quantum eigensolver (VQE) show promise for quantum simulations on near-term quantum devices, but are often limited by complex objective functions and expensive opt…
Accelerating Batch Active Learning Using Continual Learning Techniques
A major problem with Active Learning (AL) is high training costs since models are typically retrained from scratch after every query round. We start by demonstrating that standard AL on neural networks with warm starting…
Active LearningContinual Learning