당신이 거대하고 다차원적인 퍼즐을 풀려고 노력하고 있다고 상상해 보십시오. 과학과 공학의 세계에서 이러한 퍼즐은 종종 "텐서(tensor)"라는 형태로 나타납니다. 텐서는 단순한 스프레드시트의 평면 시트나 데이터베이스의 단순한 열을 훨씬 넘어, 여러 방향으로 동시에 뻗어 나가는 다차원 데이터의 하이퍼 큐브라고 생각하면 됩니다. 이 텐서는 양자 입자가 어떻게 춤추는지 시뮬레이션하거나 흐릿한 의료 영상을 재구성하는 것과 같은 모든 것의 비밀 언어입니다. 하지만 여기에는 함정이 있습니다. 차원을 더 많이 추가할수록 퍼즐의 조각 수는 폭발적으로 늘어납니다. 3D 이미지는 감당할 수 있을지 모르지만, 4D 또는 5D 버전은 지구상의 모든 하드 드라이브를 채울 만큼 엄청난 양의 데이터를 포함할 수 있습니다. 이것이 바로 "차원의 저주"입니다.

이 거인들을 길들이기 위해 과학자들은 "저계수 근사(low-rank approximation)"라는 기술을 사용합니다. 복잡한 그림을 묘사할 때 모든 픽셀의 색상을 일일이 나열하는 대신, 몇 가지 붓터치와 그것들이 어떻게 결합하는지를 설명하는 것과 같습니다. 이는 데이터를 압축하여 숫자를 계산할 수 있게 만듭니다. 그러나 당신이 GMRES(단서 목록을 구축하는 단계별 탐정)라고 불리는 인기 있는 방법을 사용하여 이 퍼즐을 풀려고 할 때, 이상한 일이 발생합니다. 탐정이 새로운 단서를 추가할 때마다 그 단서의 "복잡성"이 커집니다. 탐정의 노트는 점점 더 복잡한 설명들로 채워지기 시작하고, 결국 노트는 너무 무거워져서 들고 다닐 수 없게 됩니다. 컴퓨터는 메모리가 부족해지고, 탐정은 자신의 노트에 파묻혀 사건을 해결하지 못한 채 갇히게 됩니다.

이 논문은 탐정의 노트를 가볍고 관리하기 쉽게 유지하는 영리한 새로운 방법을 소개합니다. 저자들(영국과 미국의 수학자 팀)은 두 가지 새로운 "스케치(sketched)" 알고리즘을 제안합니다. 모든 단서에 대해 전체적이고 무거운 설명을 쓰는 대신, 이 새로운 방법들은 각 단서의 빠르고 무작위적인 "스냅샷" 또는 "스케치"를 찍습니다. 이것은 복잡한 조각상을 자로 모든 곡선을 측정하는 대신, 사진을 찍는 것과 같습니다. 이 스냅샷을 사용함으로써 탐정은 훨씬 더 빠르게 문제를 해결하고 훨씬 적은 메모리를 사용할 수 있습니다. 그들은 이 방법들을 세 가지 유형의 문제, 즉 고전적인 물리 방정식(푸아송 방정식), 까다로운 유체 흐름 문제(대류-확산), 그리고 실제 이미지 디블러링(이미지 선명화) 작업에 테스트했습니다. 모든 경우에서, 이들의 새로운 "스냅샷" 탐정들은 기존의 무거운 방식보다 더 효율적으로 문제를 해결했으며, 이미지 디블러링 사례에서는 스냅샷을 찍는 행위 자체가 노이즈를 제거하는 필터 역할을 하여 진정한 이미지를 드러내는 데 도움을 주었습니다.

문제점: 과부하된 탐정의 노트

당신이 "크릴로프 부분 공간(Krylov subspace)"을 구축하며 미스터리를 풀려는 탐정이라고 상상해 보십시오. 쉽게 말해, 이것은 단순히 늘어나는 단서 목록입니다. 하나의 단서로 시작하여, 규칙(선형 연산자)을 사용하여 두 번째 단서를 생성하고, 그다음 세 번째 단서를 만드는 식입니다. 해결책을 찾으려면 이 모든 단서가 서로 달라야 하는데, 이를 "직교화(orthogonalization)"라고 합니다.

텐서(다차원 데이터)의 세계에서 이 과정은 벽에 부딪힙니다. 단서를 더 많이 추가할수록 각 단서의 수학적 "계수(rank, 복잡도의 척도)"가 커지는 경향이 있기 때문입니다. 이는 단순한 모양을 설명하려고 하는데, 세부 사항을 추가할 때마다 그 모양이 무한한 층을 가진 프랙탈이 되는 것과 같습니다. 곧 컴퓨터의 메모리는 점점 더 복잡해지는 이 설명들로 가득 차게 되고, 프로세스는 멈춰버립니다. 이것이 이 논문이 다루는 근본적인 병목 현상입니다. 표준적인 방법들은 너무 무거워서 들고 다닐 수가 없습니다.

해결책: 측정 대신 스냅샷 찍기

저자들은 이를 해결하기 위해 "스케칭(sketching)" 개념에 기반한 두 가지 새로운 전략을 제안합니다. 모든 무거운 단서의 전체 설명을 유지하는 대신, 그 단서의 압축된 무작위 "스케치"를 찍는 것입니다. 이렇게 생각해 보십시오. 만약 당신이 두 개의 거대한 그림을 비교하고 싶다면, 모든 픽셀을 측정하지 않을 것입니다. 대신, 약간 흐릿한 카메라로 각 그림의 빠른 사진을 찍어 사진들을 비교할 것입니다. 사진들이 충분히 비슷하다면, 그림들도 비슷하다는 것을 알 수 있습니다. 이는 엄청난 시간과 공간을 절약해 줍니다.

논문은 텐서 퍼즐을 위한 두 가지 구체적인 방법을 소개합니다:

1. "스마트 추정기" (RHOSVD-Tucker sGMRES)
이 방법은 무작위 고차 싱귤러 값 분해(RHOSVD) 기술을 사용합니다. 복잡한 3D 블록 더미가 있다고 상상해 보십시오. 모든 블록을 하나하나 세는 대신, 더미를 흔들어 빛이 어떻게 통과하는지를 보고 실제로 블록이 얼마나 있는지 추측하는 것입니다. 이 방법은 "적응형(adaptive)"입니다. 즉, 실시간으로 어느 정도의 세부 사항을 유지해야 하는지 스스로 판단합니다. 이 방법은 견고하며 다양한 문제에 잘 작동하지만, 여전히 단서의 전체 목록을 유지하되 더 똑똑한 방식으로 압축하는 방식을 취합니다.

2. "스트리밍 스트리머" (MLN-Tucker sGMRES)
이것은 더 급진적인 접근 방식입니다. 이 방법은 "다중 선형 니스트롬(Multilinear Nyström)" 근사를 사용합니다. 단서들이 하나씩 들어오는 컨베이어 벨트를 상상해 보십시오. 이 방법은 모든 단서를 거대한 창고에 저장하는 대신, 단서의 빠른 스냅샷을 찍고 수학적 계산을 수행한 뒤, 무거운 원본은 버리고 아주 작은 스격샷만을 남깁니다. 이 방식은 "스트리밍 가능(streamable)"합니다. 즉, 메모리 부족 없이 끊임없이 밀려드는 데이터를 처리할 수 있습니다.

• 마법의 기술: 저자들은 수학 문제를 풀기 위해 필요한 "스냅샷"이 사실 압축 과정에서 따라오는 무료 보너스라는 것을 발견했습니다. 두 번의 사진을 찍을 필요가 없습니다. 첫 번째 사진이 두 가지 일을 모두 수행합니다.
• 메모리 절약: 그들은 심지어 "메모리 효율적" 모드도 추가했습니다. 컴퓨터의 공간이 정말 부족하다면, 최종 답을 망치지 않으면서 스냅샷의 세부 사항 중 훨씬 더 많은 부분을 버리고 가장 필수적인 부분만 남길 수 있습니다.

결과: 더 빠르고, 더 가볍고, 더 깨끗하게

팀은 이 새로운 탐정들을 세 가지 도전 과제에 테스트했습니다:

• 물리 퍼즐 (푸아송 방정식): 그들은 3D 열 방정식을 풀었습니다. 새로운 방법들은 기존의 표준 방법들보다 더 빠르고 견고했으며, 특히 매우 높은 정밀도가 필요할 때 그러했습니다.
• 유체 퍼즐 (대류-확산): 이것은 단서들이 예쁘게 움직이지 않는 더 까다로운 비대칭 문제입니다. 여기서 "스트리밍" 방식(MLN)이 빛을 발했습니다. 이 방식은 기존 방법들의 약 절반 정도의 시간만 사용하여 문제를 해결했으며, 메모리도 훨씬 적게 사용했습니다. 기존 방법들에게 메모리를 아끼기 위해 더 적은 "단서"를 사용하도록 강제했을 때조차, 새로운 방법들이 더 우수한 성능을 보였습니다.
• 이미지 디블러링 미스터리: 이것이 가장 흥ant한 테스트였습니다. 그들은 흐릿하고 노이즈가 섞인 3D 이미지(예: 속이 빈 바 팬텀의 영상)를 가져와 선명하게 만들려고 했습니다.
  • 놀라운 점: 이미지를 저계수 형식으로 압축하는 행위(스냅샷을 찍는 것) 자체가 "정규화(regularizer)" 역할을 했습니다. 간단히 말해, 압축은 중요한 세부 사항은 유지하면서 고주파 노이즈(자글자글한 정전기 같은 것)를 자연스럽게 제거했습니다. 마치 탐정의 카메라 렌즈가 안개를 자연스럽게 걸러내는 필터 역할을 한 것과 같았습니다.
  • 결과: 이 자연스러운 필터링을 스마트한 수학적 조정(티코노프 정규화)과 결려함으로써, 그들은 사진에 노이즈가 정확히 얼마나 있는지 알지 못해도 이미지를 선명하게 재구성할 수 있었습니다. 새로운 방법들은 기존의 방법들이 실패하거나 엉뚱한 결과를 내놓을 수 있는 상황에서도 안정적이고 선명한 이미지를 만들어냈습니다.

이것이 왜 중요한가

이 논문은 거대한 문제를 풀기 위해 배낭에 온 세상을 다 담을 필요는 없다는 것을 보여줍니다. 무작위 "스냅샷"과 스마트한 압축을 사용함으로써, 메모리 제한 때문에 이전에는 불가능했던 거대한 다차원 퍼즐을 풀 수 있습니다. 저자들은 이러한 방법들이 단지 이론적인 것이 아니라, 실제 시뮬레이션에서도 작동한다는 것을 입증했습니다. 이 방법들은 기존 방식으로는 몇 분 또는 몇 시간이 걸릴 문제를 몇 초 만에 해결하며, 훨씬 적은 컴퓨터 메모리를 사용합니다.

가장 중요한 것은, 이미지 디블러링과 같은 역문제(inverse problems)의 경우, 압축 자체가 강력한 도구가 된다는 점을 보여주었다는 것입니다. 이는 노이즈가 많고 지저한 실제 데이터를 다루는 새로운 방식을 제시합니다. 모든 것을 완벽하게 측정하려고 애쓰는 대신, 스마트하게 압축하십시오. 그러면 노이즈는 저절로 사라질 수도 있습니다.