01 least squares

import%20marimo%0A%0A__generated_with%20%3D%20%220.12.0%22%0Aapp%20%3D%20marimo.App()%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%20Least%20squares%0A%0A%20%20%20%20%20%20%20%20In%20a%20least-squares%20problem%2C%20we%20have%20measurements%20%24A%20%5Cin%20%5Cmathcal%7BR%7D%5E%7Bm%20%5Ctimes%0A%20%20%20%20%20%20%20%20n%7D%24%20(i.e.%2C%20%24m%24%20rows%20and%20%24n%24%20columns)%20and%20%24b%20%5Cin%20%5Cmathcal%7BR%7D%5Em%24.%20We%20seek%20a%20vector%0A%20%20%20%20%20%20%20%20%24x%20%5Cin%20%5Cmathcal%7BR%7D%5E%7Bn%7D%24%20such%20that%20%24Ax%24%20is%20close%20to%20%24b%24.%20The%20matrices%20%24A%24%20and%20%24b%24%20are%20problem%20data%20or%20constants%2C%20and%20%24x%24%20is%20the%20variable%20we%20are%20solving%20for.%0A%0A%20%20%20%20%20%20%20%20Closeness%20is%20defined%20as%20the%20sum%20of%20the%20squared%20differences%3A%0A%0A%20%20%20%20%20%20%20%20%5C%5B%20%5Csum_%7Bi%3D1%7D%5Em%20(a_i%5ETx%20-%20b_i)%5E2%2C%20%5C%5D%0A%0A%20%20%20%20%20%20%20%20also%20known%20as%20the%20%24%5Cell_2%24-norm%20squared%2C%20%24%5C%7CAx%20-%20b%5C%7C_2%5E2%24.%0A%0A%20%20%20%20%20%20%20%20For%20example%2C%20we%20might%20have%20a%20dataset%20of%20%24m%24%20users%2C%20each%20represented%20by%20%24n%24%20features.%20Each%20row%20%24a_i%5ET%24%20of%20%24A%24%20is%20the%20feature%20vector%20for%20user%20%24i%24%2C%20while%20the%20corresponding%20entry%20%24b_i%24%20of%20%24b%24%20is%20the%20measurement%20we%20want%20to%20predict%20from%20%24a_i%5ET%24%2C%20such%20as%20ad%20spending.%20The%20prediction%20for%20user%20%24i%24%20is%20given%20by%20%24a_i%5ETx%24.%0A%0A%20%20%20%20%20%20%20%20We%20find%20the%20optimal%20value%20of%20%24x%24%20by%20solving%20the%20optimization%20problem%0A%0A%20%20%20%20%20%20%20%20%5C%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Cbegin%7Barray%7D%7Bll%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Ctext%7Bminimize%7D%20%20%20%26%20%5C%7CAx%20-%20b%5C%7C_2%5E2.%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Cend%7Barray%7D%0A%20%20%20%20%20%20%20%20%5C%5D%0A%0A%20%20%20%20%20%20%20%20Let%20%24x%5E%5Cstar%24%20denote%20the%20optimal%20%24x%24.%20The%20quantity%20%24r%20%3D%20Ax%5E%5Cstar%20-%20b%24%20is%20known%20as%20the%20residual.%20If%20%24%5C%7Cr%5C%7C_2%20%3D%200%24%2C%20we%20have%20a%20perfect%20fit.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Example%0A%0A%20%20%20%20%20%20%20%20In%20this%20example%2C%20we%20use%20the%20Python%20library%20%5BCVXPY%5D(https%3A%2F%2Fgithub.com%2Fcvxpy%2Fcvxpy)%20to%20construct%20and%20solve%20a%20least-squares%20problems.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20cvxpy%20as%20cp%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20return%20cp%2C%20np%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20m%20%3D%2020%0A%20%20%20%20n%20%3D%2015%0A%20%20%20%20return%20m%2C%20n%0A%0A%0A%40app.cell%0Adef%20_(m%2C%20n%2C%20np)%3A%0A%20%20%20%20np.random.seed(0)%0A%20%20%20%20A%20%3D%20np.random.randn(m%2C%20n)%0A%20%20%20%20b%20%3D%20np.random.randn(m)%0A%20%20%20%20return%20A%2C%20b%0A%0A%0A%40app.cell%0Adef%20_(A%2C%20b%2C%20cp%2C%20n)%3A%0A%20%20%20%20x%20%3D%20cp.Variable(n)%0A%20%20%20%20objective%20%3D%20cp.sum_squares(A%20%40%20x%20-%20b)%0A%20%20%20%20problem%20%3D%20cp.Problem(cp.Minimize(objective))%0A%20%20%20%20optimal_value%20%3D%20problem.solve()%0A%20%20%20%20return%20objective%2C%20optimal_value%2C%20problem%2C%20x%0A%0A%0A%40app.cell%0Adef%20_(A%2C%20b%2C%20cp%2C%20mo%2C%20optimal_value%2C%20x)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20f%22%22%22%0A%20%20%20%20%20%20%20%20-%20The%20optimal%20value%20is%20**%7Boptimal_value%3A.04f%7D**.%0A%20%20%20%20%20%20%20%20-%20The%20optimal%20value%20of%20%24x%24%20is%20%7Bmo.as_html(list(x.value))%7D%0A%20%20%20%20%20%20%20%20-%20The%20norm%20of%20the%20residual%20is%20**%7Bcp.norm(A%20%40%20x%20-%20b%2C%20p%3D2).value%3A0.4f%7D**%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Further%20reading%0A%0A%20%20%20%20%20%20%20%20For%20a%20primer%20on%20least%20squares%2C%20with%20many%20real-world%20examples%2C%20check%20out%20the%20free%20book%0A%20%20%20%20%20%20%20%20%5BVectors%2C%20Matrices%2C%20and%20Least%20Squares%5D(https%3A%2F%2Fweb.stanford.edu%2F~boyd%2Fvmls%2F)%2C%20which%20is%20used%20for%20undergraduate%20linear%20algebra%20education%20at%20Stanford.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%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