2017/11/01 by Shashanka Ubaru, Yousef Saad, Ubaru, Shashanka +1 · 1 citation
Computer Science · Engineering · #15A18 #15A69 #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and ELM #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1711.00439
openalex publication_date 2017/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper addresses matrix approximation problems for matrices that are\nlarge, sparse and/or that are representations of large graphs. To tackle these\nproblems, we consider algorithms that are based primarily on coarsening\ntechniques, possibly combined with random sampling. A multilevel coarsening\ntechnique is proposed which utilizes a hypergraph associated with the data\nmatrix and a graph coarsening strategy based on column matching. Theoretical\nresults are established that characterize the quality of the dimension\nreduction achieved by a coarsening step, when a proper column matching strategy\nis employed. We consider a number of standard applications of this technique as\nwell as a few new ones. Among the standard applications we first consider the\nproblem of computing the partial SVD for which a combination of sampling and\ncoarsening yields significantly improved SVD results relative to sampling\nalone. We also consider the Column subset selection problem, a popular low rank\napproximation method used in data related applications, and show how multilevel\ncoarsening can be adapted for this problem. Similarly, we consider the problem\nof graph sparsification and show how coarsening techniques can be employed to\nsolve it. Numerical experiments illustrate the performances of the methods in\nvarious applications.\n