Approximation, reformulation and convex techniques for cardinality optimization problems

The cardinality minimization problem (CMP) is finding a vector with minimum cardinality, which satisfies certain linear (or non-linear) constraints. This problem is closely related to the so-called compressive sensing problems. In this paper we survey and study different approximation, reformulation and convex relaxations for both cardinality constraint problems and cardinality minimization problems, and discuss how to add a penalty function to the objective in order to get a reformulation/approximation model of the original problems, instead of simply dropping the rank constraint. By reformulation techniques, under some mild condition we may either transform the problem to a mixed integer linear program (MILP) or the so-called bilevel SDP problems. We also point out that a continuous approximation of cardinality functions can enable us to apply majorization method to extract proper weights for the (re)weighted l1 algorithms.