The fastest L1,oo prox in the west
The fastest L1,oo prox in the west
复制标题
西方最快的L1,oo prox
DOI：
10.1109/tpami.2021.3059301
复制
发表时间：
2021
影响因子：
23.6
通讯作者：
Vidal, Rene
中科院分区：
文献类型：
--
作者：
Bejar, Benjamin;Dokmanic, Ivan;Vidal, Rene
在处理非光滑目标的优化问题中，近端算子特别有趣，因为在许多实际情况下，它们导致优化算法的更新可以以封闭形式或非常有效地计算。一个著名的例子是向量范数的近邻算子，它是由软阈值算子给出的。本文研究了混合矩阵范数的近邻算子，并通过对矩阵的每一列应用众所周知的软阈值算子，证明了它可以以封闭形式计算。然而，与阈值为常数的矢量范数情况不同，在混合范数情况下，矩阵的每列可能需要不同的阈值，所有阈值都依赖于给定的矩阵。我们提出了一种计算这些阈值的一般迭代算法，以及两种有效的实现，进一步利用了最优解的混合范数易于计算的下界。在大规模合成数据和实际数据上的实验表明，所提出的方法可以比目前的方法快几个数量级。
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 vectornorm, which is given by the soft-thresholding operator. In this paper we study the proximal operator of the mixedmatrix 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 vectornorm case where the threshold is constant, in the mixednorm 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.