Cardinality minimization: the -norm trick
Cardinality Minimization
Many problems in engineering can be cast as
where is a polytope (or, more generally, a convex set), and 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:
where is some “cost” function, and is a penalty parameter.
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 with a polyhedral (hence, convex) one, involving the -norm. This heuristic leads to replace the problem at the top with
which is an LP (provided is a polyhedron).
If is described via affine inequalities, as , 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 , such that 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
We are led to the problem
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 .
The -norm heuristic consists in replacing the top (hard) problem by
|