NeurIPS 2025 Oral

Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy

잡음 섞인 공분산의 랭크 p 근사는 얼마나 움직이나

고윳값 간격이 잡음의 네 배를 넘으면 랭크 p 근사가 잡음 크기에 λp/δp를 곱한 정도까지만 움직인다는 것을 복소 경로 적분으로 보인 NeurIPS 2025 구두 발표 논문

차분 프라이버시를 위해 공분산 행렬에 가우시안 잡음을 더하면 상위 p개 고유 성분으로 만든 근사가 흔들린다. 그 흔들림을 가장 나쁜 방향(스펙트럼 노름)으로 재고, 고전적인 에카르트-영-미르스키 한계 대신 고윳값 간격으로 묶은 논문을 읽는다.

키워드

차분 프라이버시, 행렬 섭동 이론, 저랭크 근사

3줄 요약

• 공분산 행렬 \(A\)를 차분 프라이버시(differential privacy)로 공개할 때는 흔히 대칭 가우시안 잡음 \(E\)를 더한 뒤 상위 \(p\)개 고유 성분만 남긴 \(\tilde A_p\)를 내놓는다. 문제는 \(\tilde A_p\)가 원래의 최적 근사 \(A_p\)에서 가장 나쁜 방향으로 얼마나 벗어나느냐, 곧 스펙트럼 노름 \(\|\tilde A_p - A_p\|\)인데, 고전적인 답 \(2(\lambda_{p+1}+\|E\|)\)는 잡음이 0으로 가도 \(2\lambda_{p+1}\)에 머문다.
• 이 논문은 \(p\)번째 고윳값 간격 \(\delta_p=\lambda_p-\lambda_{p+1}\)이 \(4\|E\|\) 이상이면 \(\|\tilde A_p - A_p\| = O(\|E\|\,\lambda_p/\delta_p)\)임을 보인다(정리 2.1). 잡음의 분포를 가정하지 않는 부등식이라, 가우시안 잡음에 넣으면 차분 프라이버시 PCA의 오차가 기댓값이 아닌 높은 확률로, 앞선 결과의 \(\sqrt p\) 인자 없이 묶인다(따름정리 2.4).
• 증명은 경로 적분(contour integral)으로 상위 \(p\)개 성분만 골라낸 뒤, 섭동 급수를 펼치는 대신 구하려는 양이 자기 자신의 절반 이하로 다시 나타난다는 관찰 하나로 끝낸다(보조정리 3.1). 다만 증명의 상수를 펼치면 로그 항이 붙고, 상한은 실제 오차보다 수십 배 크다.

선정 이유

NeurIPS 2025 구두 발표(oral)로 뽑혔다. 다섯 리뷰어의 최종 점수는 6점 만점에 6점 둘, 5점 셋이었고, 한 리뷰어는 3년 넘게 이 문제를 붙들고 있었다며 논문을 적극 지지했다. 블로그의 연구 여지 지도에서는 ‘고차원 통계와 학습 이론’ 주제로 묶였고, 이 주제는 LLM 중심 주제를 뺀 109개 가운데 19위다.

1. 전후로 아는 것이 달라졌나. 달라졌다. 랭크 \(p\) 근사가 스펙트럼 노름으로 얼마나 흔들리는지는 사실상 고전 한계로만 알 수 있었고, Mangoubi와 Vishnoi가 열린 문제로 남긴 높은 확률의 스펙트럼 노름 한계(1장)를 이 논문이 닫았다.
2. 새 질문을 여는가. 연다. 같은 논법이 정함수(entire function) 전체로 넓어져서(정리 2.3), 행렬 거듭제곱이나 지수 함수의 저랭크 근사가 잡음에 얼마나 버티는지도 같은 틀로 물을 수 있다.
3. 일반화될 근거가 있나. 있다. 정리 2.1은 잡음이 대칭이고 간격 조건만 만족하면 성립하는 결정론적 부등식이다. 저자들은 양자화된 가우시안이나 라플라스 잡음에도 그대로 쓸 수 있다고 적었다(2장).
4. 증거가 주장만큼 강한가. 증명은 짧고 따라가기 쉽다. 다만 상한은 실제 오차보다 수십 배 크고, 실험에 쓴 상수는 증명이 주는 식과 다르다. ’날카롭다’는 말은 차수(order)에 대한 것으로 읽어야 한다.

왜 중요한가

고윳값이 \(\lambda_1\ge\cdots\ge\lambda_n\), 고유벡터가 \(u_1,\dots,u_n\)인 행렬 \(A\)에 가장 가까운 랭크 \(p\) 행렬은 스펙트럼 노름으로 재든 프로베니우스 노름으로 재든 \(A_p=\sum_{i\le p}\lambda_i u_i u_i^\top\)이다(1장). PCA는 공분산 행렬에서 이 \(A_p\)를 구하는 일이다.

공분산이 의료 기록처럼 민감한 데이터에서 나왔다면 \(A_p\)만 공개해도 개인 정보가 샐 수 있다. Dwork, Talwar, Thakurta, Zhang(STOC 2014)의 표준 방법에서는 성분마다 독립인 대칭 가우시안 잡음 \(E\)를 더한 \(\tilde A = A+E\)에서 랭크 \(p\) 근사 \(\tilde A_p\)를 구해 공개한다(1장). 잡음의 크기는 프라이버시 예산 \((\varepsilon,\delta)\)가 정하고, 입력에 잡음을 섞고 끝내므로 입력 섭동(input perturbation)이라 부른다. 남는 질문은 효용(utility), 곧 \(\tilde A_p\)가 \(A_p\)에서 얼마나 멀어졌느냐다.

무엇으로 잴까. 앞선 연구는 주로 프로베니우스 노름 \(\|\tilde A_p - A_p\|_F\)나 재구성 오차의 변화 \(\big|\|A-A_p\| - \|A-\tilde A_p\|\big|\)로 쟀다(1장). 논문은 둘 다 고유공간이 얼마나 돌아갔는지를 잘못 전할 수 있다고 본다. 프로베니우스 노름은 모든 방향의 오차를 제곱해 더하므로 오차가 퍼져 있으면 최악의 한 방향보다 크게 나온다. \(\tilde A_p - A_p\)의 랭크가 \(2p\) 이하라서 두 노름의 비는 최대 \(\sqrt{2p}\)다. 재구성 오차는 거꾸로, 잘라 낸 꼬리가 잔차의 크기를 정하는 탓에 고유공간이 꽤 돌아가도 거의 변하지 않는다(부록 C). 스펙트럼 노름은 어떤 단위 벡터를 넣어도 두 근사의 차이가 이 값을 넘지 않는다는 약속이라, 고유공간의 기하를 쓰는 후속 작업에 바로 이어진다.

(가) 재구성 오차는 회전을 놓친다

(나) 프로베니우스 노름은 방향을 모두 더한다

랭크 p 근사가 얼마나 틀렸는지 재는 세 가지 잣대. (가) 고윳값 1과 0.5인 2×2 행렬의 긴 축을 15° 돌리면 랭크 1 근사의 스펙트럼 오차는 sin 15° = 0.26이지만, 재구성 오차의 변화 |‖A−A₁‖ − ‖A−Ã₁‖|는 0.06에 그친다. 남아 있는 짧은 축 0.5가 잔차의 노름을 거의 그대로 정하기 때문이다. (나) 아래 계산 그래프와 같은 설정(n=1,000, p=10, ‖E‖/δ_p=0.1)에서 한 번 뽑은 오차 행렬 Ã_p−A_p의 특이값. 오차가 2p=20개 방향에 고르게 퍼져 있어 프로베니우스 노름이 스펙트럼 노름의 4.0배이고(최대 √20≈4.5배), 재구성 오차의 변화는 0.02에 그친다.

고전적인 답. 스펙트럼 노름 한계는 삼각부등식 하나로 나온다(부록 B). 양의 준정부호 행렬이면 에카르트-영-미르스키(Eckart-Young-Mirsky) 정리에 따라 \(\|A-A_p\|=\lambda_{p+1}\)이므로

\[ \|\tilde A_p - A_p\| \le \|\tilde A_p - \tilde A\| + \|\tilde A - A\| + \|A - A_p\| = \tilde\lambda_{p+1} + \|E\| + \lambda_{p+1} \le 2(\lambda_{p+1} + \|E\|) \]

이고, 마지막 부등호는 고윳값이 잡음의 노름보다 많이 움직이지 않는다는 바일 부등식(Weyl’s inequality)에서 나온다. 잡음이 어떤 꼴이든 성립하지만, 전체 행렬 \(A\)와 \(\tilde A\)를 거쳐 돌아가느라 잘라 낸 꼬리 \(\lambda_{p+1}\)을 두 번 치른다. 그래서 잡음이 0에 가까워져도 한계는 \(2\lambda_{p+1}\)에 머문다.

그동안의 진전. Mangoubi와 Vishnoi(NeurIPS 2022, J. ACM 2025)는 잡음이 더해지는 동안 고윳값과 고유벡터가 움직이는 다이슨 브라운 운동(Dyson Brownian motion)을 이토 미적분으로 따라가, 간격 조건 아래에서 \(\mathbb E\|\tilde A_p - A_p\|_F = \tilde O(\sqrt p\,\|E\|\,\lambda_p/\delta_p)\)를 얻었다(1장). 다만 기댓값에 대한 결과이고, 가우시안 잡음에만 성립하며, 프로베니우스 노름으로 잰다. 연산자 노름으로 넘어가려면 확률 과정 전체에서 고윳값과 고유벡터의 상관을 통제해야 해서 막힌다(부록 B).

핵심 아이디어

직관: 회전 각도에 고윳값을 곱한다

가장 작은 예로 \(A=\mathrm{diag}(\lambda_p,\lambda_{p+1})\)에서 위쪽 성분 하나만 남긴다고 하자. 잡음이 대각 성분에만 있으면 고유벡터는 그대로이고 고윳값만 움직여 오차는 \(\|E\|\)다. 논문이 차수가 최선임을 보일 때 드는 \(E=\mu I\)가 이 경우다(2장). 잡음이 비대각 성분 \(\varepsilon\)이면 사정이 다르다. 위쪽 고유벡터가 대략 \(\varepsilon/\delta_p\)만큼 돌아가고, 근사는 ’고윳값 곱하기 고유벡터 방향의 사영’이므로 차이는 \(\lambda_p\varepsilon/\delta_p\) 정도가 된다. 2×2로 계산해 보면 \(\lambda_p/\delta_p\)가 2일 때 오차는 \(\|E\|\)의 2.01배, 10일 때 9.9배다. 블로그의 해석으로는 정리 2.1의 \(\|E\|\,\lambda_p/\delta_p\)가 이 두 효과, 곧 고윳값의 이동과 ’회전 각도 곱하기 고윳값’을 함께 담은 꼴이다.

\(\lambda_p=\delta_p+\lambda_{p+1}\)로 바꿔 쓰면 고전 한계와의 차이가 드러난다(2장).

\[ \|\tilde A_p - A_p\| = O\Big(\|E\| + \lambda_{p+1}\cdot\frac{\|E\|}{\delta_p}\Big) \]

고전 한계에 맨몸으로 들어가던 꼬리 \(\lambda_{p+1}\)에 회전 각도 \(\|E\|/\delta_p\)가 곱해졌다. 잡음이 작으면 꼬리의 영향도 함께 사라진다. 개선 폭은 \(\min\{\lambda_{p+1}/\|E\|,\ \delta_p/\|E\|\}\)배다. 논문의 예처럼 스펙트럼이 \(\{10n, 9n, \dots, n, n/2, 1, \dots, 1\}\)이고 \(p=10\)이면, 노름이 \(O(\sqrt n)\)인 가우시안 잡음에 대해 고전 한계는 \(O(n)\), 새 한계는 \(O(\sqrt n)\)이다(2장).

방법: 경로 적분으로 상위 p개만 골라낸다

복소평면에서 \(\lambda_1,\dots,\lambda_p\)만 감싸고 나머지 고윳값은 밖에 두는 닫힌 경로 \(\Gamma\)를 그리면, 코시 적분 공식으로 상위 \(p\)개 성분만 골라낼 수 있다(3장).

\[ \frac{1}{2\pi i}\oint_\Gamma z\,(zI-A)^{-1}\,dz = \sum_{i\le p}\lambda_i u_i u_i^\top = A_p \]

\((zI-A)^{-1}\)을 레졸벤트(resolvent)라 부른다. \(\tilde A\)의 상위 \(p\)개 고윳값도 같은 경로 안에 있으면 \(\tilde A_p\)도 같은 식으로 나오므로, 두 근사의 차이는 레졸벤트 차이의 적분이 된다. 그 크기는 적분 안의 노름을 경로를 따라 더한 양 \(F\)를 넘지 않는다(식 1, 2).

논문의 경로는 왼쪽 변이 \(\lambda_p\)와 \(\lambda_{p+1}\)의 한가운데, 오른쪽 변과 높이가 \(2\lambda_1\)인 직사각형이다(3장). 간격 조건 \(4\|E\|\le\delta_p\)가 있으면 바일 부등식 때문에 \(\tilde A\)의 고윳값도 왼쪽 변을 넘지 못해, 한 경로를 두 행렬에 함께 쓴다.

(가) 고윳값 사이를 지나는 경로

(나) 경로 부트스트래핑

(가) 경로 적분으로 A의 상위 p개 성분만 골라내려면, 복소평면에서 λ₁…λ_p만 감싸는 닫힌 경로 Γ가 필요하다. 논문은 왼쪽 변을 λ_p와 λ_p+1의 한가운데에 두고 오른쪽 변과 높이를 2λ₁로 잡은 직사각형을 쓴다(3장). 잡음이 간격의 4분의 1 이하이면 Ã의 고윳값은 ±‖E‖ 안에서만 움직이므로 어느 것도 Γ를 넘지 않고, 같은 경로로 Ã_p도 골라낼 수 있다. (나) 레졸벤트 항등식으로 차이를 펼치면 둘째 항 안에 구하려는 양 F가 다시 나타나고, 그 앞의 계수가 ½ 이하라서 F ≤ 2F₁이 된다(보조정리 3.1, 식 3). 축척을 무시한 개념도다.

경로 부트스트래핑. \(F\)를 어림하는 흔한 길은 차이를 \(E\)의 거듭제곱 급수로 펼쳐 항마다 어림하는 것인데, 논문은 이 방식이 \(f(z)=z\)처럼 \(|z|\)와 함께 커지는 함수에서는 통하지 않는다고 본다(3장 2단계). 그래서 급수를 펼치지 않는다. 레졸벤트 항등식 \((zI-A)^{-1}-(zI-\tilde A)^{-1} = (zI-A)^{-1}E(zI-\tilde A)^{-1}\)의 오른쪽에서 \((zI-\tilde A)^{-1}\)을 다시 ’\((zI-A)^{-1}\)에서 원래의 차이를 뺀 것’으로 바꿔 쓰면, 둘째 항 안에 구하려던 차이가 그대로 다시 나온다. 삼각부등식을 쓰면

\[ F \le F_1 + \max_{z\in\Gamma}\big\|(zI-A)^{-1}E\big\|\cdot F \]

이다(식 3). \(F_1\)은 \(E\)를 한 번만 거친 항 \(z(zI-A)^{-1}E(zI-A)^{-1}\)의 적분이다. 경로 위의 모든 점은 \(A\)의 고윳값에서 \(\delta_p/2\ge 2\|E\|\) 이상 떨어져 있으므로 앞의 계수는 \(1/2\) 이하이고, 정리하면 \(F\le 2F_1\)이다(보조정리 3.1). 무한 급수를 자기 자신을 가리키는 부등식 한 줄로 바꾼 셈이고, \(z\) 자리에 어떤 정함수를 넣어도 그대로 통한다.

\(\lambda_p/\delta_p\)와 로그 항의 출처. 남은 일은 \(F_1\)의 계산이다. 적분 안의 노름은 \(\|E\|\,|z|/\min_i|z-\lambda_i|^2\)을 넘지 않고, 주된 기여는 고윳값에 가장 가까운 왼쪽 변에서 나온다. 실수축 근처에서 \(|z|\)는 대략 \(\lambda_p\)이고 가장 가까운 고윳값까지의 거리는 \(\delta_p/2\)라서, 세로 방향으로 적분하면 \(2\pi\lambda_p/\delta_p\) 정도가 남는다(3장 3단계). 좁은 간격을 지나는 자리의 \(|z|\)가 \(\lambda_p\)만큼 크다는 것이 \(\lambda_p/\delta_p\)의 출처다. 한편 실수축에서 멀리 올라가면 \(|z|\)와 거리가 함께 커져 적분 안의 값이 \(1/|t|\)처럼 줄어들고, 이것을 높이 \(2\lambda_1\)까지 더하면 \(\log(\lambda_1/\delta_p)\) 꼴의 항이 생긴다(보조정리 4.2).

수식: 세 정리와 프라이버시 따름정리

정리 2.1 (양의 준정부호 \(A\)). \(4\|E\|\le\delta_p\)이면 \(\|\tilde A_p - A_p\| \le O(\|E\|\,\lambda_p/\delta_p)\)다. 논문은 \(O\) 안의 상수가 7보다 작다고 적었다(2장). 4.1절의 증명을 양의 준정부호 경우로 좁혀 상수를 펼치면 식 5의 두 배인 다음 식이 된다.

\[ \|\tilde A_p - A_p\| \le 6\|E\|\Big(\frac{\lambda_p}{\delta_p} + \log\frac{6\lambda_1}{\delta_p}\Big) \]

일반 대칭 행렬로는 양수 쪽과 음수 쪽 고윳값을 두 경로로 따로 감싸 넓힌다(정리 4.1).

정리 2.2 (잡음과 고유공간의 상호작용). \(\lambda_{r+1}\le\lambda_p/2\)인 가장 작은 \(r\)(반감 거리)과 \(x=\max_{i,j\le r}|u_i^\top E u_j|\)에 대해, 같은 간격 조건에서 \(\|\tilde A_p - A_p\| \le \tilde O(\|E\| + r^2 x\,\lambda_p/\delta_p)\)다. 분산 1인 무작위 잡음이면 \(x\)는 로그 인자를 빼면 상수 크기지만 \(\|E\|\)는 \(2\sqrt n\)이라, \(r\)이 작은 저랭크 행렬에서는 정리 2.1보다 최대 \(\sqrt n\)배 좋아진다. 작은 공개 데이터에서는 정리 2.1이 더 쓸모 있다고 논문 스스로 적었다(2장).

정리 2.3 (스펙트럼 함수). 정함수 \(f\)와 \(f_p(A)=\sum_{i\le p}f(\lambda_i)u_iu_i^\top\)에 대해 \(\|f_p(\tilde A)-f_p(A)\| \le O(\max_{z\in\Gamma}|f(z)|\cdot\|E\|/\delta_p)\)이고 상수는 4보다 작다(2장).

따름정리 2.4 (차분 프라이버시). \(A\)가 양의 준정부호이고 \(E\)가 실수나 복소수 위그너 행렬(성분 분산 1)이면, \(\delta_p \ge 8.01\sqrt n\)일 때 확률 \(1-o(1)\)로 \(\|\tilde A_p - A_p\| \le O(\sqrt n\,\lambda_p/\delta_p)\)다. 위그너 행렬의 노름 \((2+o(1))\sqrt n\)을 정리 2.1에 넣은 결과다. 실제 가우스 메커니즘은 잡음을 \(O(\sqrt{\log(1/\delta)}/\varepsilon)\)배로 키우므로 한계도 같은 배율로 커진다(2장). Mangoubi와 Vishnoi의 결과보다 \(\sqrt p\) 인자가 빠지고, 기댓값이 높은 확률로 바뀌며, 실수 잡음도 다루고 \(\lambda_1\le n^{50}\) 같은 가정이 사라진다(2장).

블로그의 해석을 보태면, 행마다 노름을 1로 맞춘 데이터의 공분산(7장의 전처리)은 행이 많을수록 간격이 커지지만 프라이버시 잡음은 그대로다. 간격 조건은 결국 데이터가 충분히 많으냐는 질문이 된다.

결과 해설

실제 공분산. 7장은 UCI 저장소의 1990년 미국 인구조사(Census, \(n=69\), \(p=10\)), 1998년 KDD 컵(KDD, \(n=416\), \(p=2\)), Adult(\(n=6\), \(p=4\)) 공분산으로 실험한다. \(p\)는 \(A_p\)가 \(A\)의 프로베니우스 노름을 99% 넘게 담도록 골랐고, 간격은 각각 약 1433.99, 351.3, 37.02로 모두 조건 \(8\sqrt n<\delta_p\)를 만족한다. 가우시안 잡음과 라데마허(Rademacher) 잡음을 20단계로 키우며 단계마다 100번씩 평균했다.

논문 그림 1의 왼쪽과 가운데 패널. Census와 KDD 공분산에 가우시안 잡음을 더했을 때의 실제 스펙트럼 오차(파란 원), 논문이 그린 상한 7‖E‖λ_p/δ_p(주황 사각형), 고전 상한 2(‖E‖+λ_p+1)(초록 마름모). 가로축은 잡음의 표준편차, 세로축은 로그 눈금이다. 출처: Tran, Vishnoi, Vu (2025), CC BY 4.0.

세 행렬과 두 잡음 모두에서 아래부터 실제 오차, 논문의 상한, 고전 상한 순이고, 논문의 상한은 실제 오차와 나란히 움직인다(그림 1, 2). 다만 그림에서 읽으면 Census와 KDD에서 논문의 상한은 실제 오차의 30~40배쯤이다. 부록 D의 더 큰 행렬(대장암 마이크로어레이 데이터, \(n=2000\), \(p=9\))에서도 상한과 실제 오차의 비는 잡음 크기와 상관없이 87~90배로 일정했고, 고전 상한보다 작아지는 범위는 정확히 간격 조건 \(\|E\|/\delta_p\le 0.25\) 안쪽이었다(표 2).

상수까지 펼쳐 보면. 2장의 예시 스펙트럼에서 꼬리만 줄어들게 바꾼 장난감 행렬로 같은 비교를 하면, 실제 오차는 \(\|E\|\)의 약 0.57배이고 고전 상한은 잡음이 작은 쪽에서 \(2\lambda_{p+1}\)에 머문다. 논문의 상한은 기울기가 맞지만 증명의 상수로는 실제 오차의 약 72배라, 고전 상한을 이기는 것은 \(\|E\|/\delta_p\)가 0.05 아래일 때뿐이다(7배 식으로는 0.17). 차원을 키우면 \(n\)에 비례하는 고전 상한과 \(\sqrt n\)에 비례하는 논문의 상한이 뒤집히는데, 증명의 상수로는 \(n\)이 6,000 근처를 넘어야 한다.

(가) 잡음을 키울 때 (n=1,000)

(나) 차원을 키울 때 (잡음 표준편차 1)

실제 오차(파란 점, 평균)와 세 상한. 행렬은 논문 2장의 예시 스펙트럼 10n, 9n, …, n, n/2, 1, …, 1에서 뒤쪽의 1들을 n/2×0.9^k로 줄어드는 꼬리로 바꾼 대각 행렬이고(p=10, λ_p/δ_p=2), 잡음은 비대각 성분의 분산이 s²인 대칭 가우시안 행렬(GOE)이다. GOE는 회전해도 분포가 같아서 고유벡터를 표준 기저로 두어도 일반성을 잃지 않는다. 보라 선은 고전 상한 2(λ_p+1+‖E‖), 주황 실선은 4.1절 증명의 상수를 그대로 쓴 6‖E‖(λ_p/δ_p+log(6λ₁/δ_p)), 주황 점선은 논문 7장 실험이 그린 7‖E‖λ_p/δ_p다. (가) 잡음 단계마다 8번 평균했고, 회색 영역은 간격 조건 4‖E‖ ≤ δ_p 밖이다. 실제 오차는 ‖E‖의 약 0.57배로, 증명의 상수를 쓴 상한보다 약 72배, 7배 식보다 약 25배 작다. 고전 상한과의 역전(흰 원)은 ‖E‖/δ_p≈0.05(실선), 0.17(점선)에서 일어난다. (나) 따름정리 2.4의 설정으로, 차원마다 1~4번 평균했다. 간격 조건은 n ≥ 256에서 성립하고, 고전 상한은 n에, 논문 상한은 √n에 비례해 커진다.

의심해볼 점

• ’날카롭다’의 뜻. 7장은 상한이 관측 오차에서 한 자릿수(order of magnitude) 넘게 벗어나지 않는다고 적었지만, 그림 1에서 읽히는 비는 30~40배이고 표 2는 87~90배다. 차수와 모양을 맞힌다는 뜻이지 오차를 몇 배 안쪽으로 짚는다는 뜻은 아니다.
• 간격 조건과 프라이버시 잡음. 한 리뷰어는 프라이버시 잡음이 차원과 함께 커지므로 \(\delta_p\ge 8.01\sqrt n\) 같은 조건이 너무 강하다고 지적했다. 저자들은 \(\delta_p=4\sqrt n\), \((\varepsilon,\delta)=(1/2,1/10)\)이면 조건이 깨지고, 간격보다 큰 잡음이 한 방향에 몰리면 오차가 \(\lambda_p\)를 넘을 수 있다는 예로 답했다.
• ’처음’의 범위. 다른 리뷰어는 Hardt와 Roth(STOC 2013), Hardt와 Price(NeurIPS 2014)의 잡음 섞인 거듭제곱법(noisy power method)이 이미 높은 확률의 스펙트럼 노름 보장을 줬다고 지적했다. 저자들은 그쪽은 반복법이고 부분공간 각도를 재므로 저랭크 근사 오차로 옮기면 \(\lambda_1\) 인자가 붙는다고 답했고, 리뷰어도 받아들여 점수를 올렸다. 정확히는 입력 섭동 방식에서 처음이다.

리뷰어들이 짚은 점

다섯 리뷰어 모두 글이 잘 읽힌다고 평했다. 위에서 다룬 것 말고 남은 지적은 이렇다.

• 왜 \(A\)가 아니라 \(A_p\)와 비교하나. 어떤 랭크 \(p\) 행렬도 \(A\)와는 \(\|A-A_p\|\)만큼 떨어지니, 잡음이 더한 몫만 재는 것이 맞다는 답이었다.
• 다른 잣대. 부분공간 친화도(affinity)나 Ky Fan 노름을 쓰자는 지적에는 핵심 어림이 연산자 노름에서만 성립해 새 기법이 필요하다고 답했다.
• \(p\)보다 큰 랭크. 상위 \(p\)개 방향을 \(k>p\)개 차원으로 잡는 설정은 경로가 \(p\)개만 감싸도록 짜여 있어 바로 다루지 못한다고 저자들이 인정했다.

노트원문 검산 메모

• 상수 7과 로그 항. 2장은 정리 2.1의 상수가 7보다 작다고 하고 7장은 \(7\|E\|\lambda_p/\delta_p\)를 그렸지만, 4.1절 증명의 식에는 \(\log(6\lambda_1/\delta_p)\) 항이 따로 붙는다. 이를 묻는 리뷰어에게 저자들은 실제 데이터에서는 로그 항이 작아 6을 7로 올렸다고 답했다(답변에는 로그 안이 \(\lambda_p\)로 적혀 본문과도 다르다). 블로그의 해석으로는 \(\lambda_1\)이 \(\lambda_p\)보다 훨씬 크면 이 항을 무시하기 어렵다. 위 장난감 행렬은 \(\lambda_p/\delta_p=2\)인데 로그 항이 4.8이다.
• 부록의 작은 오류. 부록 C의 2×2 예(예 C.1)는 \(A=\mathrm{diag}(1,0)\)을 \(\theta\)만큼 돌리면 재구성 오차의 변화가 0이라고 적었다. 1장의 정의대로 \(\|A-\tilde A_p\|\)를 계산하면 \(|\sin\theta|\)로, 스펙트럼 오차와 같다. 블로그의 해석으로는 \(\tilde A\) 자신의 잔차 \(\|\tilde A-\tilde A_p\|\)와 비교한 듯하다. 꼬리가 클 때 재구성 오차가 회전을 가린다는 주장 자체는 논문 그림 3과 앞의 개념도가 뒷받침한다.

계보

• 고전 섭동 이론. 에카르트와 영(1936), 바일(1912), 데이비스와 카한(1970)의 고유벡터 회전 한계, 카토의 경로 적분 표현이 출발점이다.
• 차분 프라이버시 PCA. Chaudhuri, Sarwate, Sinha(NeurIPS 2012)와 Dwork 외(STOC 2014)의 가우스 메커니즘이 있고, 반복법 쪽에는 Hardt와 Roth(STOC 2013), Hardt와 Price(NeurIPS 2014)가 있다. 이 논문은 Mangoubi와 Vishnoi(NeurIPS 2022, J. ACM 2025)의 입력 섭동 분석을 잇고, Vishnoi는 양쪽 모두의 저자다.
• 기법의 뿌리. 경로 부트스트래핑은 Tran과 Vu가 중간 크기의 간격에서 데이비스-카한 정리를 다시 증명할 때 먼저 썼다(Communications in Contemporary Mathematics, 2025). 경로 적분 표현 자체는 고전 도구라 그 점을 더 일찍 밝혀야 한다는 리뷰어 지적이 있었고, 저자들은 기여가 그 위의 논법에 있다고 답했다.
• 후속 연구. 2026년 10월 기준 Semantic Scholar에 잡힌 인용은 10편이고, 그 가운데 6편은 저자가 겹친다. Tran과 Vishnoi는 같은 학회에서 \(f(z)=1/z\), 곧 저랭크 역행렬 근사로 틀을 넓혔다(arXiv 2510.25571). Tran과 Vu는 직사각 행렬과 무작위 잡음에서 고전 한계의 \(\sigma_{p+1}\) 항을 없애거나 크게 줄였고(arXiv 2511.08875), 고윳값 섭동 한계로도 연구를 넓혔다(arXiv 2603.19758, 2609.14303). 반복법 쪽에서는 Nguyen, Ene, Nguyen이 응집도(coherence)가 낮은 행렬에 맞춘 적응형 거듭제곱법을 냈다(arXiv 2602.11454).
• 같은 블로그의 글. BBP 전이 논문 해설은 고윳값이 잡음 덩어리에서 떨어져 나오는지를 묻고, 이 논문은 떨어져 나온 성분으로 만든 근사가 얼마나 버티는지를 묻는다. 차분 프라이버시의 다른 면은 스트리밍 메모리 하한 해설에 있다.

열린 질문

1. 간격 조건 밖에서. 잡음의 노름이 간격의 4분의 1을 넘을 때도 고전 한계보다 나은 스펙트럼 노름 한계가 성립할까. 부록 D의 실험은 그 비가 조건 밖에서도 일정함을 보이지만 증명은 없다.
2. 상수가 맞는 상한. 실제 오차를 몇 배 안쪽에서 따라가는 상한, 곧 공개된 행렬만 보고 계산할 수 있는 오차 증명서를 만들 수 있을까. 로그 항과 수십 배의 차이 가운데 어디까지가 증명 기법이 남긴 부산물인지가 열쇠다.
3. 다른 잣대와 다른 랭크. 부분공간 친화도, Ky Fan 노름, \(k>p\) 차원으로 상위 \(p\)개 방향을 잡는 설정에서도 같은 논법이 통할까.

이해 확인

1. 잡음이 0에 가까워져도 고전 상한 2(λp+1 + ‖E‖)가 2λp+1 밑으로 줄지 않는 까닭은?

1. 바일 부등식이 고윳값의 이동을 실제보다 크게 잡기 때문에
2. 삼각부등식이 전체 행렬 A와 Ã를 거쳐 가서, 잘라 낸 꼬리 λp+1을 잡음과 상관없이 두 번 치르기 때문에
3. 스펙트럼 노름이 프로베니우스 노름보다 늘 크기 때문에
4. 잡음이 가우시안이 아닐 때도 성립하도록 상수를 일부러 키웠기 때문에

‖Ãp − Ap‖ ≤ ‖Ãp − Ã‖ + ‖E‖ + ‖A − Ap‖에서 첫 항과 셋째 항은 λ̃p+1과 λp+1이라 잡음이 작아도 줄지 않는다(부록 B). 스펙트럼 노름은 오히려 프로베니우스 노름 이하다.

2. 정리 2.1을 O(‖E‖ + λp+1 ‖E‖/δp)로 다시 쓰면 꼬리 고윳값 λp+1에 ‖E‖/δp가 곱해진다. 이 인자의 뜻으로 가장 알맞은 것은?

1. 잡음이 상위 p개 고유공간을 돌리는 각도의 크기
2. 프라이버시 예산 ε에 반비례하는 잡음 배율
3. 프로베니우스 노름과 스펙트럼 노름의 비
4. 경로 Γ의 높이를 간격으로 나눈 값

데이비스-카한 정리처럼 고유공간은 ‖E‖/δp 정도로 돌아가고, 정리 2.3에 f = 1을 넣어도 사영 행렬의 변화가 O(‖E‖/δp)로 묶인다. 회전이 작으면 꼬리와 섞이는 정도도 작아서 잡음이 0으로 가면 이 항도 사라진다. 경로의 높이에서 나오는 것은 로그 항이다.

3. 경로 부트스트래핑에서 간격 조건 4‖E‖ ≤ δp가 하는 두 가지 일을 바르게 고른 것은?

1. 잡음 행렬을 양의 준정부호로 만들고, 로그 항을 없앤다
2. 실험식의 상수 7을 정당화하고, 고윳값의 부호를 지킨다
3. 경로 위에서 ‖(zI − A)⁻¹E‖ ≤ ½이 되게 해 F ≤ 2F₁을 끌어내고, Ã의 상위 p개 고윳값이 경로 안에 머물게 한다
4. 잡음의 노름을 2√n으로 맞추고, 레졸벤트 급수가 수렴하게 한다

경로 위의 점은 A의 고윳값에서 δp/2 이상 떨어져 있어 ‖(zI − A)⁻¹E‖ ≤ ½이고, F ≤ F₁ + ½F에서 F ≤ 2F₁이 나온다(보조정리 3.1). 또 Ã의 고윳값은 ±‖E‖ ≤ δp/4 안에서만 움직여 왼쪽 변을 넘지 않는다. 로그 항은 경로의 높이에서 나오고, 이 논법은 급수를 아예 펼치지 않는다.

논문 정보

• 제목: Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy
• 저자: Phuc Tran, Nisheeth K. Vishnoi, Van H. Vu (Yale University)
• 학회: NeurIPS 2025 Oral
• 링크: arXiv 2510.25670, OpenReview