ℓ1-norm Methods for Convex-Cardinality Problems • problems involving cardina lity • the ℓ1-norm heuristic • convex relaxation and c onvex 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 heur istic, that relies on ℓ1-norm, seems to work well • used for ma ny years, in many fields – sparse design – LASSO, robust estimation in statistics – support vector machine (SVM) in mac hine learning – total variation re construction in signal processing, geophysics – compressed sensing • new theoretical results guarantee the method works, at least for a fe w problems Prof. S. Boyd, EE364b, Stanford University 1� Cardi nality • 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 �= 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 proble m s Prof. S. Boyd, EE364b, Stanford University 2General 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 card ina lity problem: minimize card(x) subject to x ∈ C • convex problem with cardinality constraint: minimize f(x) subject to x ∈ C, card(x) ≤ k Prof. S. Boyd, EE364b, Stanford University 3Solving convex-cardinality prob l ems convex-cardinality problem with x ∈ Rn • if we fix the sparsity pattern of x (i.e., which entries are zero/nonze r o) we get a convex problem • by solving 2n convex problem s 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 proble m 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 4Boole an LP as conve x-cardinality problem • Boolean LP: minimize cT x subject to Ax � b, xi ∈ {0, 1} includes many famous (har d) problems, e.g., 3-SAT, traveling salesman • can be expresse d 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 5Sparse 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 compone nts that aren’t even nee ded • examples: – FIR filter design (zero coefficients reduce required hardware) – antenna arr ay beamforming (zero coe fficients correspond to unneeded antenna elements) – truss design (zero c oefficients correspond to bars that are not needed) – wire sizing (zero coefficients correspond to w ires 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 �Ax − b�2 subject to card(x) ≤ k • gives k-term model • chooses subset of k regr essors that (together) best fit or explain b n • can solve (in princ iple ) by trying all choices k • variations: – minimize card(x) subject to �Ax − b�2 ≤ ǫ – minimize �Ax − b�2 + λ card(x) Prof. S. Boyd, EE364b, Stanford University 7Sparse 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 �Ax − y�2 subject to card(x) ≤ k Prof. S. Boyd, EE364b, Stanford University 8Estimation with outlie r s • 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 | � 0} is set of bad measurements or outliers wi = • maximum likelihood estimate of x found by solving minimize � i6∈B(yi − aiT x)2 subject to |B| ≤ k with variables x a nd B ⊆ {1, . . . , m} • equivalent to minimize �y − Ax − w�22 subject to card(w) ≤ k Prof. S. Boyd, EE364b, Stanford University 9Minimum numbe r of violations • set of convex ine qua lities 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 10Linear 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 corre sponds to yi(wT x + v) ≤ 0 • to find w, v that give fewest classification e r r or s: 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 o f 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 m • certificate of infeasibility is g(λ) = infx( i=1 λifi(x)) ≥ 1, λ � 0 • to find smallest cardinality infeasible subse t, we solve minimize card(λ) subject to g(λ) ≥ 1, λ � 0 (assuming some constraint