저랭크 근사

수치해석 통계 마지막 수정: 2026-08-27 04:18:40

1. 개요[편집]

저랭크 근사 Low-Rank Approximation
문제	$\min_{\mathrm{rank}(B)\le r}\\|A-B\\|$
최적해	절단 SVD — 모든 유니터리 불변 노름에서
저장량	$mn \to r(m+n)$
주요 계산법	절단 SVD · 랜덤화 스케치 · CUR/교차근사 · 크리로프
깨지는 곳	가중 노름 · 구조 제약 · 비음수 · 텐서
단골 응용	POD/ROM · H-행렬 · 행렬 완성 · LoRA

데이터는 크고 정보는 작다. 그 격차를 돈으로 바꾸는 것이 이 바닥의 전부다.

저랭크 근사는 $m\times n$ 행렬 $A$ 를 계수(rank)가 $r$ 이하인 행렬 $B = XY^{\mathsf T}$ ( $X\in\mathbb R^{m\times r}$ , $Y\in\mathbb R^{n\times r}$ )로 바꿔치기해, 저장량을 $mn$ 에서 $r(m+n)$ 으로, 행렬-벡터 곱 비용을 $O(mn)$ 에서 $O(r(m+n))$ 으로 줄이는 근사 기법의 총칭이다. 특이값 분해 문서가 분해 자체를, 절단 특이값 분해 문서가 절단을 정규화로 쓰는 이야기를 다루므로, 이 문서는 “근사가 왜 가능하고, 원소를 다 보지 않고 어떻게 만드느냐” 에 집중한다.

이 주제가 수치해석·기계학습·양자정보에서 동시에 튀어나오는 이유는 단순하다.¹ 큰 행렬은 대체로 큰 정보를 담고 있지 않다. 매끄러운 커널에서 나온 경계요소법 행렬, 상관이 강한 적합직교분해의 스냅숏 행렬, 서로 비슷한 사용자들의 평점 행렬 — 죄다 특이값이 몇십 개 지나면 바닥으로 떨어진다. 그 사실을 이용하지 않는 코드는 없는 정보를 계산하느라 전기를 태우는 셈이다.

2. 랭크는 정수가 아니라 스펙트럼이다[편집]

실무에서 “랭크가 $r$ 이다”는 문장은 거의 항상 거짓이다. 반올림 오차와 측정 잡음이 섞인 행렬의 대수적 랭크는 십중팔구 $\min(m,n)$ 이다. 쓸모 있는 것은 수치 랭크( $\varepsilon$ -랭크)다.

r_\varepsilon(A) \;=\; \min\{\,k \;:\; \sigma_{k+1} \le \varepsilon \sigma_1 \,\}

즉 저랭크성은 성질이 아니라 특이값 감쇠 속도의 문제이고, 그 감쇠를 결정하는 것은 알고리즘이 아니라 문제 자체다. 대표적인 발생 원인 세 가지만 알아 두면 감이 잡힌다.

매끄러운 커널. $A_{ij} = g(x_i, y_j)$ 이고 $g$ 가 두 점 뭉치가 서로 떨어져 있는 영역에서 해석적이면, 체비쇼프 전개를 잘라 낸 것이 그대로 저랭크 근사가 되어 $\sigma_k$ 가 지수적으로 감소한다. 고속 다중극자법과 계층 행렬이 서 있는 지반이 정확히 이것이다.
변위 구조. $A$ 가 실베스터 방정식 $MA - AN =$ (저랭크)를 만족하면 특이값이 졸로타레프 문제의 해에 의해 지수적으로 눌린다. 코시·한켈·리아푸노프 방정식의 해 행렬이 왜 저랭크 인수로 저장되는지가 여기서 나온다.
상관. 데이터가 저차원 부분공간 근처에 몰려 있으면 공분산의 스펙트럼이 떨어진다. 주성분 분석의 전제 그 자체다.

거꾸로 감쇠가 없는 문제도 많다. 이류가 지배하는 유동의 스냅숏 행렬, 이동하는 충격파, 고주파 산란은 특이값이 거의 안 떨어져서 랭크 300짜리 근사를 만들어 봐야 이득이 없다. 이건 방법의 실패가 아니라 정직한 보고다.

3. 최적성 — 그리고 그 대가[편집]

에카르트-영-미르스키 정리는 이 분야의 헌법이다. 절단 SVD $A_r=\sum_{i\le r}\sigma_i u_iv_i^{\mathsf T}$ 가 모든 유니터리 불변 노름에서 동시에 최적이고, 오차는 잘라낸 특이값이 그대로 말해 준다.

\min_{\mathrm{rank}(B)\le r}\|A-B\|_2 = \sigma_{r+1}, \qquad \min_{\mathrm{rank}(B)\le r}\|A-B\|_F = \Bigl(\textstyle\sum_{i>r}\sigma_i^2\Bigr)^{1/2}

“하나의 해가 서로 다른 노름을 동시에 최소화한다”는 것은 최적화에서 극히 드문 사치다. 그런데 이 사치에는 두 가지 청구서가 붙는다.

첫째, 비용. 전체 SVD는 $O(mn\min(m,n))$ 이다. $10^6\times10^6$ 행렬에서 상위 20개를 원하는데 전체를 분해하는 것은 불가능이다.

둘째, 접근. SVD는 $A$ 의 모든 원소를 요구한다. 원소 하나 계산하는 데 적분 하나를 해야 하는 경계요소법 행렬이나, 애초에 $10^{-3}$ 만 관측된 평점 행렬에서는 이 요구 자체가 문제다.

그리고 정리가 아예 성립하지 않는 곳이 있다. 원소마다 다른 가중치를 준 가중 프로베니우스 노름의 저랭크 근사는 NP-난해이고, 한켈·퇴플리츠 같은 구조를 유지하라는 제약이나 비음수 제약(NMF)이 붙어도 마찬가지다. 이때는 교대 최소화·리프트 앤 프로젝트 같은 국소 최적화로 내려가며, “최적성 정리가 있는 문제”의 안온함은 사라진다.² 아래 절들은 전부 이 세 가지 청구서에 대한 응답이다.

4. 원소를 다 안 보는 방법 — CUR과 교차근사[편집]

$A$ 의 실제 열 $r$ 개와 행 $r$ 개만 뽑아 근사를 만드는 방식이 CUR 분해(또는 골격/skeleton 근사)다. 열 인덱스 $J$ , 행 인덱스 $I$ 를 골라

A \;\approx\; C\,U\,R, \qquad C = A(:,J),\quad R = A(I,:),\quad U = \bigl(A(I,J)\bigr)^{+}

로 둔다. 핵심은 교차점 부분행렬 $A(I,J)$ 를 어떻게 고르느냐이고, 답은 최대 부피 원리다. 고레이노프-티르티시니코프(2001)는 $r\times r$ 부분행렬 중 행렬식의 절댓값이 최대인 것을 고르면 최대 노름에서

\|A - CUR\|_{\max} \;\le\; (r+1)\,\sigma_{r+1}(A)

가 성립함을 보였다. 최적값의 $(r+1)$ 배 — SVD보다 나쁘지만, 행렬 원소를 $O(r(m+n))$ 개만 읽고 얻은 결과라는 점을 생각하면 놀라운 가격이다. 최대 부피 부분행렬 찾기 자체는 NP-난해라 실무에서는 탐욕적 대안을 쓴다.

적응 교차근사(ACA). 잔차의 가장 큰 원소를 피벗으로 잡아 십자(행 하나 + 열 하나)를 뜯어내고 랭크-1을 빼는 것을 반복한다. 사실상 완전 피벗 LU 분해를 잔차에 굴리는 것이며, 원소를 요구할 때만 계산하는 블랙박스 접근이 가능하다. 경계요소법과 계층 행렬 라이브러리의 기본 엔진이다.
보간 분해(ID). $A \approx A(:,J)\,X$ 형태로, $X$ 의 원소 크기를 상수로 묶는 강한 랭크 노출 QR(구-아이젠슈타트 1996)이 존재를 보장한다. 근사의 인수 하나가 원본의 실제 열이라 수치적 성질이 안정적이다.
레버리지 스코어 표본추출. 상위 특이벡터의 행 노름 제곱에 비례해 열을 뽑는 확률적 선택. 확률적 오차 보증이 붙는 대신 레버리지 스코어 추정이 또 하나의 숙제다.

CUR이 SVD를 이기는 진짜 지점은 오차가 아니라 해석 가능성과 구조 보존이다. 특이벡터는 모든 유전자·모든 격자점의 밀집 선형결합이라 “이게 무슨 뜻이냐”는 질문에 답이 없지만, CUR의 인수는 “이 유전자 12개, 이 환자 9명”이다. 희소행렬에 SVD를 걸면 인수가 꽉 차 버리는 반면 $C$ 와 $R$ 은 원본의 희소성을 그대로 물려받는다는 점도 크다.

5. 무작위 스케치[편집]

$A$ 에 무작위 행렬을 곱해 치역을 먼저 잡고 작은 문제로 내려오는 접근이 랜덤화 SVD 이며, 오늘날 대규모 저랭크 근사의 사실상 표준이다. 오차가 최적값의 상수배 안에 들어오고, 스펙트럼 감쇠가 느리면 멱반복 $q$ 를 한두 번 끼워 감쇠를 인위적으로 가파르게 만든다. 자세한 오차 이론·과표본 $p$ ·통과 횟수 논의는 해당 문서에 있으니 여기서는 반복하지 않는다.

기억해 둘 대비만 적어 둔다. 랜덤화는 행렬을 곱할 수만 있으면 되고, CUR/ACA는 원소를 하나씩 꺼낼 수만 있으면 된다. 어떤 접근이 가능한지가 알고리즘을 고른다. 정확한 특이값 자릿수가 필요하면 란초스 알고리즘 계열이 여전히 우위다.

6. 관측이 구멍 난 경우 — 행렬 완성[편집]

원소의 극히 일부 $\Omega$ 만 관측했을 때 저랭크라는 가정만으로 나머지를 복원하는 문제가 행렬 완성이다. 넷플릭스 프라이즈가 유명하게 만들었다. 랭크 최소화는 비볼록이지만, 랭크의 볼록 완화인 핵노름(특이값의 합)을 쓰면 볼록 최적화 문제가 된다.

\min_X \ \|X\|_* \quad \text{s.t.} \quad X_{ij} = A_{ij}\ \ \forall (i,j)\in\Omega

핵노름은 스펙트럼 노름 단위공 위에서 랭크 함수의 볼록 포락선이라는 의미에서 ” $\ell_1$ 이 $\ell_0$ 에 대해 하는 일”을 랭크에 대해 한다. 압축센싱의 논리를 특이값 벡터에 옮긴 것이라고 봐도 좋고, 실제로 반정부호 계획법으로 표현된다. 특이값 연화 임계화(SVT)를 반복하는 근접 경사법이 표준 알고리즘이다.

여기에는 저랭크성만으로는 안 되는 조건이 하나 더 붙는다. $A = e_1e_1^{\mathsf T}$ 는 완벽한 랭크 1이지만 그 한 원소를 안 뽑으면 영원히 복원 불가다. 그래서 특이벡터가 좌표축에 몰려 있지 않다는 비간섭성(incoherence)을 요구하며, 그 조건 아래 $O(\mu n r \log^2 n)$ 개의 무작위 관측이면 핵노름 최소화가 정확히 복원한다는 것이 캉데스 이후의 결과다. 실무 추천 시스템이 이 조건을 만족한다는 보장은 없고, 그래서 현장은 이론적 보증이 없는 정규화 교대최소제곱을 더 많이 쓴다. 에카르트-영-미르스키가 통하지 않는 세계라는 점을 놓치면 안 된다 — 여기엔 잘라 낼 특이값 자체가 없다.

7. 텐서에서는 정리가 깨진다[편집]

3차 이상으로 올라가면 상황이 급변한다. 행렬에서 당연했던 것 중 살아남는 게 별로 없다.

랭크 계산부터 NP-난해이고, CP 분해의 최적 랭크- $r$ 근사는 존재하지 않을 수 있다(최소값에 도달하지 못하고 발산하는 수열이 있다). 최적화 문제가 잘 정의조차 안 되는 것이다.
그럼에도 실용적 탈출구가 있다. 각 모드를 펼친 행렬에 SVD를 걸어 만드는 터커/HOSVD 근사는 최적해의 $\sqrt{d}$ 배, 텐서 트레인의 TT-SVD는 $\sqrt{d-1}$ 배 안에 든다는 준최적성이 보장된다. 최적은 못 되지만 상수배 안이고, 결정적 알고리즘이며, 한 번 훑어 계산된다.

이 준최적성이 텐서 네트워크와 DMRG가 굴러가는 이유다. “SVD로 자른다”는 같은 동작이 차수가 올라가면 최적성 대신 준최적성을 준다는 사실만 정확히 알고 있으면 된다.

8. 어디에 쓰이나[편집]

축소차수모델과 적합직교분해. 스냅숏 행렬의 저랭크 근사가 곧 POD 기저다. 감쇠가 느린 이류 지배 문제에서 이 접근이 막히는 것이 비선형 다양체 기반 ROM 연구의 출발점이다.
계층 행렬(H-행렬)과 BEM. 밀집 $N\times N$ 행렬을 블록으로 쪼개고, 서로 멀리 떨어진 블록만 ACA로 저랭크 압축하면 저장·곱 비용이 $O(N\log N)$ 으로 떨어진다. 고속 다중극자법이 커널 전개를 손으로 유도하는 데 비해, H-행렬은 같은 일을 대수적으로, 커널을 몰라도 해낸다는 것이 차이다.
커널 방법의 니스트룀 근사. $n\times n$ 커널 행렬을 대표점 $m$ 개로 저랭크 근사하면 가우시안 프로세스 추론이 $O(n^3)$ 에서 $O(nm^2)$ 로 내려온다.
LoRA. 거대 언어모형 미세조정에서 가중치를 통째로 갱신하지 않고 $W + BA$ ( $B\in\mathbb R^{d\times r}$ , $A\in\mathbb R^{r\times k}$ , $r$ 은 보통 4~64)로 갱신량만 저랭크로 제약한다. 흔한 오해와 달리 $W$ 자체를 저랭크 근사하는 것이 아니다 — 원본 가중치는 손대지 않고 얼리며, 학습 대상 파라미터 수만 몇 자릿수 줄인다. 신경망 가지치기가 원소를 지우는 쪽이라면 이쪽은 부분공간을 좁히는 쪽이다.

9. 실무 체크리스트[편집]

특이값 스펙트럼부터 그려라. 로그 축에 $\sigma_i$ 를 찍어 보지 않고 $r$ 을 고르는 것은 도박이다. 감쇠가 안 보이면 저랭크 근사가 답이 아닌 문제일 가능성이 높다.³
오차 기준을 상대값으로. $\sigma_{r+1}/\sigma_1$ 로 재야 스케일에 안 흔들린다. 절대 임계값은 단위를 바꾸는 순간 무너진다.
$A$ 에 어떻게 접근할 수 있는지가 알고리즘을 정한다. 전체가 메모리에 있으면 SVD/란초스, 곱만 가능하면 랜덤화, 원소만 꺼낼 수 있으면 ACA/CUR, 일부만 관측됐으면 행렬 완성이다.
인수를 곱해 놓지 마라. $XY^{\mathsf T}$ 를 명시적으로 조립하는 순간 $O(mn)$ 메모리가 돌아온다. 저랭크의 이득은 인수 형태를 끝까지 유지할 때만 남는다.
저랭크 인수의 재직교화를 잊지 마라. 저랭크 행렬을 더하고 다시 자르는 연산을 반복하면( $H$ -행렬 산술, TT 반올림) 인수의 직교성이 조용히 무너진다. QR 분해 기반 재압축이 주기적으로 필요하다.

10. 관련 문서[편집]

저랭크 근사는 학계에서 이름이 가장 여러 번 바뀐 주제 중 하나다. 수치해석에서는 골격 근사, 통계에서는 요인 분석, 신호처리에서는 부분공간 추적, 화학공학에서는 PCA, 양자정보에서는 슈미트 절단, 딥러닝에서는 LoRA. 같은 SVD를 놓고 여섯 커뮤니티가 각자 새 이름을 붙였고, 그래서 논문 검색이 유독 고달프다. ↩
가중 저랭크 근사가 NP-난해라는 사실은 처음 들으면 잘 안 믿긴다. 가중치를 전부 1로 두면 SVD 한 방에 끝나는 문제인데, 원소마다 다른 상수를 곱하는 순간 난이도가 다른 세계로 넘어간다. 결측치를 가중치 0으로 처리하는 관행이 곧 행렬 완성이라는 점을 생각하면 그럴듯하기는 하다. ↩
” $r$ 을 몇으로 잡을까요”라는 질문에 “에너지 99%요”라고 답하는 관행은 편하긴 한데, 그 99%가 무엇에 대한 99%인지는 아무도 안 묻는다. 스냅숏 재현율이지 하류 예측 정확도가 아니다. 최적성 정리가 붙은 방법을 볼 때는 무엇에 대해 최적인지를 먼저 확인하는 습관이 수명을 늘려 준다. ↩