Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

We aim to improve current methods of graph construction for use in dimensionality reduction, clustering, and label propagation. In particular, we study Cheng, et al.'s "l1-graph.'' This method simultaneously computes the graph structure and edge weights by decomposing each data point as a linear combination of the remaining samples so that the l1-norm of the coefficients is minimized. We study the graph structure and compare this model with other contemporary methods. Additionally, we'll discuss exploiting the structure of the dual polytope associated with the overcomplete data dictionary to reduce the construction complexity via "warm-starting'' several of the numerous l1-minimization problems that must be solved. We also explore theoretical justification for the l1-graph's experimental success, as well as improvements to this method through the framework of block sparsity.