TY - JOUR

T1 - Low Rank Approximation and Decomposition of Large Matrices Using Error Correcting Codes

AU - Ubaru, Shashanka

AU - Mazumdar, Arya

AU - Saad, Yousef

N1 - Publisher Copyright:
© 1963-2012 IEEE.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 2017/9

Y1 - 2017/9

N2 - Low rank approximation is an important tool used in many applications of signal processing and machine learning. Recently, randomized sketching algorithms were proposed to effectively construct low rank approximations and obtain approximate singular value decompositions of large matrices. Similar ideas were used to solve least squares regression problems. In this paper, we show how matrices from error correcting codes can be used to find such low rank approximations and matrix decompositions, and extend the framework to linear least squares regression problems. The benefits of using these code matrices are the following. First, they are easy to generate and they reduce randomness significantly. Second, code matrices, with mild restrictions, satisfy the subspace embedding property, and have a better chance of preserving the geometry of an large subspace of vectors. Third, for parallel and distributed applications, code matrices have significant advantages over structured random matrices and Gaussian random matrices. Fourth, unlike Fourier or Hadamard transform matrices, which require sampling O(k\log k) columns for a rank- k approximation, the log factor is not necessary for certain types of code matrices. In particular, (1+ \epsilon) optimal Frobenius norm error can be achieved for a rank- k approximation with O(k/ \epsilon) samples. Fifth, fast multiplication is possible with structured code matrices, so fast approximations can be achieved for general dense input matrices. Sixth, for least squares regression problem \min \|Ax-b\|-{2} where A\in {\mathbb R} ^{n\times d} , the (1+ \epsilon) relative error approximation can be achieved with O(d/ \epsilon) samples, with high probability, when certain code matrices are used.

AB - Low rank approximation is an important tool used in many applications of signal processing and machine learning. Recently, randomized sketching algorithms were proposed to effectively construct low rank approximations and obtain approximate singular value decompositions of large matrices. Similar ideas were used to solve least squares regression problems. In this paper, we show how matrices from error correcting codes can be used to find such low rank approximations and matrix decompositions, and extend the framework to linear least squares regression problems. The benefits of using these code matrices are the following. First, they are easy to generate and they reduce randomness significantly. Second, code matrices, with mild restrictions, satisfy the subspace embedding property, and have a better chance of preserving the geometry of an large subspace of vectors. Third, for parallel and distributed applications, code matrices have significant advantages over structured random matrices and Gaussian random matrices. Fourth, unlike Fourier or Hadamard transform matrices, which require sampling O(k\log k) columns for a rank- k approximation, the log factor is not necessary for certain types of code matrices. In particular, (1+ \epsilon) optimal Frobenius norm error can be achieved for a rank- k approximation with O(k/ \epsilon) samples. Fifth, fast multiplication is possible with structured code matrices, so fast approximations can be achieved for general dense input matrices. Sixth, for least squares regression problem \min \|Ax-b\|-{2} where A\in {\mathbb R} ^{n\times d} , the (1+ \epsilon) relative error approximation can be achieved with O(d/ \epsilon) samples, with high probability, when certain code matrices are used.

KW - Error correcting codes

KW - low rank approximation

KW - matrix decomposition

KW - randomized sketching algorithms

KW - subspace embedding

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

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

U2 - 10.1109/TIT.2017.2723898

DO - 10.1109/TIT.2017.2723898

M3 - Article

AN - SCOPUS:85022174680

VL - 63

SP - 5544

EP - 5558

JO - IRE Professional Group on Information Theory

JF - IRE Professional Group on Information Theory

SN - 0018-9448

IS - 9

M1 - 7970174

ER -