Some algorithms for maximum volume and cross approximation of symmetric semidefinite matrices

Stefano Massei (Corresponding author)

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Various applications in numerical linear algebra and computer science are related to selecting the r× r submatrix of maximum volume contained in a given matrix A∈ Rn×n. We propose a new greedy algorithm of cost O(n) , for the case A symmetric positive semidefinite (SPSD) and we discuss its extension to related optimization problems such as the maximum ratio of volumes. In the second part of the paper we prove that any SPSD matrix admits a cross approximation built on a principal submatrix whose approximation error is bounded by (r+ 1) times the error of the best rank r approximation in the nuclear norm. In the spirit of recent work by Cortinovis and Kressner we derive some deterministic algorithms, which are capable to retrieve a quasi optimal cross approximation with cost O(n3).

Original languageEnglish
JournalBIT Numerical Mathematics
DOIs
Publication statusAccepted/In press - 2021

Keywords

  • Cross approximation
  • Maximum volume
  • Symmetric positive definite matrices

Fingerprint

Dive into the research topics of 'Some algorithms for maximum volume and cross approximation of symmetric semidefinite matrices'. Together they form a unique fingerprint.

Cite this