View in EDS PDF Full Text

Conjugate gradient acceleration of iteratively re-weighted least squares methods.

Saved in:
Bibliographic Details
Title: Conjugate gradient acceleration of iteratively re-weighted least squares methods.
Authors: Fornasier, Massimo1 massimo.fornasier@ma.tum.de, Peter, Steffen1 steffen.peter@ma.tum.de, Rauhut, Holger2 rauhut@mathc.rwth-aachen.de, Worm, Stephan3 stephanworm@gmx.de
Source: Computational Optimization & Applications. Sep2016, Vol. 65 Issue 1, p205-259. 55p.
Subjects: Least squares, Problem solving research, Cost functions, Nonconvex programming, Algorithms
Abstract: Iteratively re-weighted least squares (IRLS) is a method for solving minimization problems involving non-quadratic cost functions, perhaps non-convex and non-smooth, which however can be described as the infimum over a family of quadratic functions. This transformation suggests an algorithmic scheme that solves a sequence of quadratic problems to be tackled efficiently by tools of numerical linear algebra. Its general scope and its usually simple implementation, transforming the initial non-convex and non-smooth minimization problem into a more familiar and easily solvable quadratic optimization problem, make it a versatile algorithm. However, despite its simplicity, versatility, and elegant analysis, the complexity of IRLS strongly depends on the way the solution of the successive quadratic optimizations is addressed. For the important special case of compressed sensing and sparse recovery problems in signal processing, we investigate theoretically and numerically how accurately one needs to solve the quadratic problems by means of the conjugate gradient (CG) method in each iteration in order to guarantee convergence. The use of the CG method may significantly speed-up the numerical solution of the quadratic subproblems, in particular, when fast matrix-vector multiplication (exploiting for instance the FFT) is available for the matrix involved. In addition, we study convergence rates. Our modified IRLS method outperforms state of the art first order methods such as Iterative Hard Thresholding (IHT) or Fast Iterative Soft-Thresholding Algorithm (FISTA) in many situations, especially in large dimensions. Moreover, IRLS is often able to recover sparse vectors from fewer measurements than required for IHT and FISTA. [ABSTRACT FROM AUTHOR]
Copyright of Computational Optimization & Applications is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 117018097
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Conjugate gradient acceleration of iteratively re-weighted least squares methods.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Fornasier%2C+Massimo%22">Fornasier, Massimo</searchLink><relatesTo>1</relatesTo><i> massimo.fornasier@ma.tum.de</i><br /><searchLink fieldCode="AR" term="%22Peter%2C+Steffen%22">Peter, Steffen</searchLink><relatesTo>1</relatesTo><i> steffen.peter@ma.tum.de</i><br /><searchLink fieldCode="AR" term="%22Rauhut%2C+Holger%22">Rauhut, Holger</searchLink><relatesTo>2</relatesTo><i> rauhut@mathc.rwth-aachen.de</i><br /><searchLink fieldCode="AR" term="%22Worm%2C+Stephan%22">Worm, Stephan</searchLink><relatesTo>3</relatesTo><i> stephanworm@gmx.de</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Computational+Optimization+%26+Applications%22">Computational Optimization & Applications</searchLink>. Sep2016, Vol. 65 Issue 1, p205-259. 55p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Least+squares%22">Least squares</searchLink><br /><searchLink fieldCode="DE" term="%22Problem+solving+research%22">Problem solving research</searchLink><br /><searchLink fieldCode="DE" term="%22Cost+functions%22">Cost functions</searchLink><br /><searchLink fieldCode="DE" term="%22Nonconvex+programming%22">Nonconvex programming</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Iteratively re-weighted least squares (IRLS) is a method for solving minimization problems involving non-quadratic cost functions, perhaps non-convex and non-smooth, which however can be described as the infimum over a family of quadratic functions. This transformation suggests an algorithmic scheme that solves a sequence of quadratic problems to be tackled efficiently by tools of numerical linear algebra. Its general scope and its usually simple implementation, transforming the initial non-convex and non-smooth minimization problem into a more familiar and easily solvable quadratic optimization problem, make it a versatile algorithm. However, despite its simplicity, versatility, and elegant analysis, the complexity of IRLS strongly depends on the way the solution of the successive quadratic optimizations is addressed. For the important special case of compressed sensing and sparse recovery problems in signal processing, we investigate theoretically and numerically how accurately one needs to solve the quadratic problems by means of the conjugate gradient (CG) method in each iteration in order to guarantee convergence. The use of the CG method may significantly speed-up the numerical solution of the quadratic subproblems, in particular, when fast matrix-vector multiplication (exploiting for instance the FFT) is available for the matrix involved. In addition, we study convergence rates. Our modified IRLS method outperforms state of the art first order methods such as Iterative Hard Thresholding (IHT) or Fast Iterative Soft-Thresholding Algorithm (FISTA) in many situations, especially in large dimensions. Moreover, IRLS is often able to recover sparse vectors from fewer measurements than required for IHT and FISTA. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Computational Optimization & Applications is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=117018097
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s10589-016-9839-8
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 55
        StartPage: 205
    Subjects:
      – SubjectFull: Least squares
        Type: general
      – SubjectFull: Problem solving research
        Type: general
      – SubjectFull: Cost functions
        Type: general
      – SubjectFull: Nonconvex programming
        Type: general
      – SubjectFull: Algorithms
        Type: general
    Titles:
      – TitleFull: Conjugate gradient acceleration of iteratively re-weighted least squares methods.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Fornasier, Massimo
      – PersonEntity:
          Name:
            NameFull: Peter, Steffen
      – PersonEntity:
          Name:
            NameFull: Rauhut, Holger
      – PersonEntity:
          Name:
            NameFull: Worm, Stephan
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 09
              Text: Sep2016
              Type: published
              Y: 2016
          Identifiers:
            – Type: issn-print
              Value: 09266003
          Numbering:
            – Type: volume
              Value: 65
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: Computational Optimization & Applications
              Type: main
ResultId 1