Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices
 
research article

On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices

Cortinovis, Alice  
•
Kressner, Daniel  
•
Massei, Stefano  
May 15, 2020
Linear Algebra And Its Applications

The problem of finding a k x k submatrix of maximum volume of a matrix A is of interest in a variety of applications. For example, it yields a quasi-best low-rank approximation constructed from the rows and columns of A. We show that such a submatrix can always be chosen to be a principal submatrix not only for symmetric semidefinite matrices but also for diagonally dominant matrices. Then we analyze the low-rank approximation error returned by a greedy method for volume maximization, cross approximation with complete pivoting. Our bound for general matrices extends an existing result for symmetric semidefinite matrices and yields new error estimates for diagonally dominant matrices. In particular, for doubly diagonally dominant matrices the error is shown to remain within a modest factor of the best approximation error. We also illustrate how the application of our results to cross approximation for functions leads to new and better convergence results. (C) 2020 Elsevier Inc. All rights reserved.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.laa.2020.02.010
Web of Science ID

WOS:000521514000014

Author(s)
Cortinovis, Alice  
Kressner, Daniel  
Massei, Stefano  
Date Issued

2020-05-15

Publisher

ELSEVIER SCIENCE INC

Published in
Linear Algebra And Its Applications
Volume

593

Start page

251

End page

268

Subjects

Mathematics, Applied

•

Mathematics

•

Mathematics

•

low-rank approximation

•

cross approximation

•

volume maximization

•

diagonal dominance

•

functional approximation

•

ldu decompositions

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
ANCHP  
Available on Infoscience
April 9, 2020
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/168043
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés