arXiv:1812.05721

Stochastic Gradient Descent for Spectral Embedding with Implicit Orthogonality Constraint

Mireille El Gheche, Giovanni Chierchia, Pascal Frossard

제출 2018-12-13

원문 초록

In this paper, we propose a scalable algorithm for spectral embedding. The latter is a standard tool for graph clustering. However, its computational bottleneck is the eigendecomposition of the graph Laplacian matrix, which prevents its application to large-scale graphs. Our contribution consists of reformulating spectral embedding so that it can be solved via stochastic optimization. The idea is to replace the orthogonality constraint with an orthogonalization matrix injected directly into the criterion. As the gradient can be computed through a Cholesky factorization, our reformulation allows us to develop an efficient algorithm based on mini-batch gradient descent. Experimental results, both on synthetic and real data, confirm the efficiency of the proposed method in term of execution speed with respect to similar existing techniques.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2607.11938v1cs.LG공통 태그 Clustering, Stochastic Optimization

데이터 과학의 수학

Mathematics of Data Science

이 책은 데이터 과학의 수학적 기초에 관한 것이다. 1. 서론 2. 고차원에서의 저주, 축복, 그리고 놀라움 3. 특이값 분해(SVD)와 주성분 분석(PCA) 4. 선형 회귀와 정규화 5. 그래프, 네트워크, 그리고 클러스터링 6. 비선형 차원 축소와 확산 맵(Diffusion Maps) 7. 랜덤 투영을 통한 선형 차원 축소 8. 데이터 과학을 위한 최적화 9. 분류 10. 심층 학습의 수학적 소개 11. 그래프 라플라시안의 대표본 극한 12. 커뮤니티 13. 측도 집중과 가우시안 분석 14. 행렬 집중 부등식 15. 압축 센싱과 희소성 16. 저계수 행렬 복원

토론

이 논문과 연결된 포럼 글이 아직 없습니다.