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 $\ell_1$ norm, which is given by the soft-thresholding operator. In this paper we study the proximal operator of the mixed $\ell_{1,\infty}$ 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 $\ell_1$ norm case where the threshold is constant, in the mixed $\ell_{1,\infty}$ 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.
Introduction
In machine learning and signal processing, finding sparse solutions is a common objective. While the standard $\ell_1$ norm promotes entry-wise sparsity, many real-world applications like multi-task learning or biomarker discovery exhibit a "block" structure. In these scenarios, entire columns of a matrix should ideally be zero or non-zero together. This is addressed by the mixed $\ell_{1,\infty}$ norm.
Solving optimization problems involving these norms typically requires proximal algorithms. However, computing the proximal operator for the mixed $\ell_{1,\infty}$ matrix norm has historically been computationally expensive, often requiring sorting every entry in massive matrices or using slow-to-converge root-search methods. This paper introduces a new, exact iterative algorithm that significantly accelerates this process.
Methods: Generalized Soft-Thresholding
By analyzing the Karush-Kuhn-Tucker (KKT) optimality conditions, the authors discovered that the $\ell_{1,\infty}$ proximal operator is a form of generalized soft-thresholding. While each column is soft-thresholded, the thresholds are mathematically coupled by a single global value $t^*$.
The core contribution is Algorithm 2, which finds these thresholds through two primary optimizations:
- Lower Bounding: The derivation of easy-to-compute lower bounds on the norm of the optimal solution allows the algorithm to prune columns that do not require thresholding, reducing dimensionality early.
- Active Set Implementation: An "Active Set" method efficiently manages non-zero variables, further boosting performance over standard sorting-based approaches.
Experimental Results
The proposed methods were evaluated on large-scale synthetic random matrices and five high-dimensional cancer classification datasets (e.g., Carcinom, GLIOMA).
Computational Efficiency
In timing tests against state-of-the-art methods (ST, NT, QT), the "Active Set" and "Sort" implementations demonstrated speedups of 10x to 100x. For a $10,000 \times 1,000$ matrix, the new method achieved results in approximately 0.11 seconds, compared to over 15 seconds for some existing techniques.
Classification Accuracy
Beyond speed, the $\ell_{\infty,1}$ norm (the dual of $\ell_{1,\infty}$) proved to be a superior regularizer for multi-task learning. On the GLIOMA dataset, accuracy improved from 68.9% using the standard $\ell_{2,1}$ norm to 78.5% using the proposed $\ell_{\infty,1}$ approach. Similar gains were observed across all tested real-world datasets.
Conclusion
This work presents a highly efficient, exact algorithm for the $\ell_{1,\infty}$ proximal operator. By leveraging clever pruning and active set strategies, the method makes large-scale block-sparse optimization practical for high-dimensional data. Future work may extend these techniques to more general $\ell_{p,q}$ mixed norms and integrate them into deep learning optimization pipelines.
Summary updated