Locally Regularized Sparse Graph by Fast Proximal Gradient Descent
This work addresses a domain-specific issue in data clustering by improving graph-based methods for high-dimensional data, representing an incremental advancement.
The paper tackled the problem of sparse graphs ignoring geometric information in high-dimensional data clustering by proposing a Support Regularized Sparse Graph (SRSG) that encourages local smoothness, resulting in superior clustering performance on real datasets.
Sparse graphs built by sparse representation has been demonstrated to be effective in clustering high-dimensional data. Albeit the compelling empirical performance, the vanilla sparse graph ignores the geometric information of the data by performing sparse representation for each datum separately. In order to obtain a sparse graph aligned with the local geometric structure of data, we propose a novel Support Regularized Sparse Graph, abbreviated as SRSG, for data clustering. SRSG encourages local smoothness on the neighborhoods of nearby data points by a well-defined support regularization term. We propose a fast proximal gradient descent method to solve the non-convex optimization problem of SRSG with the convergence matching the Nesterov's optimal convergence rate of first-order methods on smooth and convex objective function with Lipschitz continuous gradient. Extensive experimental results on various real data sets demonstrate the superiority of SRSG over other competing clustering methods.