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

DOI10.1007/s10107-011-0470-2zbMath1226.90076MaRDI 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

90C26: Nonconvex programming, global optimization

90C51: Interior-point methods

Related Items

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

Cites Work

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