그래프에서의 행렬 완성

최근 몇 년 동안, 주어진 행렬의 일부 항목만 주어졌을 때 그 행렬의 누락된 값을 찾는 문제, 즉 행렬 완성(matrix completion) 문제가 많은 관심을 받고 있습니다. 표준 저순위(low rank) 가정 하에서 이 문제는 NP-하드이지만, Candès와 Recht는 관찰된 항목의 수가 충분히 크다면 정확하게 완화될 수 있음을 보여주었습니다. 본 연구에서는 행과 열이 커뮤니티를 형성한다고 가정하여, 행과 열에 대한 근접성 정보를 활용하는 새로운 행렬 완성 모델을 소개합니다. 이 가정은 추천 시스템과 같은 여러 실제 문제에서 타당성이 입증됩니다. 예를 들어, 사람들은 선호도를 공유하는 커뮤니티를 형성하며, 제품들은 유사한 평점을 받는 클러스터를 형성합니다. 따라서 우리의 주요 목표는 그래프로 인코딩된 행과 열의 근접성을 구조화한 저순위(low-rank) 해법을 찾는 것입니다. 우리는 다양체 학습(manifold learning)에서 아이디어를 차용하여, 이 그래프들 위에서 해법이 부드럽도록 제약 조건을 설정하였습니다. 이를 통해 행과 열의 근접성을 암시적으로 강제할 수 있습니다. 우리의 행렬 복원 모델은 볼록 비평활 최적화 문제로 공식화되며, 이를 해결하기 위한 잘 정립된 반복 알고리즘이 제공됩니다. 우리는 합성 데이터와 실제 데이터를 사용하여 제안된 행렬 완성 모델을 연구하고 평가하였으며, 결과적으로 제안된 구조화된 저순위 복원 모델이 많은 상황에서 표준적인 행렬 완성 모델보다 우수함을 보였습니다.