| # Cardinality minimization: the L1-norm trick LP and QP > Polyhedra | Standard forms | Polyhedral Functions | Min-Cardinality | Applications Cardinality mimimization problem The -norm heuristic Why does it work? Application: piece-wise constant fitting ## Cardinality Minimization Many problems in engineering and scientific computing can be cast as where is a polyhedron (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 (usually convex) ‘‘cost’’ function, and is a penalty parameter. Cardinality minimization is a hard problem in general. It appears in many areas, such as classification. ## 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
## Why does it work? The -norm heuristic often works well, especially if the variable is bounded. Often the variable is not bounded a priori, but its size is penalized, say by a squared -norm. Consider an optimization problem of the form where is a given integer that bounds the number of non-zeroes in the variable. Invoking the Cauchy-Schwartz inequality between and the vector with 's where is non-zero, and 's elsewhere, we obtain (with the vector with elements , ): Hence, instead of solving the difficult problem above, we can solve for a lower bound: The above problem is convex. In fact, it can be written as the QP, by adding new variables: As often, CVX allows a direct implementation of the problem, but care must be taken to use the `square_pos` function to model the squared -norm, as discussed in do's and don'ts of CVX. CVX implementation
    cvx_begin
        variable x(n)
        minimize( c'*x + (1/k^2)*square_pos(norm(x,1)) )
    cvx_end
## Applications Piece-wise constant fitting. Sparse classification.