Cardinality minimization: the -norm trick

LP and QP> Half-Spaces | Polyhedra | Polyhedral Functions | Applications > Cardinality Minimization | Next

Cardinality mimimization problem
The -norm heuristic
Application: piece-wise constant fitting

Cardinality Minimization

where

is a polytope (or, more generally, a convex set), and mbox{bf card}(x)

denotes the cardinality (number of non-zero elements) of the vector

. Such problems seek a ‘‘sparse’’ solution, one with many zeroes in it.

A related problem is a penalized version of the above, where we seek to trade-off an objective function against cardinality:

$min_x : f(x) + lambda mbox{bf Card} (x) ~:~ x in mathbf{P},$

Cardinality minimization is a hard problem in general, but it appears in many areas.

The

-norm heuristic

The -norm heuristic consists in replacing the (non-convex) cardinality function mbox{bf Card}(x)

with a polyhedral (hence, convex) one, involving the l_1

-norm. This heuristic leads to replace the problem at the top with

is described via affine inequalities, as mathbf{P} = { x ::: Ax le b}

, with

a matrix and

a vector existing in the matlab workspace, then the following CVX snippet solves the above problem.

CVX implementation

cvx_begin
   variable x(n,1)
   minimize( norm(x,1) )
   subject to
       Ax <= b;
cvx_end

Applications

Piece-wise Constant Fitting

We observe a noisy time-series (encoded in a vector

) which is almost piece-wise constant. The goal in piece-wise constant fitting is to find what the constant levels are, as they have a biological interpretation.

Unfortunately, the signal is not exactly piece-wise constant, but a noisy version of such a signal. Thus, we seek to obtain an estimate of the signal, say hat{x}

, such that hat{x}

has as few changes in it as possible. We model the latter by minimizing the cardinality of the ‘‘difference’’ vector

, where

is the difference matrix

$min_{hat{x}} : |x - hat{x}|_2^2 ~:~ mbox{bf Card} (Dx) le K,$

where

is an estimate on the number of jumps in the signal. Here, objective function in the problem is a measure of the error between the noisy measurement and the estimate hat{x}

$min_{hat{x}} : |x - hat{x}|_2^2 ~:~ |Dx|_1 le K,$