06 moore penrose inverse

import%20marimo%0A%0A__generated_with%20%3D%20%220.24.0%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20pandas%20as%20pd%0A%20%20%20%20import%20plotly.graph_objects%20as%20go%0A%20%20%20%20from%20plotly.subplots%20import%20make_subplots%0A%0A%20%20%20%20return%20go%2C%20mo%2C%20np%2C%20pd%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Note%2006%3A%20Moore-Penrose%20Pseudoinverse%2C%20Least-Squares%2C%20and%20Minimum-Norm%20Solutions%0A%0A%20%20%20%20%26larr%3B%20Previous%20Note%3A%20%5B05%20Orthogonality%5D(05_orthogonality.py)%20%7C%20Next%20Note%3A%20%5B07%20Spectral%20Decomposition%5D(07_spectral_decomposition.py)%20%26rarr%3B%0A%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%20%5Ba%5D%20Why%20do%20you%20need%20to%20know%20these%20concepts%3F%0A%0A%20%20%20%20When%20solving%20a%20linear%20system%20%24%5Cmathbf%7BA%7D%5Cmathbf%7Bx%7D%20%3D%20%5Cmathbf%7Bb%7D%24%2C%20a%20square%2C%20full-rank%20matrix%20yields%20a%20unique%20solution%20via%20the%20standard%20inverse%20%24%5Cmathbf%7Bx%7D%20%3D%20%5Cmathbf%7BA%7D%5E%7B-1%7D%5Cmathbf%7Bb%7D%24.%20In%20practical%20machine%20learning%2C%20however%2C%20matrices%20are%20rarely%20square%20and%20invertible.%20Data%20matrices%20are%20typically%20tall%20(overdetermined%2C%20with%20more%20observations%20than%20features)%20or%20wide%20(underdetermined%2C%20with%20more%20parameters%20than%20observations).%0A%0A%20%20%20%20The%20**Moore-Penrose%20pseudoinverse**%20%24%5Cmathbf%7BA%7D%5E%2B%24%20generalizes%20matrix%20inversion%20to%20any%20rectangular%20or%20rank-deficient%20matrix%20%24%5Cmathbf%7BA%7D%20%5Cin%20%5Cmathbb%7BR%7D%5E%7Bm%20%5Ctimes%20n%7D%24.%20It%20guarantees%20a%20uniquely%20defined%2C%20optimal%20solution%3A%0A%20%20%20%201.%20For%20overdetermined%20systems%2C%20it%20provides%20the%20**least-squares%20solution**%20minimizing%20residual%20error%20%24%5C%7C%5Cmathbf%7BA%7D%5Cmathbf%7Bx%7D%20-%20%5Cmathbf%7Bb%7D%5C%7C_2%24.%0A%20%20%20%202.%20For%20underdetermined%20systems%2C%20it%20isolates%20the%20unique%20**minimum-norm%20solution**%20minimizing%20%24%5C%7C%5Cmathbf%7Bx%7D%5C%7C_2%24%20among%20all%20exact%20interpolators.%0A%20%20%20%203.%20For%20overparameterized%20deep%20models%20(%24p%20%5Cgg%20n%24)%2C%20gradient%20descent%20implicitly%20converges%20to%20this%20pseudoinverse%20solution%2C%20providing%20the%20foundation%20for%20understanding%20double%20descent.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%20%5Bb%5D%20Concept%20explanation%20with%20their%20role%20in%20ML%2FAI%2FStats%3F%0A%0A%20%20%20%20%23%23%23%20The%20Four%20Penrose%20Conditions%0A%0A%20%20%20%20For%20any%20matrix%20%24%5Cmathbf%7BA%7D%20%5Cin%20%5Cmathbb%7BR%7D%5E%7Bm%20%5Ctimes%20n%7D%24%2C%20there%20exists%20a%20unique%20matrix%20%24%5Cmathbf%7BA%7D%5E%2B%20%5Cin%20%5Cmathbb%7BR%7D%5E%7Bn%20%5Ctimes%20m%7D%24%20satisfying%20the%20four%20Moore-Penrose%20conditions%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cmathbf%7BA%7D%20%5Cmathbf%7BA%7D%5E%2B%20%5Cmathbf%7BA%7D%20%3D%20%5Cmathbf%7BA%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cmathbf%7BA%7D%5E%2B%20%5Cmathbf%7BA%7D%20%5Cmathbf%7BA%7D%5E%2B%20%3D%20%5Cmathbf%7BA%7D%5E%2B%0A%20%20%20%20%24%24%0A%0A%20%20%20%20%24%24%0A%20%20%20%20(%5Cmathbf%7BA%7D%20%5Cmathbf%7BA%7D%5E%2B)%5ET%20%3D%20%5Cmathbf%7BA%7D%20%5Cmathbf%7BA%7D%5E%2B%0A%20%20%20%20%24%24%0A%0A%20%20%20%20%24%24%0A%20%20%20%20(%5Cmathbf%7BA%7D%5E%2B%20%5Cmathbf%7BA%7D)%5ET%20%3D%20%5Cmathbf%7BA%7D%5E%2B%20%5Cmathbf%7BA%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20Conditions%203%20and%204%20have%20fundamental%20geometric%20interpretations%3A%0A%20%20%20%20*%20%24%5Cmathbf%7BP%7D_%7B%5Ctext%7Bcol%7D(%5Cmathbf%7BA%7D)%7D%20%3D%20%5Cmathbf%7BA%7D%5Cmathbf%7BA%7D%5E%2B%24%20is%20the%20symmetric%2C%20orthogonal%20projection%20operator%20onto%20the%20column%20space%20of%20%24%5Cmathbf%7BA%7D%24.%0A%20%20%20%20*%20%24%5Cmathbf%7BP%7D_%7B%5Ctext%7Brow%7D(%5Cmathbf%7BA%7D)%7D%20%3D%20%5Cmathbf%7BA%7D%5E%2B%5Cmathbf%7BA%7D%24%20is%20the%20symmetric%2C%20orthogonal%20projection%20operator%20onto%20the%20row%20space%20of%20%24%5Cmathbf%7BA%7D%24.%0A%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%23%20Closed-Form%20Expressions%20for%20Full-Rank%20Rectangular%20Cases%0A%0A%20%20%20%20When%20%24%5Cmathbf%7BA%7D%24%20has%20full%20rank%2C%20the%20pseudoinverse%20takes%20explicit%20algebraic%20forms%3A%0A%0A%20%20%20%20%23%23%23%23%20Full%20Column%20Rank%20(%24m%20%3E%20n%24%2C%20Overdetermined)%0A%0A%20%20%20%20The%20Gram%20matrix%20%24%5Cmathbf%7BA%7D%5ET%20%5Cmathbf%7BA%7D%20%5Cin%20%5Cmathbb%7BR%7D%5E%7Bn%20%5Ctimes%20n%7D%24%20is%20invertible.%20The%20pseudoinverse%20is%20the%20**left%20inverse**%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cmathbf%7BA%7D%5E%2B%20%3D%20(%5Cmathbf%7BA%7D%5ET%20%5Cmathbf%7BA%7D)%5E%7B-1%7D%20%5Cmathbf%7BA%7D%5ET%0A%20%20%20%20%24%24%0A%0A%20%20%20%20Notice%20that%20%24%5Cmathbf%7BA%7D%5E%2B%20%5Cmathbf%7BA%7D%20%3D%20(%5Cmathbf%7BA%7D%5ET%20%5Cmathbf%7BA%7D)%5E%7B-1%7D%20%5Cmathbf%7BA%7D%5ET%20%5Cmathbf%7BA%7D%20%3D%20%5Cmathbf%7BI%7D_n%24.%20The%20solution%20%24%5Chat%7B%5Cmathbf%7Bx%7D%7D%20%3D%20%5Cmathbf%7BA%7D%5E%2B%20%5Cmathbf%7Bb%7D%24%20minimizes%20the%20sum%20of%20squared%20residuals%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cmin_%7B%5Cmathbf%7Bx%7D%20%5Cin%20%5Cmathbb%7BR%7D%5En%7D%20%5C%7C%5Cmathbf%7BA%7D%5Cmathbf%7Bx%7D%20-%20%5Cmathbf%7Bb%7D%5C%7C_2%5E2%0A%20%20%20%20%24%24%0A%0A%20%20%20%20%23%23%23%23%20Full%20Row%20Rank%20(%24m%20%3C%20n%24%2C%20Underdetermined)%0A%0A%20%20%20%20The%20matrix%20%24%5Cmathbf%7BA%7D%20%5Cmathbf%7BA%7D%5ET%20%5Cin%20%5Cmathbb%7BR%7D%5E%7Bm%20%5Ctimes%20m%7D%24%20is%20invertible.%20The%20pseudoinverse%20is%20the%20**right%20inverse**%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cmathbf%7BA%7D%5E%2B%20%3D%20%5Cmathbf%7BA%7D%5ET%20(%5Cmathbf%7BA%7D%20%5Cmathbf%7BA%7D%5ET)%5E%7B-1%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20Notice%20that%20%24%5Cmathbf%7BA%7D%20%5Cmathbf%7BA%7D%5E%2B%20%3D%20%5Cmathbf%7BA%7D%20%5Cmathbf%7BA%7D%5ET%20(%5Cmathbf%7BA%7D%20%5Cmathbf%7BA%7D%5ET)%5E%7B-1%7D%20%3D%20%5Cmathbf%7BI%7D_m%24.%20The%20system%20%24%5Cmathbf%7BA%7D%5Cmathbf%7Bx%7D%20%3D%20%5Cmathbf%7Bb%7D%24%20has%20infinitely%20many%20solutions%2C%20and%20%24%5Chat%7B%5Cmathbf%7Bx%7D%7D%20%3D%20%5Cmathbf%7BA%7D%5E%2B%20%5Cmathbf%7Bb%7D%24%20selects%20the%20unique%20solution%20with%20the%20smallest%20Euclidean%20norm%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cmin_%7B%5Cmathbf%7Bx%7D%20%5Cin%20%5Cmathbb%7BR%7D%5En%7D%20%5C%7C%5Cmathbf%7Bx%7D%5C%7C_2%20%5Cquad%20%5Ctext%7Bsubject%20to%7D%20%5Cquad%20%5Cmathbf%7BA%7D%5Cmathbf%7Bx%7D%20%3D%20%5Cmathbf%7Bb%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%23%20General%20Construction%20via%20Singular%20Value%20Decomposition%20(SVD)%0A%0A%20%20%20%20For%20arbitrary%20rank%20%24r%20%5Cleq%20%5Cmin(m%2C%20n)%24%2C%20the%20pseudoinverse%20is%20computed%20universally%20via%20the%20Singular%20Value%20Decomposition%20%24%5Cmathbf%7BA%7D%20%3D%20%5Cmathbf%7BU%7D%20%5Cmathbf%7B%5CSigma%7D%20%5Cmathbf%7BV%7D%5ET%24%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cmathbf%7BA%7D%5E%2B%20%3D%20%5Cmathbf%7BV%7D%20%5Cmathbf%7B%5CSigma%7D%5E%2B%20%5Cmathbf%7BU%7D%5ET%0A%20%20%20%20%24%24%0A%0A%20%20%20%20where%20%24%5Cmathbf%7B%5CSigma%7D%5E%2B%20%5Cin%20%5Cmathbb%7BR%7D%5E%7Bn%20%5Ctimes%20m%7D%24%20is%20obtained%20by%20reciprocating%20non-zero%20singular%20values%20and%20transposing%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Csigma_i%5E%2B%20%3D%20%5Cbegin%7Bcases%7D%20%5Cfrac%7B1%7D%7B%5Csigma_i%7D%20%26%20%5Ctext%7Bif%20%7D%20%5Csigma_i%20%3E%200%20%5C%5C%200%20%26%20%5Ctext%7Bif%20%7D%20%5Csigma_i%20%3D%200%20%5Cend%7Bcases%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%23%20Implicit%20Bias%20in%20Overparameterized%20Models%20and%20Double%20Descent%0A%0A%20%20%20%20In%20modern%20deep%20learning%20architectures%2C%20the%20number%20of%20parameters%20%24p%24%20frequently%20exceeds%20the%20number%20of%20training%20samples%20%24n%24%20(%24p%20%5Cgg%20n%24).%20When%20training%20an%20overparameterized%20linear%20model%20on%20a%20regression%20task%20using%20gradient%20descent%20initialized%20at%20zero%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cmathbf%7Bw%7D_%7Bt%2B1%7D%20%3D%20%5Cmathbf%7Bw%7D_t%20-%20%5Ceta%20%5Cmathbf%7BX%7D%5ET%20(%5Cmathbf%7BX%7D%5Cmathbf%7Bw%7D_t%20-%20%5Cmathbf%7By%7D)%2C%20%5Cquad%20%5Cmathbf%7Bw%7D_0%20%3D%20%5Cmathbf%7B0%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20Because%20all%20gradient%20updates%20lie%20in%20the%20span%20of%20the%20data%20rows%20%24%5Ctext%7Brow%7D(%5Cmathbf%7BX%7D)%24%2C%20gradient%20descent%20converges%20to%20the%20unique%20minimum%20%24L_2%24-norm%20interpolating%20solution%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cmathbf%7Bw%7D%5E*%20%3D%20%5Cmathbf%7BX%7D%5E%2B%20%5Cmathbf%7By%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20This%20implicit%20regularization%20explains%20why%20modern%20overparameterized%20models%20can%20interpolate%20training%20data%20without%20catastrophic%20overfitting%2C%20a%20phenomenon%20linked%20to%20benign%20overfitting%20and%20double%20descent.%0A%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%23%20Ridge%20Regularization%20Limit%20(Tikhonov%20Regularization)%0A%0A%20%20%20%20To%20address%20ill-conditioned%20or%20rank-deficient%20systems%2C%20ridge%20regression%20introduces%20an%20%24L_2%24%20penalty%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cmathbf%7Bw%7D_%5Clambda%20%3D%20(%5Cmathbf%7BX%7D%5ET%20%5Cmathbf%7BX%7D%20%2B%20%5Clambda%20%5Cmathbf%7BI%7D)%5E%7B-1%7D%20%5Cmathbf%7BX%7D%5ET%20%5Cmathbf%7By%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20As%20the%20regularization%20parameter%20vanishes%20(%24%5Clambda%20%5Cto%200%5E%2B%24)%2C%20the%20ridge%20solution%20converges%20continuously%20to%20the%20Moore-Penrose%20pseudoinverse%20solution%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Clim_%7B%5Clambda%20%5Cto%200%5E%2B%7D%20(%5Cmathbf%7BX%7D%5ET%20%5Cmathbf%7BX%7D%20%2B%20%5Clambda%20%5Cmathbf%7BI%7D)%5E%7B-1%7D%20%5Cmathbf%7BX%7D%5ET%20%3D%20%5Cmathbf%7BX%7D%5E%2B%0A%20%20%20%20%24%24%0A%0A%20%20%20%20This%20establishes%20that%20unregularized%20pseudoinverse%20interpolation%20is%20the%20structural%20limit%20of%20%24L_2%24%20regularization.%0A%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%23%20Linear%20Probing%20of%20Frozen%20Representations%0A%0A%20%20%20%20When%20evaluating%20foundation%20models%20(such%20as%20CLIP%2C%20BERT%2C%20or%20DINO)%2C%20researchers%20freeze%20the%20pre-trained%20feature%20extractor%20and%20train%20a%20linear%20classification%20or%20regression%20head.%20The%20optimal%20weights%20%24%5Cmathbf%7BW%7D%5E*%24%20can%20be%20found%20in%20closed%20form%20via%20the%20pseudoinverse%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cmathbf%7BW%7D%5E*%20%3D%20%5Cmathbf%7BZ%7D%5E%2B%20%5Cmathbf%7BY%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20where%20%24%5Cmathbf%7BZ%7D%20%5Cin%20%5Cmathbb%7BR%7D%5E%7BN%20%5Ctimes%20d%7D%24%20contains%20the%20extracted%20embeddings%20and%20%24%5Cmathbf%7BY%7D%20%5Cin%20%5Cmathbb%7BR%7D%5E%7BN%20%5Ctimes%20C%7D%24%20represents%20the%20target%20labels.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%20%5Bc%5D%20Interactive%20Visualizations%3A%20Overdetermined%20vs%20Underdetermined%20Systems%0A%0A%20%20%20%20The%20two%20figures%20below%20illustrate%20the%20geometric%20duality%20of%20the%20pseudoinverse%3A%0A%20%20%20%201.%20**Overdetermined%20System%20(3D)**%3A%20Target%20vector%20%24%5Cmathbf%7Bb%7D%24%20projected%20orthogonally%20onto%20the%202D%20column%20space%20%24%5Ctext%7Bcol%7D(%5Cmathbf%7BA%7D)%24.%20The%20residual%20%24%5Cmathbf%7Br%7D%20%3D%20%5Cmathbf%7Bb%7D%20-%20%5Cmathbf%7BA%7D%5Cmathbf%7Bx%7D%5E%2B%24%20is%20strictly%20perpendicular%20to%20the%20plane.%0A%20%20%20%202.%20**Underdetermined%20System%20(2D)**%3A%20The%20affine%20line%20of%20valid%20solutions%20%24%5Cmathbf%7BA%7D%5Cmathbf%7Bx%7D%20%3D%20%5Cmathbf%7Bb%7D%24.%20The%20pseudoinverse%20selects%20%24%5Cmathbf%7Bx%7D%5E%2B%20%3D%20%5Cmathbf%7BA%7D%5E%2B%20%5Cmathbf%7Bb%7D%24%2C%20which%20is%20the%20unique%20point%20on%20the%20line%20closest%20to%20the%20origin.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(go%2C%20np)%3A%0A%20%20%20%20%23%20Panel%201%3A%20Overdetermined%20System%20(3%20equations%2C%202%20variables)%0A%20%20%20%20%23%20A%20has%202%20columns%20in%20R%5E3%2C%20b%20is%20outside%20the%20column%20space%0A%20%20%20%20a1%20%3D%20np.array(%5B1.5%2C%200.2%2C%200.5%5D)%0A%20%20%20%20a2%20%3D%20np.array(%5B0.3%2C%201.4%2C%200.4%5D)%0A%20%20%20%20a_over%20%3D%20np.column_stack(%5Ba1%2C%20a2%5D)%0A%20%20%20%20b_over%20%3D%20np.array(%5B1.8%2C%201.6%2C%202.2%5D)%0A%0A%20%20%20%20%23%20Least%20squares%20projection%3A%20x_hat%20%3D%20pinv(A)%20%40%20b%0A%20%20%20%20x_hat%20%3D%20np.linalg.pinv(a_over)%20%40%20b_over%0A%20%20%20%20b_proj%20%3D%20a_over%20%40%20x_hat%0A%20%20%20%20residual%20%3D%20b_over%20-%20b_proj%0A%0A%20%20%20%20%23%20Generate%20grid%20for%20the%20column%20space%20plane%0A%20%20%20%20u_grid%20%3D%20np.linspace(-0.2%2C%201.5%2C%2015)%0A%20%20%20%20v_grid%20%3D%20np.linspace(-0.2%2C%201.5%2C%2015)%0A%20%20%20%20u_mesh%2C%20v_mesh%20%3D%20np.meshgrid(u_grid%2C%20v_grid)%0A%20%20%20%20plane_x%20%3D%20a1%5B0%5D%20*%20u_mesh%20%2B%20a2%5B0%5D%20*%20v_mesh%0A%20%20%20%20plane_y%20%3D%20a1%5B1%5D%20*%20u_mesh%20%2B%20a2%5B1%5D%20*%20v_mesh%0A%20%20%20%20plane_z%20%3D%20a1%5B2%5D%20*%20u_mesh%20%2B%20a2%5B2%5D%20*%20v_mesh%0A%0A%20%20%20%20%23%203D%20Figure%20for%20Overdetermined%20System%0A%20%20%20%20fig_3d%20%3D%20go.Figure()%0A%0A%20%20%20%20%23%20Column%20space%20surface%0A%20%20%20%20fig_3d.add_trace(%0A%20%20%20%20%20%20%20%20go.Surface(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dplane_x%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dplane_y%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20z%3Dplane_z%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20opacity%3D0.45%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20colorscale%3D%5B%5B0%2C%20%22%2393c5fd%22%5D%2C%20%5B1%2C%20%22%233b82f6%22%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20showscale%3DFalse%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22col(A)%20Plane%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Basis%20vector%20a1%0A%20%20%20%20fig_3d.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter3d(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3D%5B0%2C%20a1%5B0%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3D%5B0%2C%20a1%5B1%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20z%3D%5B0%2C%20a1%5B2%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%2Bmarkers%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%232563eb%22%2C%20width%3D6)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20marker%3Ddict(size%3D4)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Basis%20a1%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Basis%20vector%20a2%0A%20%20%20%20fig_3d.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter3d(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3D%5B0%2C%20a2%5B0%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3D%5B0%2C%20a2%5B1%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20z%3D%5B0%2C%20a2%5B2%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%2Bmarkers%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%2306b6d4%22%2C%20width%3D6)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20marker%3Ddict(size%3D4)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Basis%20a2%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Target%20vector%20b%0A%20%20%20%20fig_3d.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter3d(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3D%5B0%2C%20b_over%5B0%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3D%5B0%2C%20b_over%5B1%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20z%3D%5B0%2C%20b_over%5B2%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%2Bmarkers%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%23dc2626%22%2C%20width%3D7)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20marker%3Ddict(size%3D5%2C%20color%3D%22%23dc2626%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Target%20b%20(Inconsistent)%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Projected%20vector%20b_hat%20%3D%20A%20x_hat%0A%20%20%20%20fig_3d.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter3d(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3D%5B0%2C%20b_proj%5B0%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3D%5B0%2C%20b_proj%5B1%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20z%3D%5B0%2C%20b_proj%5B2%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%2Bmarkers%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%2316a34a%22%2C%20width%3D7)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20marker%3Ddict(size%3D5%2C%20color%3D%22%2316a34a%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Projection%20b_hat%20%3D%20A%20x%5E%2B%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Orthogonal%20residual%20vector%20connecting%20b_proj%20to%20b_over%0A%20%20%20%20fig_3d.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter3d(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3D%5Bb_proj%5B0%5D%2C%20b_over%5B0%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3D%5Bb_proj%5B1%5D%2C%20b_over%5B1%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20z%3D%5Bb_proj%5B2%5D%2C%20b_over%5B2%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%2Bmarkers%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%23d97706%22%2C%20width%3D5%2C%20dash%3D%22dash%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20marker%3Ddict(size%3D4%2C%20color%3D%22%23d97706%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Residual%20r%20%3D%20b%20-%20A%20x%5E%2B%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20)%0A%0A%20%20%20%20fig_3d.update_layout(%0A%20%20%20%20%20%20%20%20template%3D%22plotly_white%22%2C%0A%20%20%20%20%20%20%20%20title%3D%22Overdetermined%20System%3A%20Least-Squares%20Orthogonal%20Projection%20onto%20col(A)%22%2C%0A%20%20%20%20%20%20%20%20height%3D480%2C%0A%20%20%20%20%20%20%20%20margin%3Ddict(l%3D20%2C%20r%3D20%2C%20t%3D50%2C%20b%3D20)%2C%0A%20%20%20%20%20%20%20%20scene%3Ddict(%0A%20%20%20%20%20%20%20%20%20%20%20%20xaxis_title%3D%22X%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20yaxis_title%3D%22Y%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20zaxis_title%3D%22Z%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20camera%3Ddict(eye%3Ddict(x%3D1.6%2C%20y%3D-1.5%2C%20z%3D1.2))%2C%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20legend%3Ddict(orientation%3D%22h%22%2C%20yanchor%3D%22bottom%22%2C%20y%3D-0.15%2C%20xanchor%3D%22center%22%2C%20x%3D0.5)%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Panel%202%3A%20Underdetermined%20System%20(1%20equation%2C%202%20unknowns%3A%202*x1%20%2B%203*x2%20%3D%206)%0A%20%20%20%20a_under%20%3D%20np.array(%5B%5B2.0%2C%203.0%5D%5D)%0A%20%20%20%20b_val%20%3D%206.0%0A%20%20%20%20x_min_norm%20%3D%20np.linalg.pinv(a_under)%20%40%20np.array(%5Bb_val%5D)%0A%0A%20%20%20%20x1_vals%20%3D%20np.linspace(-1.0%2C%204.0%2C%20200)%0A%20%20%20%20x2_vals%20%3D%20(b_val%20-%20a_under%5B0%2C%200%5D%20*%20x1_vals)%20%2F%20a_under%5B0%2C%201%5D%0A%0A%20%20%20%20%23%20Sample%20alternate%20feasible%20points%0A%20%20%20%20sample_x1%20%3D%20np.array(%5B0.0%2C%201.5%2C%203.0%5D)%0A%20%20%20%20sample_x2%20%3D%20(b_val%20-%20a_under%5B0%2C%200%5D%20*%20sample_x1)%20%2F%20a_under%5B0%2C%201%5D%0A%0A%20%20%20%20fig_2d%20%3D%20go.Figure()%0A%0A%20%20%20%20%23%20Solution%20line%0A%20%20%20%20fig_2d.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dx1_vals%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dx2_vals%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%232563eb%22%2C%20width%3D3)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Affine%20Solution%20Set%3A%202x_1%20%2B%203x_2%20%3D%206%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Origin%0A%20%20%20%20fig_2d.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3D%5B0%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3D%5B0%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22markers%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20marker%3Ddict(color%3D%22%2364748b%22%2C%20size%3D9)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Origin%20(0%2C%200)%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Orthogonal%20segment%20from%20origin%20to%20minimum-norm%20solution%0A%20%20%20%20fig_2d.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3D%5B0%2C%20x_min_norm%5B0%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3D%5B0%2C%20x_min_norm%5B1%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%2Bmarkers%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%2316a34a%22%2C%20width%3D4)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20marker%3Ddict(color%3D%22%2316a34a%22%2C%20size%3D9)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3Df%22Min-Norm%20Solution%20x%5E%2B%3A%20%5B%7Bx_min_norm%5B0%5D%3A.2f%7D%2C%20%7Bx_min_norm%5B1%5D%3A.2f%7D%5D%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Alternate%20feasible%20points%0A%20%20%20%20fig_2d.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dsample_x1%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dsample_x2%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22markers%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20marker%3Ddict(color%3D%22%23d97706%22%2C%20size%3D8%2C%20symbol%3D%22diamond%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Alternative%20Feasible%20Solutions%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Dashed%20segments%20from%20origin%20to%20alternative%20solutions%0A%20%20%20%20for%20sx%2C%20sy%20in%20zip(sample_x1%2C%20sample_x2)%3A%0A%20%20%20%20%20%20%20%20fig_2d.add_trace(%0A%20%20%20%20%20%20%20%20%20%20%20%20go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20x%3D%5B0%2C%20sx%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20y%3D%5B0%2C%20sy%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%23cbd5e1%22%2C%20dash%3D%22dot%22%2C%20width%3D1.5)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20showlegend%3DFalse%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20norm_min%20%3D%20float(np.linalg.norm(x_min_norm))%0A%20%20%20%20fig_2d.update_layout(%0A%20%20%20%20%20%20%20%20template%3D%22plotly_white%22%2C%0A%20%20%20%20%20%20%20%20title%3Df%22Underdetermined%20System%3A%20Minimum-Norm%20Solution%20(%7C%7Cx%5E%2B%7C%7C_2%20%3D%20%7Bnorm_min%3A.3f%7D)%22%2C%0A%20%20%20%20%20%20%20%20height%3D450%2C%0A%20%20%20%20%20%20%20%20margin%3Ddict(l%3D40%2C%20r%3D40%2C%20t%3D50%2C%20b%3D40)%2C%0A%20%20%20%20%20%20%20%20xaxis%3Ddict(range%3D%5B-1.0%2C%204.0%5D%2C%20zeroline%3DTrue%2C%20zerolinecolor%3D%22%23cbd5e1%22%2C%20gridcolor%3D%22%23f1f5f9%22)%2C%0A%20%20%20%20%20%20%20%20yaxis%3Ddict(range%3D%5B-1.0%2C%203.0%5D%2C%20zeroline%3DTrue%2C%20zerolinecolor%3D%22%23cbd5e1%22%2C%20gridcolor%3D%22%23f1f5f9%22)%2C%0A%20%20%20%20%20%20%20%20legend%3Ddict(orientation%3D%22h%22%2C%20yanchor%3D%22bottom%22%2C%20y%3D-0.25%2C%20xanchor%3D%22center%22%2C%20x%3D0.5)%2C%0A%20%20%20%20)%0A%20%20%20%20return%20fig_2d%2C%20fig_3d%0A%0A%0A%40app.cell%0Adef%20_(fig_3d%2C%20mo)%3A%0A%20%20%20%20mo.ui.plotly(fig_3d)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(fig_2d%2C%20mo)%3A%0A%20%20%20%20mo.ui.plotly(fig_2d)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%20%5Bd%5D%20Code%20Examples%0A%0A%20%20%20%20%23%23%23%20Example%201%3A%20Numerical%20Verification%20of%20the%20Four%20Penrose%20Conditions%0A%0A%20%20%20%20Below%2C%20we%20construct%20a%20rank-deficient%20rectangular%20matrix%20%24%5Cmathbf%7BA%7D%20%5Cin%20%5Cmathbb%7BR%7D%5E%7B4%20%5Ctimes%203%7D%24%20with%20rank%202.%20We%20construct%20its%20pseudoinverse%20using%20both%20SVD%20and%20NumPy's%20%60np.linalg.pinv%60%2C%20verifying%3A%0A%20%20%20%201.%20%24%5Cmathbf%7BA%7D%5Cmathbf%7BA%7D%5E%2B%5Cmathbf%7BA%7D%20%3D%20%5Cmathbf%7BA%7D%24%0A%20%20%20%202.%20%24%5Cmathbf%7BA%7D%5E%2B%5Cmathbf%7BA%7D%5Cmathbf%7BA%7D%5E%2B%20%3D%20%5Cmathbf%7BA%7D%5E%2B%24%0A%20%20%20%203.%20%24(%5Cmathbf%7BA%7D%5Cmathbf%7BA%7D%5E%2B)%5ET%20%3D%20%5Cmathbf%7BA%7D%5Cmathbf%7BA%7D%5E%2B%24%0A%20%20%20%204.%20%24(%5Cmathbf%7BA%7D%5E%2B%5Cmathbf%7BA%7D)%5ET%20%3D%20%5Cmathbf%7BA%7D%5E%2B%5Cmathbf%7BA%7D%24%0A%20%20%20%205.%20Agreement%20between%20SVD-derived%20pseudoinverse%20and%20%60np.linalg.pinv%60%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20%23%20Seed%20for%20reproducibility%0A%20%20%20%20rng%20%3D%20np.random.default_rng(42)%0A%0A%20%20%20%20%23%20Construct%20rank-deficient%204x3%20matrix%20with%20rank%202%0A%20%20%20%20basis_cols%20%3D%20rng.standard_normal((4%2C%202))%0A%20%20%20%20third_col%20%3D%200.5%20*%20basis_cols%5B%3A%2C%200%5D%20%2B%200.8%20*%20basis_cols%5B%3A%2C%201%5D%0A%20%20%20%20a_mat%20%3D%20np.column_stack(%5Bbasis_cols%2C%20third_col%5D)%0A%0A%20%20%20%20%23%20Method%201%3A%20SVD%20construction%20of%20pseudoinverse%0A%20%20%20%20u%2C%20s%2C%20vt%20%3D%20np.linalg.svd(a_mat%2C%20full_matrices%3DFalse)%0A%20%20%20%20tol%20%3D%201e-12%0A%20%20%20%20s_inv%20%3D%20np.array(%5B1.0%20%2F%20val%20if%20val%20%3E%20tol%20else%200.0%20for%20val%20in%20s%5D)%0A%20%20%20%20pinv_svd%20%3D%20vt.T%20%40%20np.diag(s_inv)%20%40%20u.T%0A%0A%20%20%20%20%23%20Method%202%3A%20NumPy%20pinv%0A%20%20%20%20pinv_numpy%20%3D%20np.linalg.pinv(a_mat)%0A%0A%20%20%20%20%23%201.%20Condition%201%3A%20A%20A%2B%20A%20%3D%3D%20A%0A%20%20%20%20c1_err%20%3D%20float(np.max(np.abs(a_mat%20%40%20pinv_svd%20%40%20a_mat%20-%20a_mat)))%0A%0A%20%20%20%20%23%202.%20Condition%202%3A%20A%2B%20A%20A%2B%20%3D%3D%20A%2B%0A%20%20%20%20c2_err%20%3D%20float(np.max(np.abs(pinv_svd%20%40%20a_mat%20%40%20pinv_svd%20-%20pinv_svd)))%0A%0A%20%20%20%20%23%203.%20Condition%203%3A%20(A%20A%2B)%5ET%20%3D%3D%20A%20A%2B%0A%20%20%20%20aa_plus%20%3D%20a_mat%20%40%20pinv_svd%0A%20%20%20%20c3_err%20%3D%20float(np.max(np.abs(aa_plus.T%20-%20aa_plus)))%0A%0A%20%20%20%20%23%204.%20Condition%204%3A%20(A%2B%20A)%5ET%20%3D%3D%20A%2B%20A%0A%20%20%20%20a_plus_a%20%3D%20pinv_svd%20%40%20a_mat%0A%20%20%20%20c4_err%20%3D%20float(np.max(np.abs(a_plus_a.T%20-%20a_plus_a)))%0A%0A%20%20%20%20%23%205.%20SVD%20vs%20NumPy%20discrepancy%0A%20%20%20%20svd_vs_numpy_err%20%3D%20float(np.max(np.abs(pinv_svd%20-%20pinv_numpy)))%0A%0A%20%20%20%20penrose_results%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%22Penrose%20Condition%20%2F%20Verification%22%3A%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%221.%20A%20A%2B%20A%20%3D%3D%20A%20(max%20error)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%222.%20A%2B%20A%20A%2B%20%3D%3D%20A%2B%20(max%20error)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%223.%20(A%20A%2B)%5ET%20%3D%3D%20A%20A%2B%20(symmetry%20error)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%224.%20(A%2B%20A)%5ET%20%3D%3D%20A%2B%20A%20(symmetry%20error)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Manual%20SVD%20vs%20np.linalg.pinv%20discrepancy%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Matrix%20rank%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Matrix%20shape%20(m%2C%20n)%22%2C%0A%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20%20%20%20%20%22Value%22%3A%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7Bc1_err%3A.2e%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7Bc2_err%3A.2e%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7Bc3_err%3A.2e%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7Bc4_err%3A.2e%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7Bsvd_vs_numpy_err%3A.2e%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20str(np.linalg.matrix_rank(a_mat))%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7Ba_mat.shape%5B0%5D%7D%20x%20%7Ba_mat.shape%5B1%5D%7D%22%2C%0A%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20%7D%0A%20%20%20%20return%20(penrose_results%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20pd%2C%20penrose_results)%3A%0A%20%20%20%20df_penrose%20%3D%20pd.DataFrame(penrose_results)%0A%20%20%20%20mo.ui.table(df_penrose)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%23%20Example%202%3A%20Minimum-Norm%20Verification%20for%20Underdetermined%20Systems%0A%0A%20%20%20%20Consider%20an%20underdetermined%20system%20with%20%24m%20%3D%203%24%20equations%20and%20%24n%20%3D%2010%24%20parameters.%20Infinitely%20many%20solutions%20%24%5Cmathbf%7Bw%7D%24%20satisfy%20%24%5Cmathbf%7BX%7D%5Cmathbf%7Bw%7D%20%3D%20%5Cmathbf%7By%7D%24.%0A%0A%20%20%20%20Any%20feasible%20solution%20can%20be%20parameterized%20as%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cmathbf%7Bw%7D%20%3D%20%5Cmathbf%7Bw%7D_%7B%5Ctext%7Bpinv%7D%7D%20%2B%20%5Cmathbf%7Bn%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20where%20%24%5Cmathbf%7Bn%7D%20%5Cin%20%5Ctext%7Bnull%7D(%5Cmathbf%7BX%7D)%24%20is%20a%20vector%20in%20the%20null%20space.%20Because%20%24%5Cmathbf%7Bw%7D_%7B%5Ctext%7Bpinv%7D%7D%20%5Cin%20%5Ctext%7Brow%7D(%5Cmathbf%7BX%7D)%24%20and%20%24%5Ctext%7Brow%7D(%5Cmathbf%7BX%7D)%20%5Cperp%20%5Ctext%7Bnull%7D(%5Cmathbf%7BX%7D)%24%2C%20the%20Pythagorean%20theorem%20gives%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5C%7C%5Cmathbf%7Bw%7D%5C%7C_2%5E2%20%3D%20%5C%7C%5Cmathbf%7Bw%7D_%7B%5Ctext%7Bpinv%7D%7D%5C%7C_2%5E2%20%2B%20%5C%7C%5Cmathbf%7Bn%7D%5C%7C_2%5E2%20%5Cgeq%20%5C%7C%5Cmathbf%7Bw%7D_%7B%5Ctext%7Bpinv%7D%7D%5C%7C_2%5E2%0A%20%20%20%20%24%24%0A%0A%20%20%20%20Below%2C%20we%20sample%201%2C000%20random%20feasible%20solutions%20and%20numerically%20verify%20that%20%24%5Cmathbf%7Bw%7D_%7B%5Ctext%7Bpinv%7D%7D%24%20achieves%20strictly%20minimal%20%24L_2%24%20norm.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20rng_sample%20%3D%20np.random.default_rng(123)%0A%0A%20%20%20%20%23%203%20samples%2C%2010%20features%20(underdetermined)%0A%20%20%20%20x_data%20%3D%20rng_sample.standard_normal((3%2C%2010))%0A%20%20%20%20y_data%20%3D%20rng_sample.standard_normal(3)%0A%0A%20%20%20%20%23%20Pseudoinverse%20minimum-norm%20solution%0A%20%20%20%20w_pinv%20%3D%20np.linalg.pinv(x_data)%20%40%20y_data%0A%20%20%20%20norm_pinv%20%3D%20float(np.linalg.norm(w_pinv))%0A%0A%20%20%20%20%23%20Compute%20null%20space%20basis%20using%20SVD%0A%20%20%20%20_%2C%20_%2C%20vt_null%20%3D%20np.linalg.svd(x_data)%0A%20%20%20%20%23%20The%20last%207%20right%20singular%20vectors%20span%20the%20null%20space%0A%20%20%20%20null_basis%20%3D%20vt_null%5B3%3A%2C%20%3A%5D.T%20%20%23%20shape%3A%20(10%2C%207)%0A%0A%20%20%20%20%23%20Sample%201%2C000%20random%20vectors%20in%20the%20null%20space%0A%20%20%20%20num_samples%20%3D%201000%0A%20%20%20%20random_coeffs%20%3D%20rng_sample.standard_normal((7%2C%20num_samples))%0A%20%20%20%20null_perturbations%20%3D%20null_basis%20%40%20random_coeffs%20%20%23%20shape%3A%20(10%2C%201000)%0A%0A%20%20%20%20%23%20Construct%20feasible%20solutions%3A%20w%20%3D%20w_pinv%20%2B%20null_vector%0A%20%20%20%20feasible_solutions%20%3D%20w_pinv%5B%3A%2C%20np.newaxis%5D%20%2B%20null_perturbations%0A%0A%20%20%20%20%23%20Verify%20all%20samples%20satisfy%20X%20w%20%3D%20y%0A%20%20%20%20residuals%20%3D%20np.max(np.abs(x_data%20%40%20feasible_solutions%20-%20y_data%5B%3A%2C%20np.newaxis%5D))%0A%0A%20%20%20%20%23%20Compute%20norms%20of%20all%20alternative%20feasible%20solutions%0A%20%20%20%20sample_norms%20%3D%20np.linalg.norm(feasible_solutions%2C%20axis%3D0)%0A%20%20%20%20min_sampled_norm%20%3D%20float(np.min(sample_norms))%0A%20%20%20%20avg_sampled_norm%20%3D%20float(np.mean(sample_norms))%0A%20%20%20%20max_sampled_norm%20%3D%20float(np.max(sample_norms))%0A%0A%20%20%20%20%23%20All%20samples%20must%20have%20norm%20greater%20than%20or%20equal%20to%20w_pinv%0A%20%20%20%20all_greater%20%3D%20bool(np.all(sample_norms%20%3E%3D%20norm_pinv%20-%201e-12))%0A%0A%20%20%20%20underdetermined_summary%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%22Metric%22%3A%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Dataset%20dimension%20(m%20x%20n)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Null%20space%20dimension%20(n%20-%20m)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Number%20of%20sampled%20feasible%20solutions%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Maximum%20interpolation%20error%20max%20%7CX%20w%20-%20y%7C%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Minimum-norm%20solution%20%7C%7Cw_pinv%7C%7C_2%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Lowest%20norm%20among%20sampled%20solutions%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Average%20norm%20among%20sampled%20solutions%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Highest%20norm%20among%20sampled%20solutions%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Is%20%7C%7Cw_pinv%7C%7C_2%20%3C%3D%20%7C%7Cw_sample%7C%7C_2%20for%20all%201%2C000%20samples%3F%22%2C%0A%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20%20%20%20%20%22Value%22%3A%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7Bx_data.shape%5B0%5D%7D%20x%20%7Bx_data.shape%5B1%5D%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20str(null_basis.shape%5B1%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20str(num_samples)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7Bresiduals%3A.2e%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7Bnorm_pinv%3A.6f%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7Bmin_sampled_norm%3A.6f%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7Bavg_sampled_norm%3A.6f%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7Bmax_sampled_norm%3A.6f%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20str(all_greater)%2C%0A%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20%7D%0A%20%20%20%20return%20(underdetermined_summary%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20pd%2C%20underdetermined_summary)%3A%0A%20%20%20%20df_under%20%3D%20pd.DataFrame(underdetermined_summary)%0A%20%20%20%20mo.ui.table(df_under)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A