1 norm Methods for Convex Cardinality Problems problems involving cardinality the 1 norm heuristic convex relaxation and convex envelope interpretations examples recent results Prof S Boyd EE364b Stanford University 1 norm heuristics for cardinality problems cardinality problems arise often but are hard to solve exactly a simple heuristic that relies on 1 norm seems to work well used for many years in many fields sparse design LASSO robust estimation in statistics support vector machine SVM in machine learning total variation reconstruction in signal processing geophysics compressed sensing new theoretical results guarantee the method works at least for a few problems Prof S Boyd EE364b Stanford University 1 Cardinality the cardinality of x Rn denoted card x is the number of nonzero components of x 0 x 0 card is separable for scalar x card x 1 x 6 0 card is quasiconcave on Rn but not Rn since card x y min card x card y holds for x y 0 but otherwise has no convexity properties arises in many problems Prof S Boyd EE364b Stanford University 2 General convex cardinality problems a convex cardinality problem is one that would be convex except for appearance of card in objective or constraints examples with C f convex convex minimum cardinality problem minimize card x subject to x C convex problem with cardinality constraint minimize f x subject to x C Prof S Boyd EE364b Stanford University card x k 3 Solving convex cardinality problems convex cardinality problem with x Rn if we fix the sparsity pattern of x i e which entries are zero nonzero we get a convex problem by solving 2n convex problems associated with all possible sparsity patterns we can solve convex cardinality problem possibly practical for n 10 not practical for n 15 or so general convex cardinality problem is NP hard can solve globally by branch and bound can work for particular problem instances with some luck in worst case reduces to checking all or many of 2n sparsity patterns Prof S Boyd EE364b Stanford University 4 Boolean LP as convex cardinality problem Boolean LP minimize cT x subject to Ax b xi 0 1 includes many famous hard problems e g 3 SAT traveling salesman can be expressed as minimize cT x subject to Ax b card x card 1 x n since card x card 1 x n xi 0 1 conclusion general convex cardinality problem is hard Prof S Boyd EE364b Stanford University 5 Sparse design minimize card x subject to x C find sparsest design vector x that satisfies a set of specifications zero values of x simplify design or correspond to components that aren t even needed examples FIR filter design zero coefficients reduce required hardware antenna array beamforming zero coefficients correspond to unneeded antenna elements truss design zero coefficients correspond to bars that are not needed wire sizing zero coefficients correspond to wires that are not needed Prof S Boyd EE364b Stanford University 6 Sparse modeling regressor selection fit vector b Rm as a linear combination of k regressors chosen from n possible regressors minimize kAx bk2 subject to card x k gives k term model chooses subset of k regressors that together best fit or explain b n choices can solve in principle by trying all k variations minimize card x subject to kAx bk2 minimize kAx bk2 card x Prof S Boyd EE364b Stanford University 7 Sparse signal reconstruction estimate signal x given noisy measurement y Ax v v N 0 2I A is known v is not prior information card x k maximum likelihood estimate x ml is solution of minimize kAx yk2 subject to card x k Prof S Boyd EE364b Stanford University 8 Estimation with outliers we have measurements yi aTi x vi wi i 1 m noises vi N 0 2 are independent only assumption on w is sparsity card w k B i wi 6 0 is set of bad measurements or outliers maximum likelihood estimate of x found by solving P T 2 minimize i6 B yi ai x subject to B k with variables x and B 1 m equivalent to Prof S Boyd EE364b Stanford University minimize ky Ax wk22 subject to card w k 9 Minimum number of violations set of convex inequalities f1 x 0 fm x 0 x C choose x to minimize the number of violated inequalities minimize card t subject to fi x ti i 1 m x C t 0 determining whether zero inequalities can be violated is easy convex feasibility problem Prof S Boyd EE364b Stanford University 10 Linear classifier with fewest errors given data x1 y1 xm ym Rn 1 1 we seek linear affine classifier y sign wT x v classification error corresponds to yi wT x v 0 to find w v that give fewest classification errors minimize card t subject to yi wT xi v ti 1 i 1 m with variables w v t we use homogeneity in w v here Prof S Boyd EE364b Stanford University 11 Smallest set of mutually infeasible inequalities given a set of mutually infeasible convex inequalities f1 x 0 fm x 0 find smallest cardinality subset of these that is infeasible certificate of infeasibility is g inf x Pm i 1 i fi x 1 0 to find smallest cardinality infeasible subset we solve minimize card subject to g 1 0 assuming some constraint qualifications Prof S Boyd EE364b Stanford University 12 Portfolio investment with linear and fixed costs we use budget B to purchase dollar amount xi 0 of stock i trading fee is fixed cost plus linear cost card x T x budget constraint is 1T x card x T x B mean return on investment is T x variance is xT x minimize investment variance risk with mean return Rmin minimize xT x subject to T x Rmin x 0 1T x card x T x B Prof S Boyd EE364b Stanford University 13 Piecewise constant fitting fit corrupted xcor by a piecewise constant signal x with k or fewer jumps problem is convex once location indices of jumps are fixed x is piecewise constant with k jumps card Dx k where 1 1 1 1 R n 1 n D 1 1 as convex cardinality problem minimize kx xcork2 subject to card Dx k Prof S Boyd EE364b Stanford University 14 Piecewise linear fitting fit xcor by a piecewise linear signal x with k or fewer kinks as convex cardinality problem minimize kx xcork2 subject to card 2x k where 2 Prof S Boyd EE364b Stanford University 1 2 1 1 2 1 1 2 1 15 1 norm heuristic replace card z with kzk1 or add regularization term kzk1 to objective 0 is parameter used to achieve desired sparsity when card appears in constraint or as term in objective more sophisticated versions use where w v are positive weights Prof S Boyd EE364b Stanford University P i wi zi or P i wi zi P i vi zi 16 Example Minimum cardinality problem start with hard minimum cardinality problem minimize card x subject to x C C convex apply heuristic to get easy 1