2010/04/08 by Ravindran Kannan, Kannan, Ravindran
Computer Science · Engineering · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Medical Image Segmentation Techniques #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.1004.1253
openalex publication_date 2010/04/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
While Spectral Methods have long been used for Principal Component Analysis, this survey focusses on work over the last 15 years with three salient features: (i) Spectral methods are useful not only for numerical problems, but also discrete optimization problems (Constraint Optimization Problems - CSP's) like the max. cut problem and similar mathematical considerations underlie both areas. (ii) Spectral methods can be extended to tensors. The theory and algorithms for tensors are not as simple/clean as for matrices, but the survey describes methods for low-rank approximation which extend to tensors. These tensor approximations help us solve Max-r-CSP's for r>2 as well as numerical tensor problems. (iii) Sampling on the fly plays a prominent role in these methods. A primary result is that for any matrix, a random submatrix of rows/columns picked with probabilities proportional to the squared lengths (of rows/columns), yields estimates of the singular values as well as an approximation to the whole matrix.