A unified approach for projections onto the intersection of ๐“1 and ๐“2 balls or spheres

Hongying Liu, Hao Wang, Mengmeng SongarXiv 2019 · arXiv

TL;DR

Computing projections onto the intersection of $\ell_1$ and $\ell_2$ balls or spheres is a common computational bottleneck in sparse machine learning models. This paper introduces a unified mathematical framework that reduces all these projection variants to finding the root of a single piecewise quadratic function. By designing clever root-finding algorithms that avoid sorting the input data, the authors achieve highly efficient $O(n)$ practical time complexity.

What Problem Does This Paper Address?

In modern machine learning and statisticsโ€”such as Sparse Principal Component Analysis (sPCA), dictionary learning, and non-negative matrix factorizationโ€”we often need to enforce "sparsity" (making many parameters exactly zero) while keeping the overall scale of the parameters bounded. Mathematically, this is done by projecting a vector onto the intersection of an $\ell_1$ constraint (which encourages sparsity, shaped like a diamond) and an $\ell_2$ constraint (which bounds magnitude, shaped like a sphere/ball).

Depending on the specific algorithm, researchers might need to project onto the intersection of:

  1. An $\ell_1$ ball and an $\ell_2$ ball.
  2. An $\ell_1$ ball and an $\ell_2$ sphere.
  3. An $\ell_1$ sphere and an $\ell_2$ sphere.

Historically, these three scenarios have been treated as separate problems with distinct algorithms. Furthermore, the authors demonstrate that some previously accepted mathematical theorems used to solve these projections have edge-case flaws. This paper aims to fix those mathematical inconsistencies and provide a single, unified, and lightning-fast algorithm to handle all three projection types.

Methods

The authors tackle the problem using partial Lagrangian duality. Instead of dealing with the complex geometry of the intersecting shapes directly, they prove that the optimal projection for all three scenarios can be found by finding the root of a single, newly proposed auxiliary function, denoted as $\phi(\lambda)$.

They prove that $\phi(\lambda)$ is a continuous, piecewisely quadratic function. Once the root of $\phi(\lambda) = 0$ is found, the projection is easily calculated via a closed-form equation.

To find this root rapidly, they propose three algorithms:

  1. Forward Searching (FS): Sorts the input vector and searches for the root interval breakpoint by breakpoint.
  2. Semi-Smooth Newton Secant Bisection (SSNSB): An iterative method that dynamically narrows down the search interval without requiring the data to be sorted.
  3. Quadratic Approximation Secant Bisection (QASB): Similar to SSNSB, but it leverages the quadratic nature of the function to approximate the root even faster.

By avoiding the sorting step, SSNSB and QASB bypass the traditional $O(n \log n)$ computational bottleneck.

Datasets

The authors evaluated their algorithms using synthetic, randomly generated Gaussian vectors of varying dimensions ($n = 10^3, 10^5, 10^7$). They categorized the data into three types to test robustness:

  • Type I: Standard normal distribution (mean 0, standard deviation 1).
  • Type II: A mixture where 7/8 of the components have a mean of 0, and 1/8 have a mean of 0.9.
  • Type III: Components evenly partitioned into four groups with means of 0.1, 0.4, 0.7, and 1.0.

Key Insights and Ideas

  • One Function to Rule Them All: The realization that ball/ball, ball/sphere, and sphere/sphere projections all boil down to the exact same piecewise quadratic root-finding problem is an elegant mathematical unification.
  • Correcting the Record: The authors provide concrete counterexamples to a previously published theorem (by Su et al.) regarding an older auxiliary function, proving that prior methods could fail to find a root. Their new function, $\phi(\lambda)$, guarantees a unique root under the right conditions.
  • Skipping the Sort: Sorting the input vector is the traditional speed limit for projection algorithms. By using advanced secant/bisection methods that dynamically prune the search space (ignoring variables that fall outside the current bounds), the algorithms achieve $O(n)$ observed complexity without ever fully sorting the array.

Key Results

  • Massive Iteration Reduction: The proposed QASB method finds the root in just 4 to 6 iterations on average, compared to ~30+ iterations for traditional bisection methods.
  • High-Dimensional Speed: For massive vectors ($n=10^7$), QASB and SSNSB substantially outperform sorting-based Forward Search and traditional bisection in raw CPU time.
  • State-of-the-Art Performance: When tested specifically on the $\ell_1$ sphere $\cap$ $\ell_2$ sphere problem, QASB was the fastest algorithm for mixed-distribution data (Types II and III), beating out existing Alternating Projection and Newton methods.

Limitations and Future Work

While the paper is mathematically rigorous, it relies entirely on synthetic data for its numerical experiments. The authors do not test the algorithms on downstream real-world tasks (like actual Sparse PCA on genomic data or image processing pipelines).

While not explicitly stated by the authors, a natural direction for future work would be implementing these unified projection operators as custom layers in deep learning frameworks (like PyTorch or JAX) to accelerate sparseness-enforcing neural networks and dictionary learning models in practice.

Summary updated

BibTeX
@misc{liu2019unified,
  author = {Hongying Liu and Hao Wang and Mengmeng Song},
  title = {{A unified approach for projections onto the intersection of ๐“1 and ๐“2 balls or spheres}},
  year = {2019},
  eprint = {1911.03946},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1911.03946},
}
Figure