Sparse regularization via bidualization

The paper considers the sparse envelope function, defined as the biconjugate of the sum of a squared $$\ell _2$$ -norm function and the indicator of the set of k-sparse vectors. It is shown that both function and proximal values of the sparse envelope function can be reduced into a one-dimensional search that can be efficiently performed in linear time complexity in expectation. The sparse envelope function naturally serves as a regularizer that can handle both sparsity and grouping information in inverse problems, and can also be utilized in sparse support vector machine problems.