| # 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 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
| Piece-wise constant fitting. Top panel: the true signal and its noisy version. Middle: -constrained fitting, showing a good fit with the true (unknown) signal. Bottom: -constrained fitting.