Complexity and Applications of the Homotopy Principle for Uniformly Constrained Sparse Minimization
- PDF / 1,410,677 Bytes
- 34 Pages / 439.37 x 666.142 pts Page_size
- 95 Downloads / 142 Views
Complexity and Applications of the Homotopy Principle for Uniformly Constrained Sparse Minimization Christoph Brauer1
· Dirk A. Lorenz1
© Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract In this paper, we investigate the homotopy path related to 1 -norm minimization problems with ∞ -norm constraints. We establish an enhanced upper bound on the number of linear segments in the path and provide an example showing that the number of segments is exponential in the number of variables in the worst case. We also use the homotopy framework to develop grid independent (cross-)validation schemes for sparse linear discriminant analysis and classification that make use of the entire path. Several numerical and statistical examples illustrate the applicability of the framework. Keywords Convex optimization · Nonsmooth optimization · Homotopy methods · Primal-dual methods · Binary classification · Cross-validation Mathematics Subject Classification 65C60 · 62H30 · 90C05 · 90C25 · 65K05
1 Introduction A fundamental concept in compressed sensing [8,11,14,16] is to recover a quantity of interest x ∈ Rn from noisy measurements b ∈ Rm exploiting that b depends on x via a linear measurement process incorporated by a matrix A ∈ Rm×n . Typically, one would like to keep the number of measurements m at a relatively low level such that it holds that m < n. In the absence of noise, this setting gives rise to an underdetermined linear equation system Ax = b. However, to make the search for x feasible, it is common to exploit that x is a sparse representation of b in terms of the columns of A, i.e., the sought quantity has only a small number of non-zero components. This gives rise to the non-convex optimization optimization problem
B
Christoph Brauer [email protected] Dirk A. Lorenz [email protected]
1
TU Braunschweig, Braunschweig, Germany
123
Applied Mathematics & Optimization
min x0 s.t. Ax = b
x∈Rn
which is known to be NP-hard [22]. For that reason, one often resorts to the convex relaxation min x1 s.t. Ax = b
x∈Rn
(1)
known as basis pursuit [10] which has been shown to be tight in a large number of situations [12]. In the presence of random measurement noise η = Ax − b ∈ Rm the equality constraint in (1) is usually replaced by an appropriate penalty, or alternatively by a hard constraint, on the residual Ax − b. For the case that the noise is Gaussian, one often uses an 2 -norm penalty as in the popular LASSO approach min λx1 + 21 Ax − b22 .
x∈Rn
(2)
In its original formulation [26], the LASSO reads min 1 Ax x∈Rn 2
− b22 s.t. x1 ≤ τ
(3)
and similarly, it is possible to impose a hard constraint on the residual such that the problem becomes min x1 s.t. Ax − b2 ≤ δ .
x∈Rn
(4)
All three problems (2)–(4) have identical optimal solutions provided that the parameters λ, τ and δ are chosen appropriately. However, their relationship is data-dependent and in many applications it is not clear a priori how to choose them, for example, when the noise level is unknown. Anoth
Data Loading...
