Analytic inverse problems with finitely many random measurements

숨겨진 형상의 미스터리

당신이 탐정이 되어 미스터리를 풀고 있다고 상상해 보세요. 하지만 용의자의 모습은 보이지 않습니다. 당신에게 있는 것이라고는 서로 다른 각도에서 찍힌 흐릿한 사진 몇 장, 혹은 몇 개의 음성 녹음 파일뿐입니다. 과학의 세계에서 이것을 **역문제(inverse problem)**라고 부릅니다. 이미 알려진 물체로부터 그 형태를 예측하는 것(이는 쉽습니다) 대신, 단서(데이터)로부터 시작하여 그 실체가 무엇인지 거꾸로 추적해 나가는 과정입니다. 의사들이 X-레이를 통해 몸속을 파악하거나, 지질학자들이 암석에 부딪혀 튕겨 나오는 음파를 듣고 지하 깊은 곳의 석유를 찾아내는 방식이 바로 이와 같습니다.

까다로운 점은 이러한 문제들이 종종 "부적절하게 설정된(ill-posed)" 경우가 많다는 것입니다. 이는 단서가 너무 모호하다는 것을 뜻하는 멋진 표현입니다. 만약 흐릿한 사진 몇 장만 가지고 있다면, 그 설명에 부합하는 용의자는 수천 명일 수도 있습니다. 보통 어떤 사람을 확실히 특정하기 위해서는 엄청난 양의 데이터, 즉 수천 장의 사진, 몇 시간 분량의 오디오, 혹은 지속적인 정보의 흐름이 필요합니다. 하지만 현실 세계에서 우리는 무한한 데이터를 가질 수 없습니다. 시간도, 돈도, 센서도 한정되어 있습니다. 그래서 과학자들은 한 가지 뜨거운 질문을 던져왔습니다. "이 미스터리를 풀기 위해 실제로 필요한 아주 작고 이산적인 단서의 개수는 과연 얼마인가?"

오랫동안 그 답은 "많음"인 것처럼 보였습니다. 내부 전도율이나 특이한 물질의 밀도를 알아내는 것과 같이 매우 어려운 미스터리의 경우, 전통적인 수학은 물체가 복잡해질수록 필요한 단서의 수가 기하급적으로 폭발할 것이라고 시사했습니다. 마치 책 한 권을 식별하기 위해 도서관 전체의 데이터가 필요한 것처럼 느껴졌습니다. 하지만 우리가 어떤 단서를 고르는지에 대해 더 똑똑해질 수 있다면 어떨까요? 가능한 모든 사진을 다 모으는 대신, 그저 무작위로 몇 개의 스냅샷만 찍는다면 어떨까요?

무작위 추측의 마법

이것이 바로 조반니 S. 알베르티(Giovanni S. Alberti), 다미아노 폴레티(Damiano Poletti), 시모네 산나(Simone Sanna), 그리고 마테오 산타세사리아(Matteo Santacesaria)의 논문이 탐구하는 내용입니다. 그들은 유한한 수의 측정값만을 가지고 이러한 까다로운 역문제를 어떻게 해결할 것인가를 다룹니다. 그들의 위대한 발견은, 만약 측정값을 무작위로(randomly) 선택한다면, 생각했던 것보다 훨씬 적은 수의 단서만으로도 미스터리를 풀 수 있다는 것입니다.

이것을 붐비는 방 안에서 특정 인물을 찾는 것에 비유해 봅시다. 기존의 방식은 방 안의 모든 사람에게 그 사람에 대해 묘사해 달라고 요청하거나, 일치하는 사람을 찾을 때까지 모든 사람의 사진을 찍는 것이었습니다. 이는 시간이 너무 오래 걸릴 것입니다. 이 논문에 따른 새로운 방식은 눈을 감고 빙글빙글 돌며 무작위로 사람들을 가리킨 뒤, "이 사람이 그 사람인가요?"라고 묻는 것입니다. 놀랍게도, 당신이 찾고 있는 사람이 고유한 형상(논문은 이를 가정합니다)을 가지고 있다면, 그 사람이 가진 "자유도(degrees of freedom)"의 약 두 배에 1을 더한 만큼의 횟수만 확인하면 됩니다.

논문의 언어로 표현하자면, 만약 미지의 물체(전도도 지도나 굴절률 같은 것)가 $d$ 차원의 공간에 존재한다면(여기서 $d$는 물체의 모양을 바꾸기 위해 돌릴 수 있는 노브의 개수라고 생각하세요), 수백만 개의 측정값이 필요하지 않습니다. 당신은 물체를 확실히 식별하기 위해 $2d + 1$개의 무작위 측정값만 있으면 됩니다.

여기에 마법 같은 트릭이 있습니다. 저자들은 만약 이론적으로 문제가 해결 가능하다면(즉, 무한한 데이터가 있다면 물체를 식별할 수 있다면), $2d + 1$개의 무작위 샘플을 뽑는 것만으로도 거의 확실하게(almost surely) 정답을 찾을 수 있음을 증명합니다. "거의 확실하게"라는 말은 수학적으로 "확률 1로"라는 뜻입니다. 이는 만약 당신이 이 실험을 10억 번 실행한다면, 물체를 식별하는 데 실패할 확률은 실질적으로 불가능할 정도로 희박한 경우뿐이라는 의미입니다.

이 논문은 두 가지 유명하고 어려운 퍼즐에 이 이론을 적용합니다:

1. 칼데론 문제(The Calderón Problem): 이는 표면의 전기를 측정하여 인체(사람이나 암석 등) 내부를 파악하는 것에 관한 것입니다. 전류를 주입하고 전압을 측정합니다. 논문은 무작위로 전류와 전압을 선택한다면, 내부 형상이 "해석적(analytic)"(매끄럽고 잘 정의된 수학적 곡선)이라는 조건 하에, 내부 전도도를 완벽하게 재구성하기 위해 오직 $2d + 1$개의 쌍만 필요함을 보여줍니다.
2. 역산란(Inverse Scattering): 이는 파동을 쏘고 그것이 어떻게 튕겨 나오는지 들어봄으로써 재료의 성질을 알아내는 것에 관한 것입니다. 음파든 빛이든, 논문은 파동을 쏘는 방향과 듣는 위치를 무작위로 선택한다면, $2d + 1$개의 무작위 "쏘고 듣기" 쌍이 재료를 식별하기에 충분하다는 것을 증명합니다.

이것이 게임의 판도를 어떻게 바꾸는가

이 논문 이전에는, 이러한 특정하고 어려운 문제들에 대한 최선의 결정론적(비무작위적) 방법들은 측정값이 물체의 복잡성에 따라 기하급수적으로 증가할 것이라고 시사했습니다. 만약 물체에 10개의 "노브"가 있다면 수천 개의 측정값이 필요했을 것이고, 20개라면 수백만 개가 필요했을 것입니다. 이는 슈퍼컴퓨터와 끝없는 데이터를 요구하는 레시피였습니다.

이 논문은 무작위 샘플링으로 전환함으로써, 그 숫자를 단순한 선형 관계로 대폭 줄일 수 있다고 주장합니다. 즉, $2d + 1$입니다. 만약 10개의 노브가 있다면 21개의 측정이 필요하고, 20개의 노브가 있다면 41개가 필요합니다. 이는 엄청난 감소입니다.

또한 저자들은 희소한(sparse) 물체들, 즉 대부분 비어 있거나 단순하여 실제로는 몇 개의 "노브"만 켜져 있는 대상들에 대해서도 살펴봅니다. 이 경우, 활성화된 노브의 개수를 $s$라고 할 때, $4s + 1$개의 측정값만 필요함을 보여줍니다. 이는 더욱 놀라운데, 매우 단순한 숨겨진 구조를 아주 적은 단서만으로도 찾아낼 수 있음을 의미하기 때문입니다.

주의 사항 (세부 조항)

이 논문이 약속하지 않는 바를 이해하는 것도 중요합니다. 저자들은 자신들이 **유일성(uniqueness)**을 증명했지, **안정성(stability)**을 증명한 것이 아님을 매우 신중하게 밝히고 있습니다.

• 유일성이란: "이 무작위 측정값들을 가지고 있다면, 가능한 답은 오직 하나뿐이다"라는 뜻입니다.
• 안정성이란: "측정값에 약간의 노이즈나 오차가 있더라도, 당신의 답이 완전히 틀려지지 않는다"는 뜻입니다.

이 논문은 답이 유일하다는 것을 증명합니다. 하지만 그 답을 찾기가 쉽다거나, 데이터에 약간의 노이즈가 섞였을 때 답이 무너지지 않을 것이라는 점은 증명하지 않습니다. 실제로 저자들은 이러한 어려운 문제의 경우, "안정성"이 매우 취약할 수 있다고 인정합니다(수학적으로는 "로그 안정성(logarithmically stable)"만을 가질 수 있으며, 이는 데이터의 아주 작은 오차가 결과의 거대한 오차로 이어질 수 있음을 의미합니다). 또한 그들은 데이터로부터 답을 실제로 계산해 내는 구체적인 알고리즘(단계별 레시피)을 제공하지 않습니다. 단지 답이 존재하며 유일하다는 것을 증명할 뿐입니다.

더 나아가, 이 논문은 완벽하고 노이즈가 없는 세상에서의 정확한 식별 가능성에 초점을 맞추고 있습니다. 센서가 고장 났거나 데이터가 지저한 상황에서도 문제를 해결할 수 있다고 주장하는 것이 아닙니다. 이것은 "만약 당신이 완벽하고 노이즈가 없는 신호를 가지고 있고 샘플을 무작위로 선택한다면, 매우 적은 샘플만으로도 반드시 올바른 물체를 찾아낼 수 있다"는 것을 말해주는 이론적 증명입니다.

결론

이 논문은 숨겨진 형상의 세계에서 무작위성이 하나의 강력한 무기임을 보여주는 수학적 증명입니다. 이는 광범위한 어려운 과학적 퍼즐들에 대해, 모든 가능한 데이터를 수집할 필요가 없음을 보여줍니다. 대신, 수학을 믿고 측정값을 무작위로 선택한다면, 물체의 복잡성보다 겨우 두 배 정도 많은 단서만으로도 미스터리를 풀 수 있습니다. 이는 산더미 같은 데이터를 모아야 하는 불가능한 작업을, 몇 번의 운 좋은 샷으로 형상을 맞히는 관리 가능한 게임으로 바꾸어 놓습니다.