랜덤화 수치선형대수(RandNLA), 최소제곱과 SVD를 수십 배 빠르게 만드는 무작위 스케치의 원리

핵심 메시지

• 수치선형대수는 컴퓨터 그래픽스와 기상 예측, 데이터 압축, MRI 복원, 추천 시스템, 딥러닝까지 떠받치는 기반 기술이다.
• 잘 배치된 무작위성은 큰 문제를 작은 '스케치'로 요약해 최소제곱 같은 핵심 연산의 계산량을 크게 줄인다.
• 이론상 1000배 수준까지 계산되는 가속은 실제 구현에서 20배 안팎으로 나타나며, 이는 하드웨어를 20배 늘린 것과 맞먹는 효과다.
• 무작위 알고리즘의 오차는 원하는 정밀도와 확률로 제어할 수 있어, 여러 사례에서 기존 표준 루틴과 사실상 같은 답을 낸다.
• BLAS와 LAPACK을 만든 연구자들이 RandBLAS·RandLAPACK이라는 새 축을 제안하면서 과학 계산 전반의 업그레이드 가능성이 열렸다.

쉽게 이해하기

영상은 수치선형대수(NLA)가 무엇이고 왜 중요한지에서 출발한다. 3차원 물체를 화면에 투영하고 회전시키는 그래픽스 연산은 물론 기상 예측, 데이터 압축, 구조 해석용 유한요소법, MRI의 압축 센싱, 유체 시뮬레이션, 추천 시스템과 검색, 그리고 심층 신경망까지 모두 이 위에 서 있다. 이 분야를 이끌었던 진 골럽은 20세기의 가장 중요한 알고리즘 열 개 가운데 여섯 개가 수치선형대수와 관련이 있다고 지적하기도 했다.

선형대수가 강력한 이유는 '선형이라고 가정하는 순간' 아주 적은 정보로 함수 전체를 결정할 수 있기 때문이다. 임의의 함수라면 두 점을 지나는 함수가 무한히 많지만, 선형을 가정하면 답은 하나뿐이다. 문제는 이를 컴퓨터로 빠르게 푸는 일이다. 기계는 수를 유한한 정밀도로만 표현해 덧셈의 결합법칙조차 성립하지 않고, 같은 행렬 곱이라도 연산 순서에 따라 데이터 이동량과 캐시 활용이 달라져 속도가 크게 갈린다.

그래서 이 분야의 역사는 하드웨어를 뒤쫓아 소프트웨어를 다시 쓰는 반복이었다. 1947년 폰 노이만과 골드스타인의 초기 연구, 1957년 포트란, 1960년대 윌킨슨의 알고리즘 정리(튜링상 수상)를 거쳐 1979년 BLAS와 LINPACK이 나왔고, 벡터 프로세서와 캐시 기반 병렬 구조가 등장할 때마다 BLAS 2·3이 뒤따랐으며 1992년 LAPACK으로 이어졌다. 오늘날 파이썬·R·매트랩·C++로 하는 선형대수는 대부분 이 계보의 소프트웨어를 부르고 있고, 분산 메모리용 ScaLAPACK, GPU용 MAGMA와 cuBLAS 같은 파생이 생태계를 이룬다.

이 성숙한 분야에 균열을 낸 것이 '랜덤화 수치선형대수' 논문이다. 핵심 예시는 어디에나 등장하는 최소제곱 문제다. 행이 매우 많은 행렬에서 기존 최선의 알고리즘은 대략 mn²의 연산이 필요한데, 작은 오차 ε을 허용하면 무작위 알고리즘은 mn·log(1/ε) + n³ 수준으로 푼다. n이 수천이고 원하는 정밀도가 소수점 몇 자리라면 지배항의 비율만 따져도 1000배 가까운 가속이 계산된다. 실제로는 생략된 비용 때문에 그 정도까지는 아니지만 20배 수준의 이득이 관측되는데, 같은 이득을 하드웨어로 얻으려면 비용과 전력을 20배 써야 한다.

원리는 '스케치 후 풀기'로 요약된다. 무작위 행렬 S를 곱해 행 수를 크게 줄인 축소 문제를 만들고 그것을 푸는데, 높은 확률로 원래 문제에서의 오차가 최적값과 거의 차이가 없다. 직관적으로는 원 데이터와 축소 데이터의 공분산 구조가 비슷해지기 때문이며, 원하는 근사 수준과 그 확률을 정하면 S의 크기가 정해진다. 실측도 뒤따른다. 저계수 행렬용 랜덤화 SVD는 기본 SVD 대비 40~100배, 키 큰 행렬용 랜덤화 QR 알고리즘은 LAPACK의 열 피벗 QR 대비 10~20배 빨랐고 오차는 기존 루틴과 견줄 만했다. 발표자는 통신 회피 알고리즘이나 전용 가속기와 달리 무작위화는 순수한 수학적 아이디어라 특정 하드웨어에 묶이지 않는다는 점을 가장 큰 강점으로 꼽는다.

주요 인사이트

• 정확한 답을 최대한 빨리 구하던 목표가, 충분히 가까운 답을 높은 확률로 빨리 구하는 목표로 바뀌었다는 점이 이 흐름의 본질이다. 데이터 자체가 잡음 섞인 근사인 머신러닝 시대에는 이 교환이 훨씬 자연스럽다.
• 가속의 크기를 정하는 것은 결국 문제의 모양이다. 행이 수백만인데 열은 수천인 '키 큰' 행렬이나 저계수 행렬처럼, 요약해도 정보 손실이 적은 구조에서 이득이 가장 크다.
• LAPACK이 모든 연산을 잘 최적화된 행렬 곱으로 환원해 속도를 얻었듯, 무작위화는 '빠르게 풀리는 새로운 기본 연산'을 하나 더 제공한다. 최소제곱이 싸지면 다른 문제들을 최소제곱의 반복으로 다시 쓰려는 시도가 이어진다.
• 제안된 RandBLAS·RandLAPACK이 자리 잡는다면 게임 그래픽스부터 기상 예측, 인공지능까지 같은 소프트웨어 층을 쓰는 분야 전체가 한꺼번에 혜택을 본다. 반대로 말하면 이 층의 개선은 응용 분야 하나를 고치는 것보다 파급력이 크다.

자주 묻는 질문