An analysis of sketched IRLS for accelerated sparse residual regression

• Main Authors: IWATA, Daichi, WAECHTER, Michael, LIN, Wen-yan, MATSUSHITA, Yasuyuki
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2020
• Subjects: Sparse residual regression; L1 minimization; Randomized algorithm; Matrix sketching; Artificial Intelligence and Robotics
• Online Access: https://ink.library.smu.edu.sg/sis_research/6110; https://ink.library.smu.edu.sg/context/sis_research/article/7113/viewcontent/123570596.pdf
• Institution: Singapore Management University

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.