A note on the complexity of $L _{p }$ minimization

DOI10.1007/s10107-011-0470-2zbMath1226.90076OpenAlexW2093347109MaRDI QIDQ644905

Xiaoye Jiang, Yinyu Ye, Dong-Dong Ge

Publication date: 7 November 2011

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-011-0470-2

zbMATH Keywords

global optimization interior-point method nonconvex programming sparse solution reconstruction

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Interior-point methods (90C51)

Related Items

Smoothing projected Barzilai-Borwein method for constrained non-Lipschitz optimization, A smoothing SQP framework for a class of composite $L_q$ minimization over polyhedron, Sparse solutions of linear complementarity problems, CVaR (superquantile) norm: stochastic case, Distributed Block Coordinate Descent for Minimizing Partially Separable Functions, Sparse signal recovery via non-convex optimization and overcomplete dictionaries, A joint matrix minimization approach for multi-image face recognition, A solution approach for cardinality minimization problem based on fractional programming, Accelerated Methods for NonConvex Optimization, Smoothing strategy along with conjugate gradient algorithm for signal reconstruction, An L p Norm Relaxation Approach to Positive Influence Maximization in Social Network under the Deterministic Linear Threshold Model, A nonconvex $l_1 (l_1-l_2)$ model for image restoration with impulse noise, Recent advances in mathematical programming with semi-continuous variables and cardinality constraint, The equivalence of three types of error bounds for weakly and approximately convex functions, Distributionally robust scheduling algorithms for total flow time minimization on parallel machines using norm regularizations, Linear program relaxation of sparse nonnegative recovery in compressive sensing microarrays, An improved algorithm for the $L_2-L_p$ minimization problem, Difference-of-Convex Learning: Directional Stationarity, Optimality, and Sparsity, An extrapolated iteratively reweighted $\ell_1$ method with complexity analysis, Analysis of the equivalence relationship between $l_{0}$-minimization and $l_{p}$-minimization, Sparse approximation over the cube, A smoothing method for sparse optimization over convex sets, An Augmented Lagrangian Method for Non-Lipschitz Nonconvex Programming, Block-sparse recovery of semidefinite systems and generalized null space conditions, Convergence rate analysis of proximal iteratively reweighted $\ell_1$ methods for $\ell_p$ regularization problems, A perturbation inequality for concave functions of singular values and its applications in low-rank matrix recovery, Complexity of unconstrained $L_2 - L_p$ minimization, Restricted $p$-isometry properties of partially sparse signal recovery, Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$, Minimal zero norm solutions of linear complementarity problems, The complexity results of the sparse optimization problems and reverse convex optimization problems, Relating $\ell_p$ regularization and reweighted $\ell_1$ regularization, Univariate $L^p$ and $l^p$ averaging, $0<p<1$, in polynomial time by utilization of statistical structure, A note on the smoothing quadratic regularization method for non-Lipschitz optimization, Non-convex ℓ_p regularization for sparse reconstruction of electrical impedance tomography, Unnamed Item, Unnamed Item, Spark-level sparsity and the $\ell_1$ tail minimization, The nonnegative zero-norm minimization under generalized $Z$-matrix measurement, A reweighted nuclear norm minimization algorithm for low rank matrix recovery, Restricted $p$-isometry property and its application for nonconvex compressive sensing, Smoothing methods for nonsmooth, nonconvex minimization, Linear convergence of inexact descent method and inexact proximal gradient algorithms for lower-order regularization problems, Tractable ADMM schemes for computing KKT points and local minimizers for $\ell_0$-minimization problems, On finding a generalized lowest rank solution to a linear semi-definite feasibility problem, Least Sparsity of $p$-Norm Based Optimization Problems with $p>1$, Spherical Designs and Nonconvex Minimization for Recovery of Sparse Signals on the Sphere, New regularization method and iteratively reweighted algorithm for sparse vector recovery, A gradient descent based algorithm for $\ell_p$ minimization, Nonconvex sorted $\ell_1$ minimization for sparse approximation, On sparse beamformer design with reverberation, Convergence of the reweighted $\ell_1$ minimization algorithm for $\ell_2-\ell_p$ minimization, Successive convex approximations to cardinality-constrained convex programs: a piecewise-linear DC approach, Queue length asymptotics for the multiple-server queue with heavy-tailed Weibull service times, The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential, Selection and Fusion of Categorical Predictors with L0-Type Penalties, Sparse Sensor Placement Optimization for Classification, $L_p$-norm Regularization Algorithms for Optimization Over Permutation Matrices, Complexity Results and Effective Algorithms for Worst-Case Linear Optimization Under Uncertainties, Sparse Solutions by a Quadratically Constrained ℓq (0 <q< 1) Minimization Model, EXACT LOW-RANK MATRIX RECOVERY VIA NONCONVEX SCHATTEN p-MINIMIZATION, Selected Open Problems in Discrete Geometry and Optimization, An interior point method for $L_{1 / 2}$-SVM and application to feature selection in classification, Large deviations for stochastic fluid networks with Weibullian tails, On the entropy of couplings, Sparse Solutions of a Class of Constrained Optimization Problems, Rank-one and sparse matrix decomposition for dynamic MRI, Entropy function-based algorithms for solving a class of nonconvex minimization problems, Two pairs of families of polyhedral norms versus $\ell _p$-norms: proximity and applications in optimization

Cites Work

A note on the complexity of \(L _{p }\) minimization