CUR Decomposition and Clustering Applications
Abstract
The project focuses on theory and applications of CUR decompositions, particularly focused on its utility in the area of subspace clustering. Today, much of the data obtained from a given process is high-dimensional by nature, but often times its structure is such that it essentially is low-dimensional. In such situations, matrix factorizations and low-rank approximations can be utilized to analyze the data in a faster, but still accurate way. One task is to cluster the data -- for example in facial recognition, clustering images corresponds to determining which images contain the same faces (but perhaps under different illumination conditions or positions). The CUR decomposition provides a general theory for finding similarity matrices for data which is drawn from a union of low-dimensional subspaces of the high-dimensional ambient space (motion tracking and facial recognition fall into this framework). The experimental focus of the project is to determine the best way to utilize the theory of CUR-based similarity matrices on real data, as well as to develop new algorithms for denoising, or preconditioning, matrices for further analysis based on the CUR decomposition. This analysis includes the development of new clustering algorithms which are of general utility, not only for unions of subspaces. The mathematical aims of the project are to prove error bounds for the algorithms developed when used in the presence of noise, and to determine the connections between solutions of the subspace clustering problem coming from matrix factorizations, minimization problems, and spectral clustering. The CUR decomposition ties many of these solutions together in a nice way, and will thus lead to a more rich theory as well as giving new techniques for use on real data.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jul 09, 2020
- Source ID
- W911NF2010076
Entities
People
- Keaton Hamm
Organizations
- Army Contracting Command
- United States Army
- University of Arizona