Novel Fast Algorithms For Low Rank Matrix Approximation

<p>Recent advances in matrix approximation have seen an emphasis on randomization techniques in which the goal was to create a sketch of an input matrix. This sketch, a random submatrix of an input matrix, having much fewer rows or columns, still preserves its relevant features. In one of such techniques random projections approximate the range of an input matrix. Dimension reduction transforms are obtained by means of multiplication of an input matrix by one or more matrices which can be orthogonal, random, and allowing fast multiplication by a vector. The Subsampled Randomized Hadamard Transform (SRHT) is the most popular among transforms. An m x n matrix can be multiplied by an n x l SRHT matrix in O(mn log l) arithmetic operations where typically l << min(m, n). This dissertation introduces an alternative, which we call the Subsampled Randomized Approximate Hadamard Transform (SRAHT), and for which complexity of multiplication by an input matrix decreases to O( (2n + l log n) m ) operations. We also prove that our sublinear cost variants of a popular subspace sampling algorithm output accurate low rank approximation (hereafter LRA) of a large class of input. Finally, we introduce new sublinear algorithms for the CUR LRA matrix factorization which consists of a column subset C and a row subset R of an input matrix and a connector matrix U. We prove that these CUR algorithms provide close LRA with a high probability on a random input matrix admitting LRA.</p>

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Computer Science

Grantor

The Graduate School and University Center of The City University of New York

Year dc:date.available

2020

Author dc:creator

• Svadlenka, John T

Advisor dc:contributor.advisor

• Victor Pan

Committee members dc:contributor.committeemember

• Feng Gu
• Liang Zhao
• Bo Yuan

• Theory and Algorithms
• Low rank matrix approximation
• matrix sketch
• random projection
• dimension reduction
• SRHT
• SRAHT

Repository record dc:identifier

https://academicworks.cuny.edu/gc_etds/3834

OAI identifier oai:identifier

oai:academicworks.cuny.edu:gc_etds-4880