Exact solution path algorithm of Generalized Lasso for nonfull rank case

Abstract

In this thesis, we propose an exact solution path algorithm of Generalized Lasso when the design matrix $X$ is non-full rank.

\newline

In the case of non-full rank, the conventional optimization algorithms find approximate solution paths because they obtain the solution path by adding a small amount of ridge term.

However, if it is important to obtain an exact solution by reflecting what is clearly revealed, such as network information between genes, in the penalty matrix $D$, it can not be solved by conventional methods. In addition, depending on the amount of the ridge term ($\epsilon$), the results of the solution change very sensitively.

So, we develop a solution path algorithm which solves the dual problem of Generalized Lasso to give an exact solution path. And we propose how to check the uniqueness of a given solution for a fixed $\lambda$ and the method of the characterization of solutions set if the solution is not unique.

본 학위 논문에서는 설계 행렬 X가 full rank가 아닐 때 Generalized Lasso 문제의 정확한 경로 해를 찾는 알고리즘을 제안한다.

기존의 Generalized Lasso 문제를 해결하는 알고리즘은 적은 양의 ridge term을 더하여 설계 행렬 X를 full rank로 바꿈으로써 경로 해를 구하기 때문에 정확한 경로 해가 아닌 개략화된 경로 해이다.

그러나 유전자간의 네트워크 정보와 같이 명확하게 밝혀진 것을 벌점화 행렬에 반영하여 정확한 해를 구하는 것이 중요한 경우는 기존 방법대로 해결할 수 없다. 뿐만 아니라 ridge term의 크기($\epsilon$)에 따라 해의 결과가 굉장히 민감하게 변하기 때문에 정확하게 해를 구하는 것이 중요하다.

따라서 본 학위 논문에서는 primal problem을 쌍대문제로 바꿔 쌍대 변수의 경로해를 구함으로써 정확한 primal solution path를 구하는 방법을 제안한다. 뿐만 아니라 고정된 lambda에 대해서 해가 주어졌을 때 그 해가 유일한 해인지를 확인하는 방법을 제안하고 만약 유일하지 않다면 모든 해를 특성화하는 방법에 대해서 제안한다.