Simple and practical algorithms for $\ell_p$-norm low-rank approximation
We propose practical algorithms for entrywise $\ell_p$-norm low-rank approximation, for $p = 1$ or $p = \infty$. The proposed framework, which is non-convex and gradient-based, is easy to implement and typically attains better approximations, faster, than state of the art. From a theoretical standpoint, we show that the proposed scheme can attain $(1 + \varepsilon)$-OPT approximations. Our algorithms are not hyperparameter-free: they achieve the desiderata only assuming algorithm's hyperparameters are known a priori---or are at least approximable. I.e., our theory indicates what problem quantities need to be known, in order to get a good solution within polynomial time, and does not contradict to recent inapproximabilty results, as in [46].
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Low-Rank Matrix Approximation in the Infinity Norm
The low-rank matrix approximation problem with respect to the entry-wise $\ell_{\infty}$-norm is the following: given a matrix $M$ and a factorization rank $r$, find a matrix $X$ whose rank is at most $r$ and that minimi…
Practical sketching algorithms for low-rank matrix approximation
This paper describes a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image of the matrix, called a sketch. These methods can preserve structural properties of the in…
Weighted Low Rank Approximation for Background Estimation Problems
Classical principal component analysis (PCA) is not robust to the presence of sparse outliers in the data. The use of the $\ell_1$ norm in the Robust PCA (RPCA) method successfully eliminates the weakness of PCA in separ…
Tractable and Scalable Schatten Quasi-Norm Approximations for Rank Minimization
The Schatten quasi-norm was introduced to bridge the gap between the trace norm and rank function. However, existing algorithms are too slow or even impractical for large-scale problems. Motivated by the equivalence rela…
Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models
We study the computational limits of Low-Rank Adaptation (LoRA) for finetuning transformer-based models using fine-grained complexity theory. Our key observation is that the existence of low-rank decompositions within th…