Paper Info
Title
The Fastest <inline-formula><tex-math notation="LaTeX">$\ell _{1,\infty }$</tex-math><alternatives><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>ℓ</mml:mi><mml:mrow><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mi>∞</mml:mi></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="bejar-ieq1-3059301.gif" xmlns:xlink="http://www.w3.org/1999/xlink"/></alternatives></inline-formula> Prox in the West
Abstract
Proximal operators are of particular interest in optimization problems dealing with non-smooth objectives because in many practical cases they lead to optimization algorithms whose updates can be computed in closed form or very efficiently. A well-known example is the proximal operator of the vector <inline-formula><tex-math notation="LaTeX">$\ell _1$</tex-math></inline-formula> norm, which is given by the soft-thresholding operator. In this paper we study the proximal operator of the mixed <inline-formula><tex-math notation="LaTeX">$\ell _{1,\infty }$</tex-math></inline-formula> matrix norm and show that it can be computed in closed form by applying the well-known soft-thresholding operator to each column of the matrix. However, unlike the vector <inline-formula><tex-math notation="LaTeX">$\ell _1$</tex-math></inline-formula> norm case where the threshold is constant, in the mixed <inline-formula><tex-math notation="LaTeX">$\ell _{1,\infty }$</tex-math></inline-formula> norm case each column of the matrix might require a different threshold and all thresholds depend on the given matrix. We propose a general iterative algorithm for computing these thresholds, as well as two efficient implementations that further exploit easy to compute lower bounds for the mixed norm of the optimal solution. Experiments on large-scale synthetic and real data indicate that the proposed methods can be orders of magnitude faster than state-of-the-art methods.
Year
DOI
Venue
2022
10.1109/TPAMI.2021.3059301
IEEE Transactions on Pattern Analysis and Machine Intelligence
Keywords
DocType
Volume
Proximal operator,mixed norm,block sparsity
Journal
44
Issue
ISSN
Citations 
7
0162-8828
0
PageRank 
References 
Authors
0.34
7
3
Name
Order
Citations
PageRank
Benjamin Bejar191.83
Ivan Dokmanic215522.37
rene victor valqui vidal35331260.14