47:"/_next/static/chunks/33yus346z0l_n.js" 48:"/_next/static/chunks/1r8ezocsukqp8.js" 49:"/_next/static/chunks/0iv56yrji_20j.js" 4a:"/_next/static/chunks/0wa9m1-tphf9u.js" 4b:"/_next/static/chunks/08cuqqn_f60pp.js" 4c:"/_next/static/chunks/3zdsl3f9b0--r.js" 4d:"/_next/static/chunks/2j22cxchii_xx.js" 4e:"/_next/static/chunks/3bgoyiso1rhn7.js" 4f:"/_next/static/chunks/01a-3hvnqu8wl.js" 50:"/_next/static/chunks/3m1xjj5kw5fie.js" 51:"/_next/static/chunks/0om3fkgfnicab.js" 52:"/_next/static/chunks/0gafyzg9j9yqj.js" 53:"/_next/static/chunks/20w4eaqlekefm.js" 54:"/_next/static/chunks/449--h5z1s6nq.js" 55:"/_next/static/chunks/3k2gyg36fnag_.js" 56:"/_next/static/chunks/18ggtgz2yf759.js" 57:"/_next/static/chunks/0hlb44ca7-4a2.js" 58:"/_next/static/chunks/253gnmj0-cj17.js" 59:"/_next/static/chunks/09nq57stwzkgf.js" 5a:"/_next/static/chunks/082jo-0ajazgr.js" 5b:"/_next/static/chunks/2ozcrjb_hh74t.js" 5c:"/_next/static/chunks/05i8en-x14ibi.js" 5d:"/_next/static/chunks/32izpn90gvm22.js" 5e:"/_next/static/chunks/0jbzid2v9xv3h.js" 5f:"/_next/static/chunks/0i3-eynrkvqi7.js" 60:"/_next/static/chunks/1tn-0fivsxsv1.js" 61:"/_next/static/chunks/34h36hyf_ggow.js" 62:"/_next/static/chunks/20329i6m_04t6.js" 63:"/_next/static/chunks/161uxd62cjny2.js" 64:"/_next/static/chunks/2k8pepwc4pxns.js" 65:I[593304,["$2c","$2d","$2e","$2f","$30","$31","$47","$48","$49","$4a","$4b","$4c","$4d","$4e","$4f","$50","$51","$52","$53","$54","$55","$56","$57","$58","$59","$5a","$5b","$5c","$5d","$5e","$5f","$60","$61","$62","$63","$64"],"OwnedHydration"] 66:T69f,import numpy as np def demonstrate_catastrophic_cancellation(): """ Demonstrates how subtracting nearly equal numbers destroys precision. """ # Case 1: sqrt(x+1) - sqrt(x) for large x x = 1e20 # Naive computation (WRONG for large x) naive_result = np.sqrt(x + 1) - np.sqrt(x) # Algebraically equivalent but numerically stable form: # sqrt(x+1) - sqrt(x) = 1 / (sqrt(x+1) + sqrt(x)) stable_result = 1.0 / (np.sqrt(x + 1) + np.sqrt(x)) # True value (computed with arbitrary precision) true_value = 5e-11 # approximately print(f"x = {x:.0e}") print(f"Naive result: {naive_result:.10e}") # Shows 0.0! print(f"Stable result: {stable_result:.10e}") # Correct answer print(f"Relative error (naive): {abs(naive_result - stable_result) / stable_result:.2%}") # Case 2: The classic quadratic formula failure # Solving x² - 10⁸x + 1 = 0 # Roots are approximately 10⁸ and 10⁻⁸ a, b, c = 1.0, -1e8, 1.0 discriminant = b**2 - 4*a*c # Standard formula (fails for the small root) x1_standard = (-b + np.sqrt(discriminant)) / (2*a) x2_standard = (-b - np.sqrt(discriminant)) / (2*a) # Stable computation using alternative form for small root x1_stable = (-b + np.sqrt(discriminant)) / (2*a) x2_stable = c / (a * x1_stable) # Uses Vieta's formula: x1 * x2 = c/a print(f" Quadratic formula comparison:") print(f"Large root - Standard: {x1_standard:.10e}, Stable: {x1_stable:.10e}") print(f"Small root - Standard: {x2_standard:.10e}, Stable: {x2_stable:.10e}") print(f"True small root ≈ 1e-8") demonstrate_catastrophic_cancellation()67:T8b3,import numpy as np from numpy.linalg import cond, svd, lstsq def analyze_condition_numbers(): """ Demonstrates condition number computation and its implications. """ np.random.seed(42) # Create a design matrix with controlled condition number n, p = 100, 5 # Well-conditioned case: X with orthonormal-ish columns X_good = np.random.randn(n, p) X_good, _ = np.linalg.qr(X_good) # Make columns orthonormal X_good *= np.sqrt(n) # Scale back # Ill-conditioned case: nearly collinear features X_bad = np.random.randn(n, p) X_bad[:, -1] = X_bad[:, 0] + 1e-8 * np.random.randn(n) # Near-duplicate column print("=== Condition Number Analysis === ") for name, X in [("Well-conditioned", X_good), ("Ill-conditioned", X_bad)]: # Compute singular values U, singular_values, Vt = svd(X, full_matrices=False) # Condition numbers kappa_X = cond(X) kappa_XtX = cond(X.T @ X) print(f"{name} Matrix:") print(f" Singular values: {singular_values}") print(f" κ(X) = {kappa_X:.2e}") print(f" κ(XᵀX) = {kappa_XtX:.2e}") print(f" κ(XᵀX) / κ(X)² = {kappa_XtX / kappa_X**2:.2f} (should be ≈1)") print(f" Expected digits lost solving normal equations: ~{np.log10(kappa_XtX):.1f}") print() # Demonstrate actual error amplification # Create true coefficients and generate data beta_true = np.array([1.0, 2.0, 3.0, 4.0, 5.0]) y = X @ beta_true # Solve via normal equations (potentially unstable) try: beta_normal = np.linalg.solve(X.T @ X, X.T @ y) except np.linalg.LinAlgError: beta_normal = np.full(p, np.nan) # Solve via SVD (stable) beta_svd = lstsq(X, y, rcond=None)[0] error_normal = np.linalg.norm(beta_normal - beta_true) error_svd = np.linalg.norm(beta_svd - beta_true) print(f" Reconstruction error (Normal Equations): {error_normal:.2e}") print(f" Reconstruction error (SVD): {error_svd:.2e}") print() analyze_condition_numbers()68:T78c,import numpy as np import matplotlib.pyplot as plt from numpy.linalg import cond, solve, lstsq def demonstrate_normal_equations_failure(): """ Shows how normal equations fail for polynomial regression while QR/SVD methods remain stable. """ np.random.seed(42) # Generate simple data n = 50 x = np.linspace(0, 1, n) y_true = np.sin(2 * np.pi * x) y = y_true + 0.1 * np.random.randn(n) degrees = [2, 5, 8, 10, 12, 14, 16] print("Polynomial Regression: Normal Equations vs SVD") print("=" * 65) print(f"{'Degree':<8} {'κ(X)':<12} {'κ(XᵀX)':<15} {'MSE Normal':<12} {'MSE SVD':<12}") print("-" * 65) for d in degrees: # Build Vandermonde matrix X = np.vander(x, d + 1, increasing=True) # Condition numbers kappa_X = cond(X) XtX = X.T @ X # Check if XtX is numerically singular try: kappa_XtX = cond(XtX) except: kappa_XtX = np.inf # Normal equations (potentially fails) try: Xty = X.T @ y beta_normal = solve(XtX, Xty) y_pred_normal = X @ beta_normal mse_normal = np.mean((y_pred_normal - y)**2) mse_normal_str = f"{mse_normal:.2e}" except np.linalg.LinAlgError: mse_normal_str = "FAILED" # SVD-based solution (robust) beta_svd = lstsq(X, y, rcond=None)[0] y_pred_svd = X @ beta_svd mse_svd = np.mean((y_pred_svd - y)**2) print(f"{d:<8} {kappa_X:<12.2e} {kappa_XtX:<15.2e} {mse_normal_str:<12} {mse_svd:<12.2e}") print() print("Observation: As degree increases, κ(XᵀX) explodes exponentially.") print("Normal equations become unreliable around degree 10-12.") print("SVD remains stable regardless of conditioning.") demonstrate_normal_equations_failure()69:Td50,import numpy as np from numpy.linalg import matrix_rank, cond, svd def diagnose_conditioning(X, feature_names=None): """ Comprehensive diagnostic for design matrix conditioning. Parameters: ----------- X : ndarray of shape (n_samples, n_features) Design matrix to analyze feature_names : list of str, optional Names of features for interpretable output Returns: -------- dict : Diagnostic information """ n, p = X.shape if feature_names is None: feature_names = [f"x{i}" for i in range(p)] # Basic properties U, s, Vt = svd(X, full_matrices=False) rank = matrix_rank(X) kappa = cond(X) # Identify problematic directions # Small singular values indicate near-linear-dependence sv_threshold = s[0] * 1e-10 # Relative threshold problematic_idx = np.where(s < sv_threshold)[0] # Analyze which features contribute to ill-conditioning # Look at right singular vectors corresponding to small singular values V = Vt.T diagnostics = { "shape": (n, p), "rank": rank, "condition_number": kappa, "singular_values": s, "log10_condition": np.log10(kappa) if kappa < np.inf else np.inf, } print("=== Design Matrix Conditioning Diagnostics ===") print(f"Shape: {n} samples × {p} features") print(f"Numerical rank: {rank} (expecting {min(n, p)})") print(f"Condition number: {kappa:.2e}") print(f"Log₁₀(κ): {diagnostics['log10_condition']:.1f}") print() # Singular value analysis print("Singular Value Spectrum:") print(f" Largest: {s[0]:.4e}") print(f" Smallest: {s[-1]:.4e}") print(f" Ratio: {s[0]/s[-1]:.4e}") print() # Check for scale disparity col_norms = np.linalg.norm(X, axis=0) scale_ratio = col_norms.max() / col_norms.min() print(f"Column Norm Disparity: {scale_ratio:.2e}") if scale_ratio > 100: print(" ⚠️ Consider standardizing features!") print() # Identify potential multicollinearity if len(problematic_idx) > 0: print("⚠️ Near-linear dependencies detected!") for idx in problematic_idx: # Which features contribute most to this null-space direction? v = V[:, idx] contributors = np.argsort(np.abs(v))[-3:][::-1] print(f" σ_{idx} = {s[idx]:.2e}: involves {[feature_names[i] for i in contributors]}") else: print("✓ No near-exact linear dependencies detected.") # Guidance print() print("Recommendations:") if kappa > 1e12: print(" 🔴 CRITICAL: Condition number too high for reliable double-precision.") print(" → Use regularization OR reformulate the problem") elif kappa > 1e8: print(" 🟠 WARNING: Use QR or SVD, avoid normal equations entirely.") elif kappa > 1e4: print(" 🟡 CAUTION: Use stable algorithms (QR preferred over normal equations).") else: print(" 🟢 GOOD: Standard algorithms should work reliably.") return diagnostics # Example usage np.random.seed(42) n, p = 100, 5 X = np.random.randn(n, p) X[:, 4] = X[:, 0] + X[:, 1] + 1e-8 * np.random.randn(n) # Introduce collinearity diagnose_conditioning(X, ["A", "B", "C", "D", "A+B (collinear)"])46:["$","$L65",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792320178014,"state":{"data":{"json":{"id":"seed_acb7f5511de2687342e6530243146abf","slug":"computational-considerations-linear-regression","category":"Machine Learning","topic":"Computational Considerations","title":"Computational Considerations in Linear Regression","description":"Master the computational aspects of linear regression implementation including numerical stability, QR decomposition, complexity analysis, online updates, and weighted least squares. Learn to implement regression algorithms that are both efficient and numerically robust.","difficulty":"ADVANCED","estimatedMinutes":90,"pages":[{"id":"seed_cc08b5f3b89ab17cc80cc1ae495a2ad1","title":"Numerical Stability","order":0,"content":[{"id":"opening-hook","title":"When Mathematics Meets Machine Precision","content":[{"data":{"content":"In the pristine world of pure mathematics, the formula **β = (XᵀX)⁻¹Xᵀy** provides an exact solution to linear regression. Given a design matrix X and target vector y, we simply compute the inverse and multiply—problem solved.\n\n**But computers don't live in that pristine world.**\n\nEvery computation happens with finite precision. Numbers are represented with approximately 16 significant decimal digits in standard double-precision floating-point format. Operations that seem mathematically innocuous—matrix inversion, solving linear systems, even simple subtraction—can catastrophically amplify tiny representation errors into results that are completely wrong."},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Hidden Danger","content":"A linear regression implementation that passes all unit tests can still produce completely wrong results in production. The difference? Real-world data often has subtle numerical properties that expose catastrophic instabilities in naive implementations. This page teaches you to recognize, diagnose, and prevent these failures.","variant":"warning"},"type":"callout"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand: (1) how floating-point arithmetic introduces errors, (2) what condition numbers reveal about numerical sensitivity, (3) why the normal equations approach fails for ill-conditioned problems, and (4) how to diagnose numerical stability issues before they corrupt your results.","variant":"info"},"type":"callout"}]},{"id":"floating-point-representation","title":"Floating-Point Representation","content":[{"data":{"content":"To understand numerical instability, we must first understand how computers represent real numbers. The IEEE 754 double-precision floating-point format is the standard representation used in virtually all scientific computing.\n\n**The Anatomy of a Float:**\n\nA 64-bit double-precision floating-point number consists of three components:\n\n- **Sign bit** (1 bit): Determines if the number is positive or negative\n- **Exponent** (11 bits): Encodes the magnitude as a power of 2 (biased by 1023)\n- **Mantissa/Significand** (52 bits): Stores the significant digits\n\nThe value represented is:\n\n$$(-1)^{\\text{sign}} \\times 1.\\text{mantissa} \\times 2^{\\text{exponent} - 1023}$$"},"type":"text"},{"data":{"icon":"Info","title":"The Hidden One","content":"Notice the '1.' before the mantissa. Since normalized binary numbers always start with 1, this leading 1 is implicit and not stored—giving us effectively 53 bits of precision for the significand. This is called the 'hidden bit' optimization.","variant":"note"},"type":"callout"},{"data":{"content":"**Machine Epsilon: The Fundamental Precision Limit**\n\nThe most important constant in numerical computing is **machine epsilon (ε_mach)**—the smallest positive number such that:\n\n$$1 + \\varepsilon_{\\text{mach}} \neq 1 \\text{ in floating-point}$$\n\nFor double precision: **ε_mach ≈ 2.22 × 10⁻¹⁶** (approximately 2⁻⁵²)\n\nThis means:\n- We have roughly **16 significant decimal digits** of precision\n- Numbers differing by less than ε_mach × |number| are indistinguishable\n- Every arithmetic operation introduces a relative error of at most ε_mach"},"type":"text"},{"data":{"rows":[["Half (float16)","16","10","≈ 9.77 × 10⁻⁴","~3-4"],["Single (float32)","32","23","≈ 1.19 × 10⁻⁷","~7"],["Double (float64)","64","52","≈ 2.22 × 10⁻¹⁶","~16"],["Extended (float80)","80","64","≈ 1.08 × 10⁻¹⁹","~19"]],"caption":"IEEE 754 Floating-Point Precision Levels","headers":["Format","Total Bits","Mantissa Bits","Machine Epsilon","Decimal Digits"]},"type":"table"},{"data":{"content":"**Catastrophic Cancellation: When Subtraction Destroys Precision**\n\nThe most dangerous operation in floating-point arithmetic is **subtraction of nearly equal numbers**. Consider computing:\n\n$$f(x) = \\sqrt{x+1} - \\sqrt{x}$$\n\nFor x = 10²⁰, mathematically this equals approximately 5 × 10⁻¹¹. But in floating-point:\n\n1. √(10²⁰ + 1) ≈ 10¹⁰ + 5 × 10⁻¹¹ (but this tiny difference is lost!)\n2. √(10²⁰) = 10¹⁰\n3. Subtraction yields 0 instead of 5 × 10⁻¹¹\n\n**This is catastrophic cancellation**—we lost *all* significant digits."},"type":"text"},{"data":{"fileName":"catastrophic_cancellation.py","languages":[{"code":"$66","label":"Python","value":"python"}],"showLineNumbers":true},"type":"code"},{"data":{"icon":"Lightbulb","title":"Numerical Stability Principle #1","content":"Never subtract nearly equal floating-point numbers if you can avoid it. Algebraically rearrange formulas to use addition instead, or use alternative formulations that avoid the cancellation entirely.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"condition-numbers","title":"Condition Numbers: Quantifying Sensitivity","content":[{"data":{"content":"The **condition number** is one of the most important concepts in numerical linear algebra. It quantifies how sensitive the output of a computation is to perturbations in the input—essentially measuring the *inherent difficulty* of a problem, independent of any algorithm used to solve it.\n\n**Definition: Matrix Condition Number**\n\nFor a square, invertible matrix A, the condition number with respect to the 2-norm is:\n\n$$\\kappa(A) = \\|A\\|_2 \\|A^{-1}\\|_2 = \\frac{\\sigma_{\\max}(A)}{\\sigma_{\\min}(A)}$$\n\nwhere σ_max and σ_min are the largest and smallest singular values of A.\n\nFor symmetric positive definite matrices (like XᵀX in least squares):\n\n$$\\kappa(A) = \\frac{\\lambda_{\\max}(A)}{\\lambda_{\\min}(A)}$$\n\nwhere λ_max and λ_min are the largest and smallest eigenvalues."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Intuition Behind Condition Numbers","content":"A condition number tells you: for every digit of precision you want in your answer, how many digits of precision do you need in your input? If κ(A) = 10⁸, you need 8 extra digits of precision just to preserve accuracy. With 16-digit double precision, you can only trust about 8 digits of your result.","variant":"note"},"type":"callout"},{"data":{"content":"**The Error Amplification Bound:**\n\nConsider solving the linear system Ax = b. If we perturb b by a small amount δb, the solution changes by δx where:\n\n$$\\frac{\\|\\delta x\\|}{\\|x\\|} \\leq \\kappa(A) \\cdot \\frac{\\|\\delta b\\|}{\\|b\\|}$$\n\nThis inequality is **tight**—there exist perturbations that achieve this worst case.\n\n**Interpretation:**\n- κ(A) = 1: Perfect conditioning (orthogonal matrices achieve this)\n- κ(A) = 10²: Lose ~2 digits of precision\n- κ(A) = 10⁸: Lose ~8 digits of precision\n- κ(A) = 10¹⁶+: Effectively singular—no reliable accuracy in double precision\n\n**Classification of Conditioning:**"},"type":"text"},{"data":{"rows":[["1 - 10","Well-conditioned","< 1 digit","Numerically safe, standard algorithms work"],["10 - 10⁴","Moderate conditioning","1-4 digits","Generally safe, monitor precision"],["10⁴ - 10⁸","Ill-conditioned","4-8 digits","Use numerically stable algorithms only"],["10⁸ - 10¹²","Severely ill-conditioned","8-12 digits","Results questionable, consider reformulation"],["> 10¹²","Near-singular","> 12 digits","Standard double precision unreliable"]],"caption":"Condition Number Classification","headers":["Condition Number κ(A)","Classification","Expected Precision Loss","Practical Interpretation"]},"type":"table"},{"data":{"content":"**Condition Number of XᵀX vs X:**\n\nHere's a critical insight for linear regression. The normal equations require forming XᵀX, but:\n\n$$\\kappa(X^\\top X) = \\kappa(X)^2$$\n\n**This is devastating!** If your design matrix has κ(X) = 10⁴ (moderately ill-conditioned but manageable), then κ(XᵀX) = 10⁸, which is severely ill-conditioned.\n\nThis squaring of the condition number is the fundamental reason why solving normal equations directly is often numerically unstable, and why we prefer methods like QR decomposition that work with X directly."},"type":"text"},{"data":{"fileName":"condition_number_analysis.py","languages":[{"code":"$67","label":"Python","value":"python"}],"showLineNumbers":true},"type":"code"}],"titleType":"number","titleNumber":2},{"id":"normal-equations-problem","title":"Why Normal Equations Fail","content":[{"data":{"content":"The **normal equations** provide a direct formula for the least squares solution:\n\n$$X^\\top X \\beta = X^\\top y \\implies \\beta = (X^\\top X)^{-1} X^\\top y$$\n\nWhile mathematically elegant, this approach has multiple numerical pitfalls that can lead to catastrophic failures in practice."},"type":"text"},{"data":{"items":["**Condition Number Squaring**: As shown, κ(XᵀX) = κ(X)². Moderate ill-conditioning becomes severe.","**Explicit Matrix Inversion**: Computing (XᵀX)⁻¹ is never recommended—it's numerically unstable and computationally inefficient.","**Loss of Orthogonality Information**: The product XᵀX loses geometric information about the column space of X.","**Near-Singularity Amplification**: If X has any near-zero singular values, XᵀX will have near-zero eigenvalues squared, making detection harder.","**Symmetry Exploitation Backfires**: While XᵀX is symmetric positive semi-definite (allowing Cholesky), the squaring effect dominates any savings."],"title":{"icon":"AlertCircle","text":"Numerical Problems with Normal Equations","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"content":"**A Concrete Failure Case:**\n\nConsider polynomial regression with high-degree polynomials. The design matrix has the form:\n\n$$X = \\begin{bmatrix} 1 & x_1 & x_1^2 & \\cdots & x_1^d \\\\ 1 & x_2 & x_2^2 & \\cdots & x_2^d \\\\ \\vdots & \\vdots & \\vdots & \\ddots & \\vdots \\\\ 1 & x_n & x_n^2 & \\cdots & x_n^d \\end{bmatrix}$$\n\nThis is known as a **Vandermonde matrix**, and they are notoriously ill-conditioned. For even moderate degree d ≈ 10-15 and typical data ranges, κ(X) can exceed 10¹⁶, making XᵀX essentially numerically rank-deficient."},"type":"text"},{"data":{"fileName":"normal_equations_failure.py","languages":[{"code":"$68","label":"Python","value":"python"}],"showLineNumbers":true},"type":"code"},{"data":{"icon":"AlertCircle","title":"Never Explicitly Invert XᵀX","content":"Even if normal equations are used, never compute (XᵀX)⁻¹ explicitly. At minimum, use Cholesky decomposition: factor XᵀX = LLᵀ, then solve Lz = Xᵀy followed by Lᵀβ = z. This is still twice as ill-conditioned as necessary, but avoids the numerical disaster of explicit inversion.","variant":"error"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"sources-of-ill-conditioning","title":"Sources of Ill-Conditioning in Practice","content":[{"data":{"content":"Understanding *why* design matrices become ill-conditioned helps you prevent the problem before it occurs. Here are the most common causes in real-world machine learning:\n\n**1. Multicollinearity: Correlated Features**\n\nWhen features are highly correlated (or nearly linearly dependent), the columns of X point in nearly the same direction. The \"narrower\" the column space of X, the smaller its minimum singular value, and the larger κ(X).\n\n*Example*: Including both Celsius and Fahrenheit temperature as features. Or GDP and GDP-per-capita in a country-level model."},"type":"text"},{"data":{"content":"**2. Scale Disparities: Features on Different Scales**\n\nIf one feature ranges from 0-1 and another from 0-10⁶, the columns have vastly different magnitudes. This creates artificial ill-conditioning that's easily fixed by standardization.\n\n*Example*: Using age (0-100) and annual income ($0-$10M) as raw features without scaling."},"type":"text"},{"data":{"content":"**3. Polynomial and Interaction Features**\n\nAs we saw, polynomial features create Vandermonde-like structures that are inherently ill-conditioned. Higher-order interaction terms exacerbate this.\n\n*Example*: Including x, x², x³, ..., x¹⁵ as features."},"type":"text"},{"data":{"content":"**4. High-Dimensional Settings (p ≈ n)**\n\nWhen the number of features approaches or exceeds the number of samples, XᵀX approaches singularity. The matrix may be technically invertible but with enormous condition number.\n\n*Example*: Gene expression data with 20,000 genes and 100 patients."},"type":"text"},{"data":{"content":"**5. Redundant or Constant Features**\n\nFeatures that are constant (zero variance) or exact linear combinations of other features create singular or near-singular XᵀX.\n\n*Example*: Including a feature that's always 1 alongside one-hot encoded categories that sum to 1."},"type":"text"},{"data":{"rows":[["Multicollinearity","Correlation matrix, VIF > 10","Remove correlated features, PCA, Ridge regression"],["Scale disparity","Feature variance comparison","Standardization (z-score) or normalization"],["Polynomial features","Condition number of Vandermonde","Orthogonal polynomials (Legendre, Chebyshev)"],["High dimensionality","p/n ratio > 0.5","Regularization (Ridge, Lasso), dimensionality reduction"],["Redundant features","Rank deficiency check","Remove constant/duplicate columns, use pivoted QR"]],"caption":"Ill-Conditioning Sources and Remedies","headers":["Source","Detection Method","Remedy"]},"type":"table"},{"data":{"fileName":"diagnose_conditioning.py","languages":[{"code":"$69","label":"Python","value":"python"}],"showLineNumbers":true},"type":"code"}],"titleType":"number","titleNumber":4},{"id":"numerical-stability-best-practices","title":"Numerical Stability Best Practices","content":[{"data":{"content":"Before diving into specific algorithms (QR decomposition, SVD), let's consolidate the general principles of numerical stability that every practitioner should internalize:"},"type":"text"},{"data":{"type":"ordered","items":["**Never explicitly invert matrices.** Instead of computing A⁻¹b, solve the linear system Ax = b using factorization (LU, Cholesky, QR).","**Avoid forming XᵀX when possible.** Work directly with X via QR or SVD decomposition to preserve the condition number.","**Standardize features before regression.** Subtract mean and divide by standard deviation to equalize column norms and reduce scale-induced ill-conditioning.","**Check condition numbers before solving.** If κ(X) > 10⁸, be suspicious of any result; if κ(X) > 10¹², use extended precision or regularization.","**Use pivoting in factorizations.** Pivoted QR and LU with partial pivoting are more robust than their unpivoted counterparts.","**Prefer backward-stable algorithms.** An algorithm is backward-stable if the computed solution is the exact solution to a slightly perturbed problem. QR and SVD are backward-stable; normal equations are not."],"title":{"icon":"CheckCircle","text":"Golden Rules of Numerical Linear Algebra","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**Backward Stability: The Gold Standard**\n\nA fundamental concept in numerical analysis is **backward stability**. An algorithm for computing f(x) is backward stable if, for any input x, it produces a result f̂(x) that is the *exact* answer to a slightly perturbed input:\n\n$$\\hat{f}(x) = f(x + \\delta x) \\text{ where } \\frac{\\|\\delta x\\|}{\\|x\\|} = O(\\varepsilon_{\\text{mach}})$$\n\n**Why this matters:** If your algorithm is backward stable, and your problem is well-conditioned, the result will be accurate. If the problem is ill-conditioned, the result will be inaccurate—but no better algorithm could do better with the same precision.\n\nQR factorization and the SVD are backward stable. Solving normal equations via Cholesky (even with pivoting) is not backward stable for least squares because the conditioning of XᵀX, not X, dominates."},"type":"text"},{"data":{"rows":[["Normal Equations (Cholesky)","Not backward stable","κ(XᵀX) = κ(X)²","Only when X is very well-conditioned and n >> p"],["QR Decomposition","Backward stable","κ(X)","Default choice for moderate-sized problems"],["SVD","Backward stable","κ(X)","Rank-deficient problems, need pseudoinverse"],["Modified Gram-Schmidt","Less stable than Householder QR","κ(X), can degrade","Educational purposes, iterative refinement available"],["Householder QR","Fully backward stable","κ(X)","Standard library implementation (LAPACK)"]],"caption":"Algorithm Stability Comparison for Least Squares","headers":["Method","Stability","Condition Dependence","When to Use"]},"type":"table"},{"data":{"icon":"Lightbulb","title":"The Practitioner's Rule","content":"In 99% of cases: use np.linalg.lstsq() or scipy.linalg.lstsq() which internally use QR or SVD. Never write beta = np.linalg.inv(X.T @ X) @ X.T @ y. The latter is a numerical disaster waiting to happen.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"summary-numerical-stability","title":"Summary: Numerical Stability","content":[{"data":{"content":"We've covered the foundational concepts of numerical stability in linear regression. These ideas are crucial for any production-quality implementation:"},"type":"text"},{"data":{"type":"ordered","items":["**Floating-point arithmetic has fundamental precision limits** — Machine epsilon (≈10⁻¹⁶ for doubles) bounds the relative accuracy of every operation.","**Catastrophic cancellation destroys accuracy** — Subtracting nearly equal numbers can lose all significant digits. Reformulate to avoid.","**Condition numbers quantify problem sensitivity** — κ(A) tells you how many digits of precision you'll lose. High condition = unreliable results.","**Normal equations square the condition number** — κ(XᵀX) = κ(X)² makes moderate ill-conditioning catastrophic. Avoid this approach.","**Ill-conditioning has identifiable causes** — Multicollinearity, scale disparity, high-degree polynomials, and high dimensionality all contribute.","**Use backward-stable algorithms** — QR and SVD preserve precision; normal equations do not. Always prefer the former in practice."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nNow that we understand *why* numerical stability matters and *why* normal equations fail, the next page introduces the **QR decomposition**—the industry-standard approach for solving least squares problems stably and efficiently. We'll derive the method from first principles and understand why it preserves conditioning where normal equations fail."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand the numerical challenges of linear regression and why naive implementations fail. This knowledge is essential for implementing reliable ML systems—the difference between a model that works in testing and one that works in production at scale.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":6}],"isLocked":false},{"id":"seed_2e8a100634acba71f9d69d243b21c1ac","title":"QR Decomposition Solution","order":1,"content":null,"isLocked":true},{"id":"seed_8f7a6e10bd46099a2b5e6949d6259d4d","title":"Complexity Analysis","order":2,"content":null,"isLocked":true},{"id":"seed_d626d357937e0d9615a995e9fb9fb771","title":"Online Updates","order":3,"content":null,"isLocked":true},{"id":"seed_01a54def315c67fdbf7d74a929a6037a","title":"Weighted Least Squares","order":4,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792320178008,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"computational-considerations-linear-regression"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"computational-considerations-linear-regression\"},\"type\":\"query\"}]"},{"dehydratedAt":1792320178015,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792320178012,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_acb7f5511de2687342e6530243146abf"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_acb7f5511de2687342e6530243146abf\"},\"type\":\"query\"}]"},{"dehydratedAt":1792320178015,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792320178013,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","get"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_2e8a100634acba71f9d69d243b21c1ac"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_2e8a100634acba71f9d69d243b21c1ac\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792320178015,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792320178013,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","getUserLike"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_2e8a100634acba71f9d69d243b21c1ac"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_2e8a100634acba71f9d69d243b21c1ac\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792320178015,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792320178013,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["highlights","getHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_2e8a100634acba71f9d69d243b21c1ac"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_2e8a100634acba71f9d69d243b21c1ac\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792320178015,"state":{"data":"$undefined","dataUpdateCount":0,"dataUpdatedAt":0,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"pending","fetchStatus":"fetching"},"queryKey":[["highlights","getPopularHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_2e8a100634acba71f9d69d243b21c1ac","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_2e8a100634acba71f9d69d243b21c1ac\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@6a"}]},"children":"$L6b"}]