Matrix nearness problems with off-block-diagonal rank constraints

Lujing Chen*, Frederik H. Pedersen, Martin S. Andersen

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

16 Downloads (Pure)

Abstract

This paper explores the problem of finding a rank-structured approximation to a given Hermitian positive definite matrix. We first study a fundamental matrix nearness problem which seeks an approximation whose off-diagonal block must have low rank. Our investigation focuses on three objective functions: the spectral norm, Frobenius divergence, and log-determinant divergence. We derive closed-form solutions for the fundamental nearness problem, extending our analysis to include problems with a range restriction on the off-diagonal block. Building upon these results, we propose a practical, scalable algorithm to compute a positive definite hierarchical off-diagonal low-rank approximation to a Hermitian positive definite matrix. Through numerical experiments, we explore the use of our approximation as a general-purpose preconditioner for the conjugate gradient method. Our results demonstrate that the log-determinant divergence-based approximation exhibits good performance across a diverse set of test problems.

Original languageEnglish
JournalLinear Algebra and Its Applications
Number of pages37
ISSN0024-3795
DOIs
Publication statusAccepted/In press - 2024

Keywords

  • Hierarchical matrices
  • Iterative methods
  • Low-rank matrices
  • Matrix nearness problems
  • Positive definite matrices

Fingerprint

Dive into the research topics of 'Matrix nearness problems with off-block-diagonal rank constraints'. Together they form a unique fingerprint.

Cite this