Sparsity-Promoting Convex Optimization Over Simplex

Question

Say we want to find a sparse approximate minimizer to the function $f(x) : \mathbb{R}^d \to \mathbb{R}$. Then in line with the work in the field of compressed sensing, we can instead minimize $$f(x) + \lambda \|x\|_1$$ as a convex proxy/relaxation to the desired sparsity constraint on $\|x\|_0$.

But often times optimization problems are actually already restricted to an $\ell^1$ ball. For example, say we are optimizing over the space of discrete probability distributions on $d$ elements, which can be represented as \begin{align*} \text{minimize: } & f(x)\\ \text{subj. to: } & x \succeq 0\\ & \langle \boldsymbol{1}, x \rangle = 1. \end{align*} Call that problem (P). Then since any feasible solution to (P) has $\|x\|_1 = 1$ exactly, adding the objective penalty $\lambda\|x\|_1$ cannot change the optimal solution of the problem.

Question: Is there a way to add a convex penalty / constraint to (P) so that the resulting problem (P') has a sparse solution?

Answer 1

Very interesting question.

One option is to relax the cardinality regularizer to the reciprocal of an infinity norm, i.e., replace $\mathrm{card}(x)$ with $$1 / \|x\|_{\infty}.$$ This yields a non-convex problem, but one that can be solved by solving $n$ convex programs, each of dimension $n+1$.

In particular, the problem \begin{equation*} \begin{array}{ll} \mbox{minimize} & f(x) + \lambda /\|x\|_{\infty} \\ \mbox{subject to} & x \geq 0 \\ & \mathbf{1}^Tx = 1 \end{array} \end{equation*}

is equivalent to solving the following problem, for $i = 1, \ldots, n$,

\begin{equation*} \begin{array}{ll} \mbox{minimize} & f(x) + t \\ \mbox{subject to} & x_i \geq \lambda / t \\ & x \geq 0 \\ & \mathbf{1}^Tx = 1 \\ & t \geq 0 \end{array} \end{equation*}

and taking as the solution with smallest optimal value to be the solution of your original problem (here, $t \in \mathbf{R}_{+}$ is a slack variable).

In some settings, it can be shown that this relaxation exactly recovers the minimum-cardinality solution.

This relaxation is suggested in the paper "Recovery of Sparse Probability Measures via Convex Programming," which explains how to solve the relaxed problem and characterizes its solutions.