Iterative reweighted methods for $$\ell _1-\ell _p$$ minimization

In this paper, we focus on the \(\ell _1-\ell _p\) minimization problem with \(0<p<1\), which is challenging due to the \(\ell _p\) norm being non-Lipschizian. In theory, we derive computable lower bounds for nonzero entries of the generalized first-order stationary points of \(\ell _1-\ell _p\) minimization, and hence of its local minimizers. In algorithms, based on three locally Lipschitz continuous \(\epsilon \)-approximation to \(\ell _p\) norm, we design several iterative reweighted \(\ell _1\) and \(\ell _2\) methods to solve those approximation problems. Furthermore, we show that any accumulation point of the sequence generated by these methods is a generalized first-order stationary point of \(\ell _1-\ell _p\) minimization. This result, in particular, applies to the iterative reweighted \(\ell _1\) methods based on the new Lipschitz continuous \(\epsilon \)-approximation introduced by Lu (Math Program 147(1–2):277–307, 2014), provided that the approximation parameter \(\epsilon \) is below a threshold value. Numerical results are also reported to demonstrate the efficiency of the proposed methods.     

The $$ \ell _1 $$-Analysis in Phase Retrieval with Redundant Dictionary

This article presents new results concerning the recovery of a signal from the magnitude only measurements where the signal is not sparse in an orthonormal basis but in a redundant dictionary, which we call it phase retrieval with redundant dictionary for short. To solve this phaseless problem, we analyze the \( \ell _1 \)-analysis model. Firstly we investigate the noiseless case with presenting a null space property of the measurement matrix under which the \( \ell _1 \)-analysis model provides an exact recovery. Secondly we introduce a new property (S-DRIP) of the measurement matrix. By solving the \( \ell _1 \)-analysis model, we prove that this property can guarantee a stable recovery of real signals that are nearly sparse in overcomplete dictionaries.     

Second-order orthant-based methods with enriched Hessian information for sparse $$\ell _1$$-optimization

We present a second order algorithm, based on orthantwise directions, for solving optimization problems involving the sparsity enhancing \(\ell _1\)-norm. The main idea of our method consists in modifying the descent orthantwise directions by using second order information both of the regular term and (in weak sense) of the \(\ell _1\)-norm. The weak second order information behind the \(\ell _1\)-term is incorporated via a partial Huber regularization. One of the main features of our algorithm consists in a faster identification of the active set. We also prove that a reduced version of our method is equivalent to a semismooth Newton algorithm applied to the optimality condition, under a specific choice of the algorithm parameters. We present several computational experiments to show the efficiency of our approach compared to other state-of-the-art algorithms.     

Minimization over the $$\ell _1$$ -ball using an active-set non-monotone projected gradient

Computational Optimization and Applications - The $$\ell _1$$ -ball is a nicely structured feasible set that is widely used in many fields (e.g., machine learning, statistics and signal analysis)...     

Demiquantifiers on $$\ell $$-groups

In this paper we introduce two kinds of unary operations on abelian \(\ell \)-groups with a positive distinguished element u. One of them, called demiquantifier of type I, behaves like an existential quantifier (in the sense of Cimadamore and Varela) in the negative cone, and like a universal quantifier in the positive cone. The other kind of unary operation we introduce, called demiquantifier of type II, satisfies analogous properties to demiquantifiers of type I via a translation of the negative cone, by means of the element u. These unary operations are interdefinable with the usual existential quantifiers, provided the distinguished element u is a strong unit. Moreover, if G is an abelian \(\ell \)-group, then the restriction of a demiquantifier of type II to the MV-algebra \(\Gamma (G,u)\) yields a different type of quantifier, where \(\Gamma \) is Mundici’s functor. These quantifiers are interdefinable with the usual existential quantifiers on MV-algebras given by Rutledge, provided that the involution of the corresponding MV-algebras have a fixed point.     

Data filtering for cluster analysis by $$\ell _0$$-norm regularization

A data filtering method for cluster analysis is proposed, based on minimizing a least squares function with a weighted \(\ell _0\)-norm penalty. To overcome the discontinuity of the objective function, smooth non-convex functions are employed to approximate the \(\ell _0\)-norm. The convergence of the global minimum points of the approximating problems towards global minimum points of the original problem is stated. The proposed method also exploits a suitable technique to choose the penalty parameter. Numerical results on synthetic and real data sets are finally provided, showing how some existing clustering methods can take advantages from the proposed filtering strategy.     

Algebraic geometry for $$\ell $$-groups

In this paper we focus on the algebraic geometry of the variety of \(\ell \)-groups (i.e. lattice ordered abelian groups). In particular we study the role of the introduction of constants in functional spaces and \(\ell \)-polynomial spaces, which are themselves \(\ell \)-groups, evaluated over other \(\ell \)-groups. We use different tools and techniques, with an increasing level of abstraction, to describe properties of \(\ell \)-groups, topological spaces (with the Zariski topology) and a formal logic, all linked by the underlying theme of solutions of \(\ell \)-equations.     

A generalized elastic net regularization with smoothed $$\ell _{q}$$ penalty for sparse vector recovery

In this paper, we propose an iterative algorithm for solving the generalized elastic net regularization problem with smoothed \(\ell _{q} (0<q \le 1)\) penalty for recovering sparse vectors. We prove the convergence result of the algorithm based on the algebraic method. Under certain conditions, we show that the iterative solutions converge to a local minimizer of the generalized elastic net regularization problem and we also present an error bound. Theoretical analysis and numerical results show that the proposed algorithm is promising.     

An $$\ell _{2}$$-neighborhood infeasible interior-point algorithm for linear complementarity problems

In this paper, we propose an infeasible interior-point algorithm for linear complementarity problems. In every iteration, the algorithm constructs an ellipse and searches an \(\varepsilon \)-approximate solution of the problem along the ellipsoidal approximation of the central path. The theoretical iteration-complexity of the algorithm is derived and the algorithm is proved to be polynomial with the complexity bound \(O\left(n\log \varepsilon ^{-1}\right)\) which coincides with the best known iteration bound for infeasible interior-point methods.     

Adaptive basis expansion via \ell _1 trend filtering

We propose a new approach for nonlinear regression modeling by employing basis expansion for the case where the underlying regression function has inhomogeneous smoothness. In this case, conventional nonlinear regression models tend to be over- or underfitting, where the function is more or less smoother, respectively. First, the underlying regression function is roughly approximated with a locally linear function using an \(\ell _1\) penalized method, where this procedure is executed by extending an algorithm for the fused lasso signal approximator. We then extend the fused lasso signal approximator and develop an algorithm. Next, the residuals between the locally linear function and the data are used to adaptively prepare the basis functions. Finally, we construct a nonlinear regression model with these basis functions along with the technique of a regularization method. To select the optimal values of the tuning parameters for the regularization method, we provide an explicit form of the generalized information criterion. The validity of our proposed method is then demonstrated through several numerical examples.     

Collapsing $$\omega _2$$ with semi-proper forcing

We examine the differences between three standard classes of forcing notions relative to the way they collapse the continuum. It turns out that proper and semi-proper posets behave differently in that respect from the class of posets that preserve stationary subsets of \(\omega _1\).     

Epsilon substitution for $$\textit{ID}_1$$ via cut-elimination

The \(\epsilon \)-substitution method is a technique for giving consistency proofs for theories of arithmetic. We use this technique to give a proof of the consistency of the impredicative theory \(\textit{ID}_1\) using a variant of the cut-elimination formalism introduced by Mints.     

Dimension Reduction for Finite Trees in \varvec{\ell _1}

We show that every $n$ -point tree metric admits a $(1+\varepsilon )$ -embedding into $\ell _1^{C(\varepsilon ) \log n}$ , for every $\varepsilon > 0$ , where $C(\varepsilon ) \le O\big ((\frac{1}{\varepsilon })^4 \log \frac{1}{\varepsilon })\big )$ . This matches the natural volume lower bound up to a factor depending only on $\varepsilon $ . Previously, it was unknown whether even complete binary trees on $n$ nodes could be embedded in $\ell _1^{O(\log n)}$ with $O(1)$ distortion. For complete $d$ -ary trees, our construction achieves $C(\varepsilon ) \le O\big (\frac{1}{\varepsilon ^2}\big )$ .     

Approximating the weighted maximin dispersion problem over an $$\ell _p$$-ball: SDP relaxation is misleading

Consider the problem of finding a point in a unit n-dimensional \(\ell _p\)-ball (\(p\ge 2\)) such that the minimum of the weighted Euclidean distance from given m points is maximized. We show in this paper that the recent SDP-relaxation-based approximation algorithm (Haines et al., SIAM J Optim 23(4):2264–2294, 2013) will not only provide the first theoretical approximation bound of \(\frac{1-O\left( \sqrt{ \ln (m)/n}\right) }{2}\), but also perform much better in practice, if the SDP relaxation is removed and the optimal solution of the SDP relaxation is replaced by a simple scalar matrix.     

On the Isotropic Constant of Random Polytopes with Vertices on an $$\ell _p$$-Sphere

The symmetric convex hull of random points that are independent and distributed according to the cone probability measure on the \(\ell _p\)-unit sphere of \({{\mathbb {R}}}^n\) for some \(1\le p < \infty \) is considered. We prove that these random polytopes have uniformly absolutely bounded isotropic constants with overwhelming probability. This generalizes the result for the Euclidean sphere \((p=2)\) obtained by Alonso-Gutiérrez. The proof requires several different tools including a probabilistic representation of the cone measure due to Schechtman and Zinn and moment estimates for sums of independent random variables with log-concave tails originating in a paper of Gluskin and Kwapień.     

Revisiting several problems and algorithms in continuous location with \ell _\tau norms

This paper addresses the general continuous single facility location problems in finite dimension spaces under possibly different \(\ell _\tau \) norms, \(\tau \ge 1\) , in the demand points. We analyze the difficulty of this family of problems and revisit convergence properties of some well-known algorithms. The ultimate goal is to provide a common approach to solve the family of continuous \(\ell _\tau \) ordered median location problems Nickel and Puerto (Facility location: a unified approach, 2005) in dimension \(d\) (including of course the \(\ell _\tau \) minisum or Fermat-Weber location problem for any \(\tau \ge 1\) ). We prove that this approach has a polynomial worst case complexity for monotone lambda weights and can be also applied to constrained and even non-convex problems.