题目：Graph Refinement via Simultaneously Low-rank and Sparse Approximation
摘要：Graph plays an important role in many fields of machine learning such as clustering. Many graph-based machine learning approaches assume that the graphs have hidden class structures. However, the class structures are unclear or noised in applications generally. Graph refinement aims to clarify the underlying class structures. In this work, we propose a novel approach, named as SLSA for graph refinement, which imposes a strong cluster structure through strict sparse and low-rank assumptions simultaneously. It results in a non-convex optimization, but the optimization problem can be efficiently solved via an alternative iteration method. We prove that the iterative method can converge to the global optimizer under a weak condition. A fast iterative algorithm is also given for sparse graphs in large scales, which costs $O(n)$ in each iteration. We also compare SLSA with other two related methods for graph refinement on both synthetic and real-world data sets. The refinement method SLSA also has many applications in machine learning. We show that it could significantly improve the performance of seven algorithms for subspace learning, nonlinear manifold dimensional reduction, or multi-view learning.