Projection onto the l_{∞,1} mixed norm ball

Description

This page focuses on our root-finding based algorithm for computing projections onto the l_{infty,1}-ball. This method proposes an initial guess of the root of a search function that can be obtained with low computational cost. We consider an additional pruning strategy to reduce operations. 

Our basic version used a Steffensen root-search algorithm and was introduced in the paper G. Chau, B. Wohlberg and P. Rodriguez, “Fast Projection onto the l∞,1 Mixed Norm Ball using Steffensen Root Search,” presented at the 2018 International Conference on Acoustics, Speech and Signal Processing. 

We have developed an improved version, which trough a mathematical analysis of the search function introduces an approximated Newton method.

The code for both implementations is provided in this page.

Matlab Code

[Download Code]

The matlab code provides a usage example in the main.m file. The core files in the package are proj_newton_pruned and proj_steffensen_pruned 

[ X,tau_opt,iter ] = proj_steffensen_pruned( B, tau, gamma_0 )

[ X,tau_opt,iter ] = proj_newton_pruned( B, tau, gamma_0 )

B is the input matrix, tau is the constraint parameter and gamma_0 is an optional initial point for the root search algorithm.