Low-rank matrix recovery arises from many engineering and applied science problems.Rank minimization is a crucial regularizer to derive a low-rank solution, which has attracted much attention.Since directly solving rank minimization is a NP-hard problem, its tightest convex surrogate has been solved instead. In literature, while the convex relaxation has proven that under some mild conditions, exact recoverability is guaranteed, i.e., the global optimal solution of the approximate problem matches the global optimal one of the original NP-hard problem, many real world problems do not often satisfy these conditions.Furthermore, in this case, the optimal solution of the convex surrogate is departing from the true solution.This is a problem caused by the approximation gap.Although many non-convex approaches have been proposed to reduce the gap, there has been no remarkable improvement.In this regard, I focus on the fact that the approaches have not exploited prior information according to the data generation procedure of each problem.In this dissertation, I leverage prior information, which naturally arises from each problem definition itself, so that performance degradation caused by the gap can be improved.The contributions of this dissertation are as follows. (1) By proposing a soft rank constraint, the rank of low-rank solution is encouraged to be close to the target rank.By virtue of this simple additional information, it properly deals with a deficient number of data regimes where the convex nuclear norm approach fails. (2) I propose a method to learn priors from data in the empirical Bayesian manner.This method demonstrates the state-of-the-art performance.Surprisingly, the proposed method outperforms the matrix completion method, which assumes the perfect knowledge of exact outlier locations, without such prior knowledge. (3) I extend the learning prior approach such that the prior information of rank and fractional outlier location is leveraged, i.e., robust matrix completion with rank prior. This further improves the success regimes of the algorithm.The proposed methods are applied to the various real computer vision problems to demonstrate their practicality (in terms of quality and efficiency).The above three contributions have shown the fundamental performance improvement. This implies that the applicability range has widened far beyond at least the vast range of applications of the existing problems, e.g., PCA and matrix completion. Namely, the practicality of the low-rank approach has improved dramatically.
실 세계에 존재하는 많은 데이터들은 고차원 공간상에 존재한다. 분야의 전문 지식 없이 고차원 데이터 분석 및 처리하는 것은 현시점에서도 굉장히 도전적인 문제이며, 최근 각광 받는 기계 학습(인공 지능)과 필요 충분 문제 볼 수 있다. 이는 다음과 같은 가정을 기반으로 한다; 1)고차원 데이터는 그 데이터를 구성하는 최소 정보량을 가지는 어떤 저차원으로의 변환이 존재하며, 2) 저차원 변환된 데이터는 고차원 공간상에 다양체(manifold)를 구성한다.이를 활용한 대표적인 접근법으로서, 저 행렬 계수 행렬 복원(low-rank matrix recovery)문제는 많은 공학과 응용과학 분야에 발생한다. 이를 해결하기 위한 시도로, 행렬 계수 최소화(rank minimization) 방법들이 제안됐으며 분야를 막론하고 큰 관심을 끌어왔다.이 행렬 계수 최소화를 직접 푸는 것은 비결정 난해(NP-hard) 문제이기 때문에, 대신 볼록 함수로 근사하여 문제를 해결해왔다. 이 방법은 어떤 온화한 조건 하에서, 근사 문제의 전역 최적해가 원래의 비결정 난해 문제의 전역 최적 해와 일치한다는 것이 증명되었으며, 이를 기반으로 많은 분야에서 성공적으로 적용됐다.그러나 여전히 실 세계의 많은 문제들은 위 조건을 만족하지 못하며, 이때 볼록 함수 근사의 최적 해는 실제 해와 멀어지게 된다.이는 행렬 계수 함수와 근사 된 볼록 함수 사이에 발생하는 근사 차이로 인해 발생하는 문제이며, 이를 해결하기 위한 많은 비 볼록 함수 기반 방법론들이 제안되었으나, 괄목할 만한 개선은 없었다.저자는 기존에 방법론들이 각 문제의 데이터 생성 절차에 따른 사전 정보를 활용하지 못한다는 것에 초점을 맞추었다.본 학위 논문에서는 이를 해결하기 위한 하나의 원리로, 각 문제의 모델링에서 발생하는 기본 정보인 사전 정보를 활용함으로서 근사 차이에서 발생한 성능 저하를 개선하려고 하였다.행렬 계수 최소화의 다음과 같은 큰 틀에서의 대안적인 방법론들을 제안하고, 성능 저하를 개선하는 것은 물론, 더 나아가 압도적인 성능 향상을 시연하였다.본 학위 논문이 기여한 부분들은 다음과 같다.(1) 부드러운 행렬 계수 제약을 제안함으로써, 명시적으로 사전 행렬 계수 정보를 이용해 최종 해의 행렬 계수가 사전 행렬 계수와 비슷하게 수렴하도록 유도하였다.이 간단한 추가 정보로 인해, 볼록 함수 방법론이 작동하지 못하는 데이터 부족 상황에서도 실제 물리 해와 비슷한 해를 생성하는 것을 보였다. (2) 사전 분포를 데이터로부터 학습해낼 수 있는 경험적 베이지안 방법론을 제안하였다.본 방법은 현재 시점에서 현존하는 알고리즘 중 가장 넓은 작동 영역을 보였다.놀랍게도, 데이터의 어떤 부분이 손상되었는지 정확히 알고 있다는 가정을 한 행렬 완성(matrix completion) 방법보다 본 방법론은 그러한 사전 정보 없이도 더 높은 성능을 보였다.(3) 앞서 제안한 사전 분포 학습 방법론을 기반으로 사전 행렬 계수 정보 및 데이터 손상 위치 사전 정보를 활용할 수 있는 간단한 방법론을 제안하였다. 이러한 추가 사전 정보가 적용 가능 문제들의 경우, 본 방법론이 응용 가능한 영역을 상당히 넓힐 수 있다는 것을 보였다.제안된 방법들은 다양한 실제 컴퓨터 비전 문제에 적용하여 그 실용성(해의 질과 효율성 측면)을 입증하려고 하였다. 위 세 가지 대표적인 기여들로 인해, 저 행렬 계수 관련된 알고리즘들의 근본적인 성능 향상을 이루었음을 보였다. 이는 응용 가능 범위가 최소 기존 알고리즘의 광대한 응용 범위보다도 더 크게 넓혔다는 의의가 있으며, 저 행렬 계수 접근법의 실용성을 비약적으로 향상 시켰다고 볼 수 있다.
