Structural conditions for projection-cost preservation via randomized matrix multiplication

Agniva Chowdhury; Jiasen Yang; Petros Drineas

doi:10.1016/j.laa.2019.03.013

Structural conditions for projection-cost preservation via randomized matrix multiplication

Agniva Chowdhury, Jiasen Yang, Petros Drineas

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

Projection-cost preservation is a low-rank approximation guarantee which ensures that the cost of any rank-k projection can be preserved using a smaller sketch of the original data matrix. We present a general structural result outlining four sufficient conditions to achieve projection-cost preservation. These conditions can be satisfied using tools from the Randomized Linear Algebra literature.

Original language	English
Pages (from-to)	144-165
Number of pages	22
Journal	Linear Algebra and Its Applications
Volume	573
DOIs	https://doi.org/10.1016/j.laa.2019.03.013
State	Published - Jul 15 2019
Externally published	Yes

Funding

We would like to thank Ilse Ipsen for many useful comments and, in particular, for deriving the proof of Lemma 6 in Section 5 . AC and PD were supported by NSF IIS-1661760 , NSF IIS-1661756 , NSF CCF-1814041 , and NSF DMS-1760353 . JY was supported by NSF IIS-1149789 and NSF IIS-1618690 . We would like to thank Ilse Ipsen for many useful comments and, in particular, for deriving the proof of Lemma 6 in Section 5. AC and PD were supported by NSF IIS-1661760, NSF IIS-1661756, NSF CCF-1814041, and NSF DMS-1760353. JY was supported by NSF IIS-1149789 and NSF IIS-1618690.

Funders	Funder number
National Science Foundation	IIS-1661760, CCF-1814041, IIS-1618690, DMS-1760353, 1760353, IIS-1149789, IIS-1661756
National Science Foundation

Keywords

Leverage scores
Matrix sketching
Projection-cost preservation
Randomized linear algebra

Access to Document

10.1016/j.laa.2019.03.013

Cite this

@article{fa59e2766b464beda717fe9b9d233abd,

title = "Structural conditions for projection-cost preservation via randomized matrix multiplication",

abstract = "Projection-cost preservation is a low-rank approximation guarantee which ensures that the cost of any rank-k projection can be preserved using a smaller sketch of the original data matrix. We present a general structural result outlining four sufficient conditions to achieve projection-cost preservation. These conditions can be satisfied using tools from the Randomized Linear Algebra literature.",

keywords = "Leverage scores, Matrix sketching, Projection-cost preservation, Randomized linear algebra",

author = "Agniva Chowdhury and Jiasen Yang and Petros Drineas",

note = "Publisher Copyright: {\textcopyright} 2019 Elsevier Inc.",

year = "2019",

month = jul,

day = "15",

doi = "10.1016/j.laa.2019.03.013",

language = "English",

volume = "573",

pages = "144--165",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier",

}

TY - JOUR

T1 - Structural conditions for projection-cost preservation via randomized matrix multiplication

AU - Chowdhury, Agniva

AU - Yang, Jiasen

AU - Drineas, Petros

PY - 2019/7/15

Y1 - 2019/7/15

N2 - Projection-cost preservation is a low-rank approximation guarantee which ensures that the cost of any rank-k projection can be preserved using a smaller sketch of the original data matrix. We present a general structural result outlining four sufficient conditions to achieve projection-cost preservation. These conditions can be satisfied using tools from the Randomized Linear Algebra literature.

AB - Projection-cost preservation is a low-rank approximation guarantee which ensures that the cost of any rank-k projection can be preserved using a smaller sketch of the original data matrix. We present a general structural result outlining four sufficient conditions to achieve projection-cost preservation. These conditions can be satisfied using tools from the Randomized Linear Algebra literature.

KW - Leverage scores

KW - Matrix sketching

KW - Projection-cost preservation

KW - Randomized linear algebra

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

U2 - 10.1016/j.laa.2019.03.013

DO - 10.1016/j.laa.2019.03.013

M3 - Article

AN - SCOPUS:85063348836

SN - 0024-3795

VL - 573

SP - 144

EP - 165

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

ER -

Structural conditions for projection-cost preservation via randomized matrix multiplication

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this