Sparse Approximation via Penalty Decomposition Methods
From MaRDI portal
Abstract: In this paper we consider sparse approximation problems, that is, general minimization problems with the -"norm" of a vector being a part of constraints or objective function. In particular, we first study the first-order optimality conditions for these problems. We then propose penalty decomposition (PD) methods for solving them in which a sequence of penalty subproblems are solved by a block coordinate descent (BCD) method. Under some suitable assumptions, we establish that any accumulation point of the sequence generated by the PD methods satisfies the first-order optimality conditions of the problems. Furthermore, for the problems in which the part is the only nonconvex part, we show that such an accumulation point is a local minimizer of the problems. In addition, we show that any accumulation point of the sequence generated by the BCD method is a saddle point of the penalty subproblem. Moreover, for the problems in which the part is the only nonconvex part, we establish that such an accumulation point is a local minimizer of the penalty subproblem. Finally, we test the performance of our PD methods by applying them to sparse logistic regression, sparse inverse covariance selection, and compressed sensing problems. The computational results demonstrate that our methods generally outperform the existing methods in terms of solution quality and/or speed.
Recommendations
- Optimization with sparsity-inducing penalties
- Sparse representations and approximation theory
- Penalty decomposition methods for rank minimization
- Computational approaches to non-convex, sparsity-inducing multi-penalty regularization
- Sparse approximations with interior point methods
- Sparsity in penalized empirical risk minimization
- Sparse approximation by greedy algorithms
- Sparse Regularization via Convex Analysis
- scientific article; zbMATH DE number 7750674
- Sparse Approximate Solutions to Linear Systems
Cited in
(only showing first 100 items - show all)- An active set Barzilar-Borwein algorithm for \(l_0\) regularized optimization
- Splitting augmented Lagrangian method for optimization problems with a cardinality constraint and semicontinuous variables
- A two-level simultaneous orthogonal matching pursuit algorithm for simultaneous sparse approximation problems
- Minimization of \(\ell_{1-2}\) for compressed sensing
- _0-minimization methods for image restoration problems based on wavelet frames
- A penalty decomposition approach for multi-objective cardinality-constrained optimization problems
- A Lagrange-Newton algorithm for sparse nonlinear programming
- Newton method for \(\ell_0\)-regularized optimization
- On the convergence of inexact alternate minimization in problems with \(\ell_0\) penalties
- A quadratic penalty method for hypergraph matching
- A penalty PALM method for sparse portfolio selection problems
- On solutions of sparsity constrained optimization
- The first-order necessary conditions for sparsity constrained optimization
- Tucker-3 decomposition with sparse core array using a penalty function based on Gini-index
- Iteratively weighted thresholding homotopy method for the sparse solution of underdetermined linear equations
- Sparse representations and approximation theory
- Iterative hard thresholding methods for \(l_0\) regularized convex cone programming
- Iterative reweighted minimization methods for \(l_p\) regularized unconstrained nonlinear programming
- Dynamic string‐averaging CQ‐methods for the split feasibility problem with percentage violation constraints arising in radiation therapy treatment planning
- A subgradient-based approach for finding the maximum feasible subsystem with respect to a set
- Inexact penalty decomposition methods for optimization problems with geometric constraints
- A primal dual active set with continuation algorithm for the \(\ell^0\)-regularized optimization problem
- Sparse approximate reconstruction decomposed by two optimization problems
- On nondegenerate M-stationary points for sparsity constrained nonlinear optimization
- Selection and Fusion of Categorical Predictors with L0-Type Penalties
- A unifying framework for sparsity-constrained optimization
- Weakly decomposable regularization penalties and structured sparsity
- A successive convex approximation approach for sparse solutions of convex programs
- Sparsity penalized mean-variance portfolio selection: analysis and computation
- Minimization of transformed L₁ penalty: theory, difference of convex function algorithm, and robust application in compressed sensing
- Lagrangian duality and saddle points for sparse linear programming
- Nonsmooth sparsity constrained optimization problems: optimality conditions
- Cardinality minimization, constraints, and regularization: a survey
- Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization
- A unified view of exact continuous penalties for _2-_0 minimization
- On the Solution of ℓ0-Constrained Sparse Inverse Covariance Estimation Problems
- Sparse solutions to an underdetermined system of linear equations via penalized Huber loss
- Iterative mix thresholding algorithm with continuation technique for mix sparse optimization and application
- Global optimization for sparse solution of least squares problems
- Sparse approximation based on a random overcomplete basis
- Proximal mapping for symmetric penalty and sparsity
- Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
- Efficient regularized regression with \(L_0\) penalty for variable selection and network construction
- Linear convergence of inexact descent method and inexact proximal gradient algorithms for lower-order regularization problems
- Sparse inverse covariance matrix estimation via the _0-norm with Tikhonov regularization
- An inexact proximal DC algorithm for the large-scale cardinality constrained mean-variance model in sparse portfolio selection
- Poisson image deblurring with frame-based nonconvex regularization
- Column \(\ell_{2,0}\)-norm regularized factorization model of low-rank matrix recovery and its computation
- Sparsity constrained optimization problems via disjunctive programming
- Alternating direction method of multipliers for solving dictionary learning models
- The proximal alternating iterative hard thresholding method for \(l_0\) minimization, with complexity \(\mathcal{O}(1/\sqrt{k})\)
- Malitsky-Tam forward-reflected-backward splitting method for nonconvex minimization problems
- Tractable ADMM schemes for computing KKT points and local minimizers for \(\ell_0\)-minimization problems
- Convergent inexact penalty decomposition methods for cardinality-constrained problems
- scientific article; zbMATH DE number 5259795 (Why is no real title available?)
- A difference-of-convex approach for split feasibility with applications to matrix factorizations and outlier detection
- An inexact projected regularized Newton method for fused zero-norms regularization problems
- Solution sets of three sparse optimization problems for multivariate regression
- An augmented Lagrangian proximal alternating method for sparse discrete optimization problems
- Optimality conditions for sparse nonlinear programming
- A penalty decomposition algorithm with greedy improvement for mean‐reverting portfolios with sparsity and volatility constraints
- Simultaneous factors selection and fusion of their levels in penalized logistic regression
- An inexact proximal DC algorithm with sieving strategy for rank constrained least squares semidefinite programming
- scientific article; zbMATH DE number 7370529 (Why is no real title available?)
- Complex portfolio selection via convex mixed‐integer quadratic programming: a survey
- An extended Newton-type algorithm for \(\ell_2\)-regularized sparse logistic regression and its efficiency for classifying large-scale datasets
- A continuous relaxation of the constrained \(\ell_2-\ell_0\) problem
- Sparse projection onto semi-symmetric sets with applications to sparse optimization
- The non-convex sparse problem with nonnegative constraint for signal reconstruction
- Penalized least square in sparse setting with convex penalty and non Gaussian errors
- Second-order optimality conditions for sparse optimization via Fréchet second-order subdifferential
- Optimality conditions for group sparsity constrained optimization problems with equality and inequality constraints
- A refined convergence analysis of \(\mathrm{pDCA}_{e}\) with applications to simultaneous sparse recovery and outlier detection
- Iterative Potts minimization for the recovery of signals with discontinuities from indirect measurements: the multivariate case
- An effective procedure for feature subset selection in logistic regression based on information criteria
- An efficient optimization approach for a cardinality-constrained index tracking problem
- Optimality conditions for locally Lipschitz optimization with l₀-regularization
- Adaptive projected gradient thresholding methods for constrained \(l_0\) problems
- Proximal algorithm for minimization problems in \(l_0\)-regularization for nonlinear inverse problems
- Sparse extended mean-variance-CVaR portfolios with short-selling
- A penalty decomposition method for the optimization problem with two 0-norm constraints
- Generalized sparse recovery model and its neural dynamical optimization method for compressed sensing
- An exact penalty approach for general ℓ 0 -sparse optimization problems
- Solving \(\ell_0\)-penalized problems with simple constraints via the Frank-Wolfe reduced dimension method
- Nonconvex regularizer and homotopy-based sparse optimization: convergent algorithms and applications
- Extrapolated hard thresholding algorithms with finite length for composite _0 penalized problems
- On the minimization over sparse symmetric sets: projections, optimality conditions, and algorithms
- Exact penalty decomposition method for zero-norm minimization based on MPEC formulation
- Probabilistic iterative hard thresholding for sparse learning
- Sparse Recovery via Partial Regularization: Models, Theory, and Algorithms
- Restricted Robinson constraint qualification and optimality for cardinality-constrained cone programming
- A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems
- Successive convex approximations to cardinality-constrained convex programs: a piecewise-linear DC approach
- Accelerated iterative hard thresholding algorithm for \(l_0\) regularized regression problem
- A parameterized Douglas-Rachford splitting algorithm for nonconvex optimization
- Testing Sparsity-Inducing Penalties
- Cardinality-Constrained Multi-objective Optimization: Novel Optimality Conditions and Algorithms
- Second-Order Conditions for the Existence of Augmented Lagrange Multipliers for Sparse Optimization
- Efficient Convex Optimization for Non-convex Non-smooth Image Restoration
- Penalty decomposition methods for rank minimization
This page was built for publication: Sparse Approximation via Penalty Decomposition Methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5408227)
