marimo-team/marimo-learn

1# /// script2# requires-python = ">=3.11"3# dependencies = [4#     "clarabel>=0.11.1",5#     "cvxpy-base>=1.8.2",6#     "marimo",7#     "numpy==2.4.3",8# ]9# ///10 11import marimo12 13__generated_with = "0.18.4"14app = marimo.App()15 16 17@app.cell18def _():19    import marimo as mo20    return (mo,)21 22 23@app.cell(hide_code=True)24def _(mo):25    mo.md(r"""26    # Least Squares27 28    In a least-squares problem, we have measurements $A \in \mathcal{R}^{m \times29    n}$ (i.e., $m$ rows and $n$ columns) and $b \in \mathcal{R}^m$. We seek a vector30    $x \in \mathcal{R}^{n}$ such that $Ax$ is close to $b$. The matrices $A$ and $b$ are problem data or constants, and $x$ is the variable we are solving for.31 32    Closeness is defined as the sum of the squared differences:33 34    \[ \sum_{i=1}^m (a_i^Tx - b_i)^2, \]35 36    also known as the $\ell_2$-norm squared, $\|Ax - b\|_2^2$.37 38    For example, we might have a dataset of $m$ users, each represented by $n$ features. Each row $a_i^T$ of $A$ is the feature vector for user $i$, while the corresponding entry $b_i$ of $b$ is the measurement we want to predict from $a_i^T$, such as ad spending. The prediction for user $i$ is given by $a_i^Tx$.39 40    We find the optimal value of $x$ by solving the optimization problem41 42    \[43        \begin{array}{ll}44        \text{minimize}   & \|Ax - b\|_2^2.45        \end{array}46    \]47 48    Let $x^\star$ denote the optimal $x$. The quantity $r = Ax^\star - b$ is known as the residual. If $\|r\|_2 = 0$, we have a perfect fit.49    """)50    return51 52 53@app.cell(hide_code=True)54def _(mo):55    mo.md(r"""56    ## Example57 58    In this example, we use the Python library [CVXPY](https://github.com/cvxpy/cvxpy) to construct and solve a least-squares problems.59    """)60    return61 62 63@app.cell64def _():65    import cvxpy as cp66    import numpy as np67    return cp, np68 69 70@app.cell71def _():72    m = 2073    n = 1574    return m, n75 76 77@app.cell78def _(m, n, np):79    np.random.seed(0)80    A = np.random.randn(m, n)81    b = np.random.randn(m)82    return A, b83 84 85@app.cell86def _(A, b, cp, n):87    x = cp.Variable(n)88    objective = cp.sum_squares(A @ x - b)89    problem = cp.Problem(cp.Minimize(objective))90    optimal_value = problem.solve()91    return optimal_value, x92 93 94@app.cell95def _(A, b, cp, mo, optimal_value, x):96    mo.md(97        f"""98        - The optimal value is **{optimal_value:.04f}**.99        - The optimal value of $x$ is {mo.as_html(list(x.value))}100        - The norm of the residual is **{cp.norm(A @ x - b, p=2).value:0.4f}**101        """102    )103    return104 105 106@app.cell(hide_code=True)107def _(mo):108    mo.md(r"""109    ## Further reading110 111    For a primer on least squares, with many real-world examples, check out the free book112    [Vectors, Matrices, and Least Squares](https://web.stanford.edu/~boyd/vmls/), which is used for undergraduate linear algebra education at Stanford.113    """)114    return115 116 117if __name__ == "__main__":118    app.run()119