Publication Type
Conference Proceeding Article
Version
acceptedVersion
Publication Date
8-2020
Abstract
This paper studies the problem of sparse residual regression, i.e., learning a linear model using a norm that favors solutions in which the residuals are sparsely distributed. This is a common problem in a wide range of computer vision applications where a linear system has a lot more equations than unknowns and we wish to find the maximum feasible set of equations by discarding unreliable ones. We show that one of the most popular solution methods, iteratively reweighted least squares (IRLS), can be significantly accelerated by the use of matrix sketching. We analyze the convergence behavior of the proposed method and show its efficiency on a range of computer vision applications. The source code for this project can be found at https://github.com/Diwata0909/Sketched IRLS.
Keywords
Sparse residual regression, L1 minimization, Randomized algorithm, Matrix sketching
Discipline
Artificial Intelligence and Robotics
Research Areas
Intelligent Systems and Optimization
Publication
ECCV 2020 16th European Conference on Computer Vision
First Page
609
Last Page
626
Identifier
doi.org/10.1007/978-3-030-58610-2_36
City or Country
UK
Citation
1
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.