Least Squares TODO
Concept
Least squares is a method for an overdetermined system Ax=b — where there are more equations than unknowns and no exact solution exists — that finds the x minimizing the Euclidean norm of the residual, ||Ax-b||. Geometrically, this is the same as projecting b orthogonally onto the column space of A, and at the optimum the residual is orthogonal to the column space. Using this orthogonality condition yields the normal equations AᵀAx = Aᵀb, and the solution is unique when A's columns are linearly independent. Numerically, however, forming AᵀA directly squares the condition number and loses precision, so in practice it's safer to solve via QR decomposition or SVD. When the columns are nearly dependent or the data is noisy, adding a regularization term, as in ridge regression, stabilizes the solution.
Nearly every task that fits data to a model — regression, calibration, sensor correction — is least squares, and carelessly using the normal equations is a common source of coefficients that wobble due to condition-number issues. Understanding why the residual must be orthogonal also makes diagnosing results easier.
Code & Formula
# 최소제곱법(Least Squares) — 과결정계 Ax=b를 lstsq로 풀고, 정규방정식 AᵀAx=Aᵀb 및
# "잔차는 열공간과 직교한다"는 기하적 성질을 직접 검증한다.
import numpy as np
# 직선 y = a*x + c 를 5개의 잡음 섞인 점에 최소제곱으로 맞추는 과결정계 (미지수 2개, 식 5개)
x_data = np.array([0.0, 1.0, 2.0, 3.0, 4.0])
y_data = np.array([1.1, 2.9, 4.8, 7.2, 8.9]) # 대략 y ≈ 2x + 1 근처의 잡음 데이터
A = np.column_stack([x_data, np.ones_like(x_data)]) # [a, c]를 구하기 위한 설계행렬
b = y_data
x_lstsq, residuals, rank, sv = np.linalg.lstsq(A, b, rcond=None)
a_hat, c_hat = x_lstsq
print(f"lstsq 해: y ≈ {a_hat:.4f}*x + {c_hat:.4f}")
# 정규방정식으로 직접 풀어서 lstsq 결과와 일치하는지 확인 (교육적 검증용, 실무는 lstsq/QR 권장)
x_normal_eq = np.linalg.solve(A.T @ A, A.T @ b)
print(f"정규방정식(AᵀAx=Aᵀb) 해: {x_normal_eq}")
print(f"lstsq와 일치? {np.allclose(x_lstsq, x_normal_eq)}")
# 기하적 성질: 최적점에서 잔차 벡터는 A의 열공간과 직교 → Aᵀ(Ax-b) ≈ 0
residual = A @ x_lstsq - b
orthogonality = A.T @ residual
print(f"\n잔차 벡터: {np.round(residual, 4)}")
print(f"Aᵀ·잔차 (열공간과의 직교성, ≈0이어야 함): {np.round(orthogonality, 10)}")
Exercise
Deliberately construct a matrix with a large condition number, compute the least-squares solution three ways — solving the normal equations directly, via QR, and via SVD — and compare the error against the true value for each.
Practical Connection
In Verex, fitting LMSR's liquidity parameter or a slippage/fee model to historical trade data, or regressing gas cost against block parameters, all apply the same least-squares procedure and the same condition-number cautions.
Where it lands in Jayverse
- Verex: fit LMSR's liquidity parameter and the slippage/fee model via QR or SVD, not the normal equations. Log the condition number so a badly conditioned fit is visible instead of silently wobbling.
- Verex: add ridge regularization for the gas-cost-vs-block-parameter regression. Near-dependent columns there are a plausible place for accidentally noisy fee estimates to hide.
- Auditor / Number: publish the fitting method alongside any indicator derived this way. State QR/SVD and any regularization used, so consumers can tell a numerically stable fit from a fragile one.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| overdetermined | 미지수보다 식이 많아 과결정된 · 정확한 해가 없는 연립방정식을 가리킴. "an overdetermined system Ax=b" |
| orthogonal to | ~에 직교하는 · 최적점에서 잔차가 열공간과 수직이라는 뜻. "the residual is orthogonal to the column space" |
| condition number | 조건수 · 수치 계산에서 오차 민감도를 나타내는 값. "forming AᵀA directly squares the condition number" |
| wobble | 수치·결과가 불안정하게 흔들리다 · 조건수 문제로 계수가 튀는 현상. "coefficients that wobble due to condition-number issues" |
| stabilize | 안정시키다 · 정규화 항을 추가해 해를 안정시킨다는 뜻. "stabilizes the solution" |
| diagnose | 문제·원인을 진단하다 · 결과가 왜 그런지 파악하기 쉬워진다는 뜻. "makes diagnosing results easier" |
| QR (decomposition) | QR 분해(QR decomposition) · 행렬을 직교행렬과 상삼각행렬로 분해해 최소제곱을 수치적으로 안정하게 푸는 방법. "it's safer to solve via QR decomposition or SVD" |
| SVD | 특이값 분해(Singular Value Decomposition) · 조건수 문제를 피해 최소제곱 해를 구하는 또 다른 수치적 방법. "solve via QR decomposition or SVD" |
| LMSR | 로그 시장 스코어링 규칙(Logarithmic Market Scoring Rule) · 예측시장의 유동성 파라미터를 정하는 AMM 방식, Verex에서 적용 대상. "fitting LMSR's liquidity parameter or a slippage/fee model" |
| ridge regression | 릿지 회귀(ridge regression) · 정규화 항을 더해 거의 종속적인 열이나 잡음 있는 데이터에서 해를 안정시키는 기법. "adding a regularization term, as in ridge regression, stabilizes the solution" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.