Differentiable sparsity measure

Question

I know that the sparsity of a matrix is the fraction of zero elements to the whole number of elements in a matrix. However, I wonder if there is a differentiable function or measure or approximation that does the same thing over a matrix: $F: R^{m\times n}\rightarrow R$, where F is a continuously differentiable sparsity function.

Answer 1

There is Hoyer's sparsity measure.

Originally $\,$defined for a vector, it can easily be extended to a matrix $$ \def\a{\alpha}\def\b{\beta} \def\q{{\sqrt{mn}}} \def\o{{\tt1}}\def\H{{\cal H}} \def\Jo{\| J \|_\o}\def\Jt{\| J \|_2} \def\Xo{\| X \|_\o}\def\Xt{\| X \|_2} \def\LR#1{\left(#1\right)} \def\BR#1{\Big(#1\Big)} \def\fracLR#1#2{\LR{\frac{#1}{#2}}} \def\p{\partial} \def\grad#1#2{\frac{\p #1}{\p #2}} \H = \frac{\Jt\cdot\Xt-\Xo}{\Jt\cdot\Xt-\Xt} $$ where $J$ is the all-ones matrix with the same dimensions as $X\,$ and $\,\|X\|_\o$ is the Manhattan norm and $\,\|X\|_2$ is the Frobenius norm.

The range of values is $\;0\le\H\le\o.\;$ The lower bound is achieved for $X=J,\,$ and the upper bound occurs when $X$ has a single non-zero element. $\H$ is undefined when $X=0.$

Although the $\|X\|_\o$ term is not differentiable, one can calculate the subgradient $$ \grad{\H}{X} = \frac{\Xo\,X-\Xt^2\,J}{\Jt\cdot\Xt^3-\Xt^3 } $$ Hoyer's function has been used in the Lagrangian for Nonnegative Matrix Factorization (NMF) to induce sparsity in the matrix factors. But as Hyperplane points out, including $\Xo$ in the Lagrangian will induce sparsity all by itself.

Answer 2

The $L^1$ norm, which is continuously differentiable almost everywhere (and even at points where it is non-differentiable, subderivatives exist) is often used to induce sparsity.

While it does not measure sparsity directly, solving constrained optimization problems like

$$ \min_x f(x) s.t. \|x\|_1 \le \beta \qquad\text{or}\qquad \min_x f(x) + \lambda\|x\|_1 $$

Typically yield sparse solutions. The most famous applications begin the LASSO (sparse linear regression) and compressed sensing.