Adapting regularized low-rank models for parallel architectures
From MaRDI portal
(Redirected from Publication:4646456)
Abstract: We introduce a reformulation of regularized low-rank recovery models to take advantage of GPU, multiple CPU, and hybridized architectures. Low-rank recovery often involves nuclear-norm minimization through iterative thresholding of singular values. These models are slow to fit and difficult to parallelize because of their dependence on computing a singular value decomposition at each iteration. Regularized low-rank recovery models also incorporate non-smooth terms to separate structured components (e.g. sparse outliers) from the low-rank component, making these problems more difficult. Using Burer-Monteiro splitting and marginalization, we develop a smooth, non-convex formulation of regularized low-rank recovery models that can be fit with first-order solvers. We develop a computable certificate of convergence for this non-convex program, and use it to establish bounds on the suboptimality of any point. Using robust principal component analysis (RPCA) as an example, we include numerical experiments showing that this approach is an order-of-magnitude faster than existing RPCA solvers on the GPU. We also show that this acceleration allows new applications for RPCA, including real-time background subtraction and MR image analysis.
Recommendations
- Robust principal component analysis: a factorization-based approach with linear complexity
- Relations among some low-rank subspace recovery models
- Efficient algorithms for robust and stable principal component pursuit problems
- Parallel matrix factorization for low-rank tensor completion
- An Unbiased Approach to Low Rank Recovery
Cites work
- Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization
- Communication-optimal parallel and sequential QR and LU factorizations
- Convex analysis and monotone operator theory in Hilbert spaces
- Fast methods for denoising matrix completion formulations, with applications to robust seismic data interpolation
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Generalized low rank models
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- scientific article; zbMATH DE number 3804766 (Why is no real title available?)
- scientific article; zbMATH DE number 964349 (Why is no real title available?)
- Level-set methods for convex optimization
- Local minima and convergence in low-rank semidefinite programming
- Local Regression and Likelihood
- Low-rank matrix completion using alternating minimization
- Matrix completion from noisy entries
- Nonsmooth optimization via quasi-Newton methods
- Nonsmooth variants of Powell's BFGS convergence theorem
- Nonsmoothness and a variable metric method
- Optimization with sparsity-inducing penalties
- Regularization and Variable Selection Via the Elastic Net
- Robust principal component analysis?
- Scalable robust matrix recovery: Frank-Wolfe meets proximal methods
- SLOPE-adaptive variable selection via convex optimization
- Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
- Sparse Approximate Solutions to Linear Systems
- Towards dense linear algebra for hybrid GPU accelerated manycore systems
- Variational Analysis
Cited in
(3)
This page was built for publication: Adapting regularized low-rank models for parallel architectures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4646456)
