Fast low-rank approximation for covariance matrices

Mohamed Ali Belabbas; Patrick J. Wolfe

doi:10.1109/CAMSAP.2007.4498023

Fast low-rank approximation for covariance matrices

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Computing an efficient low-rank approximation of a given positive definite matrix is a ubiquitous task in statistical signal processing and numerical linear algebra. The optimal solution is well known and is given by the singular value decomposition; however, its complexity scales as the cube of the matrix dimension. Here we introduce a low-complexity alternative which approximates this optimal low-rank solution, together with a bound on its worst-case error. Our methodology also reveals a connection between the approximation of matrix products and Schur complements. We present simulation results that verify performance improvements relative to contemporary randomized algorithms for low-rank approximation.

Original language	English (US)
Title of host publication	2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMPSAP
Pages	293-296
Number of pages	4
DOIs	https://doi.org/10.1109/CAMSAP.2007.4498023
State	Published - 2007
Externally published	Yes
Event	2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMPSAP - St. Thomas, Virgin Islands, U.S. Duration: Dec 12 2007 → Dec 14 2007

Publication series

Name	2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMPSAP

Other

Other	2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMPSAP
Country/Territory	Virgin Islands, U.S.
City	St. Thomas
Period	12/12/07 → 12/14/07

ASJC Scopus subject areas

Artificial Intelligence
Computer Networks and Communications
Control and Systems Engineering
Electrical and Electronic Engineering

Online availability

10.1109/CAMSAP.2007.4498023

Library availability

Discover UIUC Full Text

Cite this

Belabbas, M. A., & Wolfe, P. J. (2007). Fast low-rank approximation for covariance matrices. In 2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMPSAP (pp. 293-296). Article 4498023 (2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMPSAP). https://doi.org/10.1109/CAMSAP.2007.4498023

Fast low-rank approximation for covariance matrices. / Belabbas, Mohamed Ali; Wolfe, Patrick J.
2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMPSAP. 2007. p. 293-296 4498023 (2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMPSAP).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Belabbas, MA & Wolfe, PJ 2007, Fast low-rank approximation for covariance matrices. in 2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMPSAP., 4498023, 2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMPSAP, pp. 293-296, 2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMPSAP, St. Thomas, Virgin Islands, U.S., 12/12/07. https://doi.org/10.1109/CAMSAP.2007.4498023

@inproceedings{a78c81384a874a74b46ba138cfe28e89,

title = "Fast low-rank approximation for covariance matrices",

abstract = "Computing an efficient low-rank approximation of a given positive definite matrix is a ubiquitous task in statistical signal processing and numerical linear algebra. The optimal solution is well known and is given by the singular value decomposition; however, its complexity scales as the cube of the matrix dimension. Here we introduce a low-complexity alternative which approximates this optimal low-rank solution, together with a bound on its worst-case error. Our methodology also reveals a connection between the approximation of matrix products and Schur complements. We present simulation results that verify performance improvements relative to contemporary randomized algorithms for low-rank approximation.",

author = "Belabbas, {Mohamed Ali} and Wolfe, {Patrick J.}",

year = "2007",

doi = "10.1109/CAMSAP.2007.4498023",

language = "English (US)",

isbn = "9781424417148",

series = "2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMPSAP",

pages = "293--296",

booktitle = "2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMPSAP",

note = "2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMPSAP ; Conference date: 12-12-2007 Through 14-12-2007",

}

TY - GEN

T1 - Fast low-rank approximation for covariance matrices

AU - Belabbas, Mohamed Ali

AU - Wolfe, Patrick J.

PY - 2007

Y1 - 2007

N2 - Computing an efficient low-rank approximation of a given positive definite matrix is a ubiquitous task in statistical signal processing and numerical linear algebra. The optimal solution is well known and is given by the singular value decomposition; however, its complexity scales as the cube of the matrix dimension. Here we introduce a low-complexity alternative which approximates this optimal low-rank solution, together with a bound on its worst-case error. Our methodology also reveals a connection between the approximation of matrix products and Schur complements. We present simulation results that verify performance improvements relative to contemporary randomized algorithms for low-rank approximation.

AB - Computing an efficient low-rank approximation of a given positive definite matrix is a ubiquitous task in statistical signal processing and numerical linear algebra. The optimal solution is well known and is given by the singular value decomposition; however, its complexity scales as the cube of the matrix dimension. Here we introduce a low-complexity alternative which approximates this optimal low-rank solution, together with a bound on its worst-case error. Our methodology also reveals a connection between the approximation of matrix products and Schur complements. We present simulation results that verify performance improvements relative to contemporary randomized algorithms for low-rank approximation.

UR - http://www.scopus.com/inward/record.url?scp=50249182305&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=50249182305&partnerID=8YFLogxK

U2 - 10.1109/CAMSAP.2007.4498023

DO - 10.1109/CAMSAP.2007.4498023

M3 - Conference contribution

AN - SCOPUS:50249182305

SN - 9781424417148

T3 - 2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMPSAP

SP - 293

EP - 296

BT - 2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMPSAP

T2 - 2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMPSAP

Y2 - 12 December 2007 through 14 December 2007

ER -

Fast low-rank approximation for covariance matrices

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this