regularization

A Fixed-Point Continuation Method for l_1-Regularized Minimization with Applications to Compressed Sensing

  • Elaine Hale
  • Wotao Yin
  • Yin Zhang
    • Categories Applications - Science and Engineering, Convex Optimization, Nonsmooth Optimization Tags , , , ,

    We consider solving minimization problems with $\ell_1$-regularization: $$\min \|x\|_1 + \mu f(x),$$ particularly for $f(x) = \frac{1}{2}\|Ax-b\|_M^2$ where $A \in \R^{m \times n}$ with $m < n$. Our goal is to construct efficient and robust algorithms for solving large-scale problems with dense data, and our approach is based on two powerful algorithmic ideas, operator-splitting and ... Read more

    Exact regularization of convex programs

  • Michael P. Friedlander
  • Paul Tseng
    • Categories Convex Optimization Tags , , , , , , , ,

    The regularization of a convex program is exact if all solutions of the regularized problem are also solutions of the original problem for all values of the regularization parameter below some positive threshold. For a general convex program, we show that the regularization is exact if and only if a certain selection problem has a … Read more

    Computing nonnegative tensor factorizations

  • Michael P. Friedlander
  • Kathrin Hatz
    • Categories Applications - Science and Engineering Tags , , , , , , ,

    Nonnegative tensor factorization (NTF) is a technique for computing a parts-based representation of high-dimensional data. NTF excels at exposing latent structures in datasets, and at finding good low-rank approximations to the data. We describe an approach for computing the NTF of a dataset that relies only on iterative linear-algebra techniques and that is comparable in … Read more

    On Handling Free Variables in Interior-Point Methods for Conic Linear Optimization

  • Miguel F. Anjos
  • Samuel Burer
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    We revisit a regularization technique of Meszaros for handling free variables within interior-point methods for conic linear optimization. We propose a simple computational strategy, supported by a global convergence analysis, for handling the regularization. Using test problems from benchmark suites and recent applications, we demonstrate that the modern code SDPT3 modified to incorporate the proposed … Read more

    Coordinate and Subspace Optimization Methods for Linear Least Squares with Non-Quadratic Regularization

  • Michael Elad
  • Michael Zibulevsky
  • Boaz Matalon
    • Categories Statistics, Unconstrained Optimization Tags , , , , ,

    This work addresses the problem of regularized linear least squares (RLS) with non-quadratic separable regularization. Despite being frequently deployed in many applications, the RLS problem is often hard to solve using standard iterative methods. In a recent work [10], a new iterative method called Parallel Coordinate Descent (PCD) was devised. We provide herein a convergence … Read more

    Exact regularization of linear programs

  • Michael P. Friedlander
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    We show that linear programs (LPs) admit regularizations that either contract the original (primal) solution set or leave it unchanged. Any regularization function that is convex and has compact level sets is allowed–differentiability is not required. This is an extension of the result first described by Mangasarian and Meyer (SIAM J. Control Optim., 17(6), pp. … Read more

    Regularization Using a Parameterized Trust Region Subproblem

  • Oleg Grodzevich
  • Henry Wolkowicz
    • Categories Applications - Science and Engineering, Biomedical Applications, Nonlinear Systems and Least-Squares Tags , , , ,

    We present a new method for regularization of ill-conditioned problems, such as those that arise in image restoration or mathematical processing of medical data. The method extends the traditional {\em trust-region subproblem}, \TRS, approach that makes use of the {\em L-curve} maximum curvature criterion, a strategy recently proposed to find a good regularization parameter. We … Read more

    An interior-point L1-penalty method for nonlinear optimization

  • Nicholas I. M. Gould
  • Dominique Orban
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization Tags , , ,

    A mixed interior/exterior-point method for nonlinear programming is described, that handles constraints by an L1-penalty function. A suitable decomposition of the penalty terms and embedding of the problem into a higher-dimensional setting leads to an equivalent, surprisingly regular, reformulation as a smooth penalty problem only involving inequality constraints. The resulting problem may then be tackled … Read more

    Robust regularization

  • Adrian Lewis
    • Categories Control Applications, Nonsmooth Optimization, Robust Optimization Tags , , , , , , , ,

    Given a real function on a Euclidean space, we consider its “robust regularization”: the value of this new function at any given point is the maximum value of the original function in a fixed neighbourhood of the point in question. This construction allows us to impose constraints in an optimization problem *robustly*, safeguarding a constraint … Read more