Graph Sparsification by Universal Greedy Algorithms

发布时间：2021-04-15 来源：赢咖3 浏览次数：

Speaker:	谢家新	DateTime:	2021年4月23号（周五）下午3:00-4:00
Brief Introduction to Speaker: 谢家新，北京航空航天大学副教授。		Place:	腾讯会议（会议号请联系张雄军老师索取）
Abstract:Graph sparsification is to approximate an arbitrary graph by a sparse graph and is useful in many applications, such as simplification of social networks, least squares problems, numerical solution of symmetric positive definite linear systems and etc. In this talk, inspired by the well-known sparse signal recovery algorithm called orthogonal matching pursuit (OMP), we introduce a deterministic, greedy edge selection algorithm called universal greedy approach (UGA) for graph sparsification. The convergent results as well as the computational complexity are discussed. Extensive experimental results, including applications to graph clustering and least squares regression, show the effectiveness of proposed approaches.