N9 · 계산량을 줄인 뒤에도 답을 검증하는 방법#
1. 네 측정점의 변화를 한 방향으로 요약할 수 있을까#
같은 기준단위로 정규화한 네 측정점의 변화량을 \(x\in\mathbb R^4\)로 기록하고, 출력이 \(Ax\)라고 합시다. 이번에는 전체 평균, 두 지역 사이 차이, 더 작은 국소 차이가 서로 다른 배율로 전달됩니다. 다음 네 방향은 길이가 1이고 서로 직교합니다.
모형을 \(A=4u_1u_1^T+u_2u_2^T+\frac1{10}u_3u_3^T\)로 정합니다. 각 배율은 무차원입니다. 예를 들어 첫 행은 \((51,49,31,29)/40\)입니다. 상수 입력 \(u_1\)은 4배, 지역차 \(u_2\)는 1배, 국소차 \(u_3\)는 \(1/10\)배가 되고 \(u_4\)는 관측되지 않습니다.
H5의 최적 저계수 근사에 의해 최적 계수 1 근사는 \(4u_1u_1^T\)이고, 버린 부분의 스펙트럼노름은 1, Frobenius 노름은 \(\sqrt{1+1/100}\)입니다. 그런데 큰 자료에서는 모든 특이벡터를 먼저 계산하는 비용이 부담스럽습니다. 몇 개의 시험 입력에 대한 출력만으로 중요한 방향을 알아낼 수 있을까요?
시험 입력을 \(e_1=(1,0,0,0)^T\)로 두면 \(u_j^Te_1=1/2\)이므로
이를 정규화한 \(q\)와 \(u_1\) 사이 각도의 탄젠트는 \(\sqrt{(1/2)^2+(1/20)^2}/2=\sqrt{101}/40\)입니다. 이미 큰 배율의 방향이 강하게 나타납니다. \(AA^T\)를 한 번 더 적용하면 계수가 \(32,1/2,1/2000\)이 되므로 비율은 더 작아집니다. 다만 입력이 \(u_4\)이면 출력이 0이고, \(u_2\)이면 큰 방향을 영원히 놓칩니다. 고정된 시험 입력 하나가 모든 행렬에서 성공하는 것은 아닙니다.
그림 113 초기 시험 입력은 \(e_1\)이다. 왼쪽은 방향각의 탄젠트에 로그 눈금을 사용하고, 오른쪽은 스펙트럼 근사오차를 최적값 1과 비교한다. 방향이 계속 개선되어도 버려야 하는 둘째 특잇값 1은 사라지지 않는다.#
2. 곱셈 횟수와 자료 이동을 따로 세기#
밀집 \(n\times n\) 행렬 두 개와 벡터 하나가 있을 때 \((AB)x\)와 \(A(Bx)\)는 정확산술에서 같습니다. 첫 경로는 약 \(2n^3+2n^2\)번의 실수 연산과 \(n^2\)개 중간 성분을 요구하고, 둘째는 약 \(4n^2\)번과 \(n\)개 중간 성분이면 됩니다. 필요한 것이 벡터 출력 하나라면 결합순서를 바꾸는 것만으로 계산 자체가 줄어듭니다. 반올림 순서가 달라지므로 두 결과의 마지막 비트까지 같다고 요구하지는 않습니다.
다른 질문은 같은 계산량을 얼마나 빨리 수행하는가입니다. double 한 수를 8바이트로 세고, 처음 자료를 읽고 결과를 쓰는 이상적인 이동량을 비교해 봅시다. 캐시 재사용과 덧셈·곱셈 각각 1 flop이라는 규약을 사용합니다.
계산 |
대략적인 연산량 |
이상적인 자료 이동량 |
산술강도: flop/byte |
|---|---|---|---|
\(y\leftarrow ax+y\), BLAS 1 |
\(2n\) |
\(24n\) |
\(1/12\) |
\(y\leftarrow Ax\), BLAS 2 |
\(2n^2\) |
\(8(n^2+2n)\) |
큰 \(n\)에서 \(1/4\) |
\(C\leftarrow AB\), BLAS 3 |
\(2n^3\) |
\(24n^2\) |
이상적으로 \(n/12\) |
마지막 행은 각 행렬을 한 번만 읽거나 쓴다는 이상화입니다. 유한 캐시에서는 같은 블록을 여러 번 옮길 수 있습니다. 연산량 \(F\), 실제 이동량 \(D\), 최대 연산률 \(P\), 대역폭 \(B\)라면 시간은 적어도 \(F/P\) 및 \(D/B\)이므로
이는 상한이며 달성 보장이 아닙니다. 작은 행렬의 호출 비용, 스레드 시작 비용, 메모리 배치도 영향을 줍니다. 블록 행렬곱은 가져온 자료로 여러 출력을 만들기 때문에 재사용 기회가 크지만, 실제 속도비를 특정 숫자로 강제해서는 안 됩니다.
그림 114 양축은 로그 눈금이며 바이트당 실수 연산 수를 표시한다. 행렬곱 곡선은 이상적 재사용 모형의 값이다. 특정 컴퓨터의 측정 성능이나 무조건적인 속도 향상을 뜻하지 않는다.#
실제 코드를 읽을 때에는 다음을 확인합니다. 역행렬 전체가 필요한지, 선형계의 해만 필요한지 구별하고 해만 필요하면 분해·대입을 사용합니다. 같은 계수행렬의 여러 우변에는 분해를 재사용합니다. 대각 스케일링은 큰 대각행렬 대신 성분곱으로 수행합니다. 결합순서와 중간 배열 크기를 계산합니다. 비연속 배열의 복사 비용을 측정에 포함할지 명시합니다. 병렬 작업 안에서 BLAS 스레드가 중복되는지 확인합니다. 마지막으로 속도를 비교할 때 원래 문제의 잔차도 함께 계산합니다. 역행렬이라는 수학적 대상을 금지하는 규칙은 아닙니다.
실행시간은 다음처럼 같은 자료와 같은 출력으로 측정합니다. 배열 생성은 측정 밖이고 각 경로를 한 번 예열한 뒤 다섯 번의 중앙값을 보고합니다. 작은 예라 호출·캐시 효과도 포함되며, 속도의 순위를 통과조건으로 두지 않습니다.
import time
import numpy as np
rng_timing=np.random.default_rng(20260916)
At=rng_timing.normal(size=(160,160));Bt=rng_timing.normal(size=(160,160));xt=rng_timing.normal(size=160)
def median_seconds(operation,repeats=5):
operation()
elapsed=[]
for _ in range(repeats):
start=time.perf_counter();operation();elapsed.append(time.perf_counter()-start)
return float(np.median(elapsed))
left=lambda:(At@Bt)@xt
right=lambda:At@(Bt@xt)
relative=np.linalg.norm(left()-right())/np.linalg.norm(right())
assert relative<1e-12
print('크기 160, NumPy',np.__version__)
print('(AB)x / A(Bx) 중앙값(초):',median_seconds(left),median_seconds(right))
print('두 결과 상대차:',relative)
크기 160, NumPy 2.4.6
(AB)x / A(Bx) 중앙값(초): 0.0002152579999972204 1.073600000722763e-05
두 결과 상대차: 5.178035480445442e-16
3. 무작위성의 가정을 먼저 고정하기#
확률적 스케치는 원래 자료 \(A,b\)를 고정한 뒤, 그 자료와 독립적으로 시험행렬을 뽑는 절차입니다. 가우시안 행렬 \(S\in\mathbb R^{s\times m}\)의 성분을 독립적인 평균 0·분산 \(1/s\) 정규변수로 정합니다. 여기서는 정규밀도, 적분, 독립변수의 곱밀도, 기댓값과 합집합 부등식을 출발 전제로 사용합니다. 일반 확률공간과 농축이론은 I4에서 확장합니다.
고정된 비영 \(v\)에 대해 \(\|Sv\|^2/\|v\|^2\)는 독립 표준정규 \(Z_j\)의 제곱 평균 \(s^{-1}\sum_jZ_j^2\)와 같습니다. 마지막 절에서 직접 적분과 지수 Markov 부등식으로
을 증명합니다. 이는 제곱길이의 왜곡입니다. 길이에는 \(\sqrt{1\pm\epsilon}\)가 붙습니다.
고정된 \(N\)개 점의 차이벡터는 최대 \(N(N-1)/2\)개입니다. 각 실패확률을 더하면, 예를 들어 \(s\ge8\epsilon^{-2}\log(N(N-1)/\delta)\)이면 모든 쌍의 제곱거리가 확률 \(1-\delta\) 이상으로 보존됩니다. 이것이 가우시안 Johnson–Lindenstrauss 결론입니다. 원래 차원 \(m\)이 이 충분조건에 직접 나타나지 않지만, 모든 자료와 모든 방향을 동시에 보존한다는 명제는 아닙니다. \(s<m\)이면 \(S\)에는 영공간이 있습니다.
고정된 \(d\)차원 부분공간의 모든 방향을 보존하려면 유한 점 목록 대신 구면의 그물을 사용합니다. 마지막 절에서는 반지름 \(1/4\)인 그물의 점이 \(9^d\)개 이하이고,
이면 그 공간의 모든 \(v\)에 \((1-\epsilon)\|v\|^2\le\|Sv\|^2\le(1+\epsilon)\|v\|^2\)가 같은 확률로 성립함을 보입니다. 상수는 보수적인 증명용 값이며 실험의 최소 필요 차원이 아닙니다.
4. 작은 최소제곱을 대신 풀 것인가, 원래 문제를 빨리 풀 것인가#
\(\widetilde x=\arg\min_x\|S(Ax-b)\|\)를 구하는 것을 sketch-and-solve라고 합니다. 앞 임베딩은 \(\operatorname{col}(A)\)만이 아니라 \(\operatorname{col}([A\ b])\)에서 필요합니다. 모든 잔차가 그 공간에 있기 때문입니다. 성공 사건 위에서
완전 열계수이면 최소제곱 잔차가 열공간과 직교하므로
따라서 계수오차는 \(\sigma_{\min}(A)^{-1}\sqrt{2\epsilon/(1-\epsilon)}\|Ax_*-b\|\) 이하입니다. 목적함수의 작은 상대변화와 계수의 작은 상대변화는 같지 않습니다.
예를 들어 \(A=(0,\eta)^T\), \(b=(1,0)^T\)이면 정확해는 0입니다. \(S^TS=\begin{pmatrix}1&t\\t&1\end{pmatrix}\), \(|t|<1\)로 길이를 조금 비틀면 스케치 목적함수는 \(1-2t\eta x+\eta^2x^2\)입니다. 최소점 \(\widetilde x=t/\eta\)는 \(\eta\)가 작으면 매우 크지만 원래 잔차 제곱은 \(1+t^2\)입니다. 이 예의 \(S\)는 손계산용 결정론적 임베딩이며 무작위 표본이라고 부르지 않습니다.
다른 사용법은 \(SA=QR\)에서 \(R\)을 얻은 뒤 원래 문제를 \(AR^{-1}y\approx b\), \(x=R^{-1}y\)로 푸는 것입니다. \(\operatorname{col}(A)\)에서 임베딩이 성립하면
이것이 sketch-and-precondition입니다. \(R^{-1}\)을 명시적으로 만들 필요 없이 삼각풀이를 적용합니다. 최종 오차는 반복 정지, 삼각풀이와 원래 입력의 민감도에 달려 있으며 무조건 기계정밀도의 계수오차가 보장되지는 않습니다.
5. 무작위 범위 탐색과 작은 SVD#
시험행렬 \(\Omega\in\mathbb R^{n\times\ell}\)을 뽑고 \(Y=A\Omega\)의 정규직교기저 \(Q\)를 만듭니다. 다음 \(B=Q^TA\)의 SVD를 계산하여 \(A\approx QB\)로 요약합니다. 목표 계수 \(k\)보다 \(\ell=k+p\)를 크게 잡는 \(p\)가 오버샘플링입니다. 마지막에는 \(B\)의 상위 \(k\)개만 남길 수 있습니다. 범위 사영 오차와 계수 \(k\)로 다시 자른 오차는 구별해야 합니다.
멱반복은 \(Y=(AA^T)^qA\Omega\)에 해당하여 특이값을 \(\sigma_j^{2q+1}\)로 바꿉니다. 그대로 거듭제곱을 만들면 작은 방향이 소실되기 쉬우므로 매번 \(A^TQ\)와 \(AQ\) 뒤에 QR을 적용합니다.
import numpy as np
import scipy.linalg as la
def randomized_svd(A, k, oversample=4, power=1, seed=20260916):
A = np.asarray(A, dtype=float)
m, n = A.shape
if not 1 <= k <= min(m,n) or oversample < 0 or power < 0:
raise ValueError("계수와 반복 수를 확인하세요")
ell = min(k+oversample, m, n)
rng = np.random.default_rng(seed)
Q = la.qr(A@rng.normal(size=(n,ell)), mode='economic')[0]
for _ in range(power):
V = la.qr(A.T@Q, mode='economic')[0]
Q = la.qr(A@V, mode='economic')[0]
U, s, Vt = la.svd(Q.T@A, full_matrices=False)
return Q@U[:,:k], s[:k], Vt[:k], Q
W = np.array([[1,1,1,1],[1,1,-1,-1],[1,-1,1,-1],[1,-1,-1,1]],float).T/2
A = (W*np.array([4.,1.,.1,0.]))@W.T
U, s, Vt, Q = randomized_svd(A, 1, oversample=2, power=1)
assert np.linalg.norm(A-(U*s)@Vt,2) <= 1+1e-12
assert np.linalg.norm(Q.T@Q-np.eye(3)) < 1e-12
print("측정 행렬의 특잇값:", la.svdvals(A))
측정 행렬의 특잇값: [4.00000000e+00 1.00000000e+00 1.00000000e-01 1.36643908e-16]
독립 표준정규 \(\Omega\), \(p\ge2\)에서 마지막 절의 증명은
를 줍니다. 이것은 기대값이며 개별 실행의 상한이 아닙니다. 계수 \(k\) 절단 뒤에는 결정론적으로 \(\|A-QB_k\|_F^2\le\|(I-QQ^T)A\|_F^2+\sum_{j>k}\sigma_j^2\)를 사용할 수 있습니다. 더 정밀한 스펙트럼노름·멱반복 상한은 Halko–Martinsson–Tropp의 원 논문을 외부 조망으로 둡니다.
그림 115 각 점은 고정된 여러 시드의 실제 계산값이며 범위와 중앙값을 표시한다. 같은 크기의 두 행렬에서 최적 Frobenius 오차로 나눴다. 기대오차 정리를 모든 점에 대한 확정 상한으로 표시하지 않는다.#
원래 \(A\)를 다시 읽을 수 없는 단일 패스에서는 동시에 \(Y=A\Omega\), \(Z=\Psi A\)를 저장할 수 있습니다. \(Y\)로 \(Q\)를 만든 뒤 \((\Psi Q)B\approx Z\)를 풀어 \(B\)를 복원합니다. 이제 두 번째 작은 최소제곱의 계수와 조건수가 추가되며 \(B=Q^TA\)가 정확히 얻어지는 것은 아닙니다. 스트리밍 제약이 없는 위 코드와 같은 오차를 무조건 약속하지 않습니다.
6. 큰 관측 하나를 놓치지 않으려면#
회귀 설계 \(X=[\mathbf1\ t]\), \(t=(0,1,2,3,10)^T\)를 생각합시다. 평균은 \(16/5\), 중심 제곱합은 \(314/5\)입니다. 각 행의 레버리지 값은
합은 2이고 마지막 값은 \(147/157\)입니다. 마지막 관측은 단순히 값이 크다는 설명을 넘어 열공간의 방향을 많이 담습니다. 다섯 행에서 서로 다른 두 행을 균등하게 고르면 마지막 행을 놓칠 확률은 \(\binom42/\binom52=3/5\)입니다.
일반적으로 열공간의 정규직교기저 \(U\)에 대해 \(h_i=\|U_{i,:}\|^2\), \(\sum h_i=\operatorname{rank}X\), \(0\le h_i\le1\)입니다. 열기저를 가역적으로 바꾸어도 열공간과 사영이 같아서 값은 변하지 않습니다. 표본확률을 \(h_i/r\)에 비례시킬 이유는 이 방향정보이지만, 표본 수·재가중·실패확률을 생략한 채 그것만으로 정확한 회귀를 보장할 수는 없습니다.
7. 결과를 믿기 전에 계산할 숫자#
\(A\widehat x\approx b\)의 잔차를 \(r=b-A\widehat x\)로 직접 다시 계산합니다. 성분별 상대 후진오차는
분모·분자가 모두 0이면 비율을 0으로 둡니다. 이는 \(|E|\le\eta|A|\), \(|f|\le\eta|b|\) 아래 \((A+E)\widehat x=b+f\)가 되게 하는 최소 \(\eta\)이며 마지막 절에서 달성하는 \(E,f\)도 만듭니다. 실제 부동소수점 잔차를 계산할 때의 반올림은 별도이므로 높은 정확도의 인증에는 잔차 계산 자체의 오차도 제한해야 합니다.
def componentwise_backward_error(A,b,x):
residual = b-A@x
scale = np.abs(A)@np.abs(x)+np.abs(b)
ratios = np.divide(np.abs(residual),scale,out=np.zeros_like(scale),where=scale>0)
ratios[(scale==0)&(residual!=0)] = np.inf
return float(np.max(ratios))
Acheck = np.array([[2.,1.],[1.,3.]])
bcheck = np.array([1.,2.]); xcheck = np.array([.201,.599])
assert np.isclose(componentwise_backward_error(Acheck,bcheck,xcheck),1/1999)
print("성분별 상대 후진오차:", componentwise_backward_error(Acheck,bcheck,xcheck))
성분별 상대 후진오차: 0.0005002501250625317
전진오차에는 민감도가 추가됩니다. Hager 방식은 \(\|A^{-1}\|_1=\max_{\|x\|_1=1}\|A^{-1}x\|_1\)의 큰 값을 찾습니다. \(y=A^{-1}x\)를 풀고 \(s_i=\operatorname{sign}y_i\)로 둔 뒤 \(z=A^{-T}s\)를 풀면 \(s^TA^{-1}v=z^Tv\)가 선형 하한입니다. \(|z_j|\)가 가장 큰 좌표의 \(e_j\)를 다음 시험점으로 씁니다. 방문점에서 얻은 값은 역노름의 하한이며 전역 최댓값을 놓칠 수 있습니다. 조건수의 과소추정으로 전진오차를 과소평가할 수 있으므로 엄밀한 상한이라고 부르지 않습니다.
LAPACK에서 d는 실 double, ge는 일반행렬, po는 양의 정부호 계열입니다. getrf는 피벗 LU, getrs는 그 인자를 사용한 풀이, gecon은 조건수 추정에 쓰입니다. 이 이름을 안다고 상위 함수의 실제 경로가 자동 확정되지는 않습니다.
예를 들어 SciPy lstsq는 gelsd, gelsy, gelss를 선택할 수 있습니다. get_lapack_funcs로 루틴을 얻는 일과 상위 호출의 드라이버 선택을 추적하는 일을 구별합니다. 패키지 버전과 호출 옵션을 함께 기록합니다. ferr는 해당 루틴이 제공하는 전진오차 추정, berr는 성분별 잔차 기반 지표로 해석하며 같은 수치가 아닙니다.
앞 장의 실패 |
함께 확인할 양 |
대안 또는 추가 조건 |
|---|---|---|
N4 정규방정식의 정보 손실 |
원래 \(A\)의 조건수·잔차 |
원래 행렬의 QR/SVD |
N3 직교성 손실 |
\(|I-Q^TQ|\)와 분해 잔차 둘 다 |
재직교화·Householder |
N6 작은 특이값 소실 |
교차곱 대신 원래 입력 |
이중대각 SVD |
N8 비정규 GMRES 정체 |
실제 잔차 이력 |
고윳값만으로 판단하지 않기 |
N2 큰 소거 성장 |
성장인자·후진오차 |
피벗 전략과 스케일 검사 |
N5 다항식 경유 오차 |
원래 행렬의 고유쌍 잔차 |
Schur 기반 계산 |
고정 시드는 확률적 입력의 재생에 도움이 됩니다. 합산 순서, BLAS 버전, 스레드 수, 장치까지 다르면 비트 재현성은 별도입니다. 예를 들어 \((2^{53}+1)-2^{53}=0\)이지만 \(2^{53}+(1-2^{53})=1\)인 binary64 계산은 N1에서 이미 보았습니다. 시간 측정은 준비·워밍업·반복·집계 방식을 기록하고, 특정 스레드 수에서 반드시 빨라져야 한다는 검사는 두지 않습니다.
8. 연습과 전체 풀이#
1. \(u_4\)만 시험 입력으로 고르면 계수 1 근사가 왜 실패하나요?
풀이. \(Au_4=0\)이라 출력으로부터 비영 방향을 만들 수 없습니다. \(u_2\)를 고르면 출력은 \(u_2\)이므로 사영 후에도 \(4u_1u_1^T\)가 남아 오차가 4입니다. 시험 입력의 크기만 정규화해서 해결되는 문제가 아닙니다.
2. \(n=120\)에서 위 모형의 행렬곱과 행렬·벡터곱 산술강도를 비교하세요.
풀이. 행렬곱은 \(n/12=10\) flop/byte입니다. 행렬·벡터곱은 \(2n^2/[8(n^2+2n)]=120/488\approx0.246\)입니다. 이는 이상적 이동량의 비교이며 40.7배의 실제 속도비를 증명하지 않습니다.
3. \(s<m\)인 고정 스케치가 모든 벡터 길이를 보존할 수 없음을 보이세요.
풀이. 계수는 최대 \(s\)이므로 영공간 차원이 적어도 \(m-s>0\)입니다. 비영 \(v\in\ker S\)를 택하면 \(\|Sv\|=0\)인데 \(\|v\|>0\)입니다. 고정된 유한 집합·부분공간을 먼저 정한 뒤 확률을 적용해야 합니다.
4. \(\eta=10^{-4}\), \(t=10^{-2}\)인 4절 예의 계수와 원래 잔차를 구하세요.
풀이. 계수는 \(t/\eta=100\)이고 출력은 \((0,.01)^T\)입니다. 잔차는 \((1,-.01)^T\)로 제곱노름 \(1.0001\)입니다. 최적 잔차 제곱 1과 거의 같아도 계수는 100만큼 달라집니다.
5. 레버리지 수열의 합과 마지막 값이 1보다 작은 이유를 확인하세요.
풀이. 공통분모 314에서 분자는 \(114+87+70+63+294=628\)이므로 합은 2입니다. 마지막 값은 \(294/314<1\)입니다. 사영의 대각은 \(\|Pe_i\|^2\le\|e_i\|^2=1\)이며, 합은 사영 공간 차원입니다.
6. \(A=\operatorname{diag}(1,100)\), \(b=(1,100)^T\), \(\widehat x=(1,0)^T\)의 두 후진오차를 비교하세요.
풀이. 잔차는 \((0,100)^T\)입니다. 성분별 분모는 \((2,100)^T\)여서 berr는 1입니다. 2-노름 비구조 후진오차는 \(100/(100+\sqrt{10001})\approx1/2\)입니다. 허용하는 행렬·우변 섭동의 집합이 달라 같은 수가 아닙니다.
7. \(\ell=k+p\) 범위 사영의 기대오차 상한을 계수 \(k\) 결과의 각 실행에 그대로 적용해도 되나요?
풀이. 안 됩니다. 먼저 기댓값 상한은 모든 표본의 상한이 아닙니다. 또한 \(QQ^TA\)는 계수 최대 \(\ell\)이고 \(QB_k\)는 최대 \(k\)여서 추가 절단오차가 있습니다. 두 차이를 모두 반영해야 합니다.
9. 지금까지의 내용을 수학의 언어로 정리해 봅시다#
계산량 모형, 고정 입력에 대한 확률 명제, 계산 결과의 후진오차는 다른 종류의 주장입니다. 각각의 조건을 분리하여 증명합니다.
정리 1. 가우시안 길이 집중과 유한 점 보존#
3절의 단일 벡터 꼬리부등식과 유한 점에 대한 JL 결론이 성립합니다.
증명. 정규밀도의 직교불변성은 지수에 들어가는 제곱노름과 직교변환의 Jacobian 절댓값 1에서 따릅니다. 따라서 각 행과 고정 \(v\)의 내적은 분산 \(\|v\|^2/s\)인 정규변수이고 행들은 독립입니다. \(Z\sim N(0,1)\)에서 제곱완성과 변수변환으로 \(\mathbb E e^{tZ^2}=(1-2t)^{-1/2}\) (\(t<1/2\))입니다. \(X=\sum_{j=1}^sZ_j^2\)에 지수 Markov 부등식을 적용하고 \(t=\epsilon/[2(1+\epsilon)]\)를 쓰면
마지막 부등식은 \(\epsilon-\log(1+\epsilon)=\int_0^\epsilon t/(1+t)\,dt\ge\epsilon^2/4\)에서 얻습니다. 아래 꼬리에는 \(t=-\epsilon/[2(1-\epsilon)]\)를 적용하여 \(\exp[-s(-\epsilon-\log(1-\epsilon))/2]\)를 얻고, \(\int_0^\epsilon t/(1-t)\,dt\ge\epsilon^2/2\)이므로 같은 상한보다 작습니다. 두 사건을 더해 단일 벡터 명제를 얻습니다. 각 비영 점 차이에 적용한 실패확률을 합하면 최대 \(N(N-1)e^{-s\epsilon^2/8}\)이고, 제시한 \(s\)에서 \(\delta\) 이하입니다. 겹치는 점의 차이는 0이라 항상 보존됩니다. ∎
정리 2. 부분공간 임베딩과 두 최소제곱 사용법#
3절의 부분공간 차원 조건과 4절의 잔차·전처리 상한이 성립합니다.
증명. \(d\)차원 단위구면에서 서로 거리 \(\eta\)보다 큰 점을 최대한 고르면 반지름 \(\eta/2\)의 공들이 서로 겹치지 않고 반지름 \(1+\eta/2\)의 공 안에 듭니다. 부피비에서 점 수가 \((1+2/\eta)^d\) 이하입니다. 최대성 때문에 모든 구면점은 선택한 점 중 하나와 거리 \(\eta\) 이하입니다. \(\eta=1/4\)이면 \(9^d\)입니다.
부분공간의 정규직교기저를 \(U\)라 하고 \(M=U^TS^TSU-I\)라 쓰겠습니다. 임의 단위 \(x\)와 가까운 그물점 \(v\)에서
대칭행렬의 노름은 단위구면 이차형식의 최대 절댓값입니다. 따라서 \(\|M\|_2\le2\max_v|v^TMv|\)입니다. 각 그물점에 정리 1을 허용오차 \(\epsilon/2\)로 적용하면 실패확률 합이 \(2\cdot9^d e^{-s\epsilon^2/32}\le\delta\)입니다.
이제 \(r(x)=Ax-b\)에 임베딩을 적용합니다. 작은 문제의 최소성으로
직교 잔차를 이용한 피타고라스식과 최소 특이값 하한으로 계수 상한이 따릅니다. 전처리에는 \(SA=QR\), \(\|QR R^{-1}y\|=\|y\|\)를 임베딩 부등식 가운데에 넣고 양쪽을 나눕니다. 최소·최대 특이값의 비로 조건수 상한을 얻습니다. ∎
정리 3. 범위 탐색의 결정론적·기대 Frobenius 오차#
SVD 좌표에서 \(V^T\Omega=(\Omega_1^T,\Omega_2^T)^T\)로 나누고 \(\Omega_1\)을 첫 \(k\)행이라 합시다. 완전 행계수이면
독립 표준정규 \(\Omega\)와 \(\ell=k+p\), \(p\ge2\)에서는 5절의 기대 상한이 성립합니다.
증명. 직교좌표로 \(A=\operatorname{diag}(\Sigma_1,\Sigma_2)\)라 두어도 오차는 같습니다. \(Y\Omega_1^+=[\Sigma_1;\Sigma_2\Omega_2\Omega_1^+]\)이므로 이 행렬 뒤에 영 열들을 붙인 후보는 모두 \(Y\)의 열공간에 있고, \(A\)와의 차는 아래 블록 두 개 \(-\Sigma_2\Omega_2\Omega_1^+\) 및 \(\Sigma_2\)뿐입니다. 직교사영은 각 열의 거리를 최소화하므로 상한을 얻습니다. 영 특이값·직사각형에서는 영 블록을 함께 붙여 같은 계산을 합니다.
가우시안 직교불변성으로 두 \(\Omega\) 블록은 다시 독립 표준정규입니다. \(\Omega_1\)을 고정하면 행별 제곱기댓값에서 교차항은 0, 제곱항 평균은 1이므로 \(\mathbb E_{\Omega_2}\|\Sigma_2\Omega_2\Omega_1^+\|_F^2=\|\Sigma_2\|_F^2\|\Omega_1^+\|_F^2\)입니다.
남은 평균도 계산할 수 있습니다. \(G=\Omega_1\)의 \(i\)행을 다른 \(k-1\)행이 만드는 공간의 수직방향에 사영한 벡터를 \(w_i\)라 합시다. Gram 행렬의 Schur 보원에서 \([(GG^T)^{-1}]_{ii}=1/\|w_i\|^2\)입니다. 다른 행을 고정하면 수직공간 차원은 \(\ell-k+1=p+1\)이고 \(\|w_i\|^2\)는 그 개수의 표준정규 제곱합입니다. 이 밀도는 \(x^{(p+1)/2-1}e^{-x/2}/[2^{(p+1)/2}\Gamma((p+1)/2)]\)입니다.
적분에서 \(x^{-1}\)을 곱하고 부분적분 관계 \(\Gamma(a)=(a-1)\Gamma(a-1)\)를 쓰면 평균은 \(1/(p-1)\)입니다. 종속 행 사건은 연속밀도에서 영확률입니다. 대각을 합하여 \(\mathbb E\|G^+\|_F^2=k/(p-1)\)를 얻습니다. 앞 상한에 대입하고 \(\mathbb E Z\le\sqrt{\mathbb E Z^2}\)를 쓰면 결론입니다.
마지막 절단에는 \(\|A-QB_k\|_F^2=\|(I-QQ^T)A\|_F^2+\|B-B_k\|_F^2\)입니다. \(Q^TA_k\)는 계수 \(k\) 이하 후보이고 직교사영은 노름을 늘리지 않으므로 둘째 항은 \(\|A-A_k\|_F^2\) 이하입니다. ∎
정리 4. 레버리지의 기저 불변성#
열공간의 직교사영 \(P=UU^T\)에서 \(h_i=P_{ii}=\|U^Te_i\|^2\in[0,1]\), \(\sum_i h_i=r\)입니다.
증명. 성분곱으로 대각식이 나옵니다. \(e_i=Pe_i+(I-P)e_i\)의 두 항이 직교하므로 \(\|Pe_i\|\le1\)입니다. \(\sum_i\sum_jU_{ij}^2=\sum_j\|U_{:,j}\|^2=r\)입니다. 다른 정규직교기저는 \(UO\)이고 \(OO^T=I\)여서 같은 \(P\)를 줍니다. 완전 열계수에서는 \(P=X(X^TX)^{-1}X^T\)이므로 회귀의 hat 값과 일치합니다. ∎
정리 5. 성분별 최소 상대 후진오차#
7절의 berr 공식은 실수의 정확한 산술에서 최소 허용 \(\eta\)입니다.
증명. \((A+E)\widehat x=b+f\)이면 \(r=E\widehat x-f\)입니다. 따라서 \(|r_i|\le\eta d_i\), \(d_i=(|A||\widehat x|+|b|)_i\)가 필요합니다. \(d_i>0\)에서는
로 두면 \(\sum_jE_{ij}\widehat x_j-f_i=r_i\)이고 필요한 성분별 상한을 만족합니다. \(\operatorname{sign}0=0\)으로 둡니다. \(d_i=0\)이면 모든 \(a_{ij}\widehat x_j\)와 \(b_i\)가 0이어서 정확한 잔차도 0이며 그 행의 섭동은 0으로 둡니다. 따라서 최대 비율이 하한인 동시에 달성됩니다. ∎
실제로 확인한 것 |
정확한 수학적 의미 |
|---|---|
적은 시험 출력이 큰 방향을 담는다 |
범위 사영오차와 확률 가정 |
작은 회귀가 원래 잔차도 잘 맞춘다 |
확대 열공간 임베딩 |
좌표를 바꾸어 원래 문제를 푼다 |
스케치 전처리의 조건수 제한 |
계산해가 가까운 입력의 해이다 |
명시적으로 달성한 성분별 후진오차 |
빠른 계산의 결과도 원래 문제의 잔차와 오차 기준으로 읽어야 합니다. 다음 장부터는 해를 구하는 문제를 최적화의 관점에서 정리하며, 볼록성과 곡률이 주는 보증을 살펴봅니다. O1로 이어 읽기.