ALORA: Affine Low-Rank Approximations

Alan Ayala 1 Xavier Claeys 1 Laura Grigori 1
1 ALPINES - Algorithms and parallel tools for integrated numerical simulations
INSMI - Institut National des Sciences Mathématiques et de leurs Interactions, Inria de Paris, LJLL - Laboratoire Jacques-Louis Lions
Abstract : In this paper we present the concept of affine low-rank approximation for an m x n matrix, consisting in fitting its columns into an affine subspace of dimension at most k << min(m, n). We show that the optimal affine approximation can be obtained by applying an orthogonal projection to the matrix before constructing its best approximation. Moreover, we present the algorithm ALORA that constructs an affine approximation by slightly modifying the application of any lowrank approximation method. We focus on approximations created with the classical QRCP and subspace iteration algorithms. For the former, we present a detailed analysis of the existing pivoting techniques and furthermore, we provide a bound for the error when an arbitrary pivoting technique is used. For the case of subspace iteration, we prove a result on the convergence of singular vectors, showing a bound that is in agreement with the one for convergence of singular values proved recently. Finally, we present numerical experiences using challenging matrices taken from different fields, showing good performance and validating the theoretical framework.
Complete list of metadatas

Cited literature [39 references]  Display  Hide  Download

https://hal.inria.fr/hal-01762882
Contributor : Ayala Alan <>
Submitted on : Tuesday, April 10, 2018 - 2:46:11 PM
Last modification on : Friday, September 20, 2019 - 4:34:04 PM

File

RR-9170.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01762882, version 1

Citation

Alan Ayala, Xavier Claeys, Laura Grigori. ALORA: Affine Low-Rank Approximations. Journal of Scientific Computing, Springer Verlag, 2018. ⟨hal-01762882⟩

Share

Metrics

Record views

515

Files downloads

339