Least-squares¶

In a least-squares, or linear regression, problem, we have measurements\(A \in \mathcal{R}^{m \times n}\) and\(b \in \mathcal{R}^m\)and seek a vector\(x \in \mathcal{R}^{n}\) such that\(Ax\) isclose to\(b\). Closeness is defined as the sum of the squareddifferences:

also known as the\(\ell_2\)-norm squared,\(\|Ax - b\|_2^2\).

For example, we might have a dataset of\(m\) users, eachrepresented by\(n\) features. Each row\(a_i^T\) of\(A\)is the features 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 is given by\(a_i^Tx\).

We find the optimal\(x\) by solving the optimization problem

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.

Example¶

In the following code, we solve a least-squares problem with CVXPY.

# Import packages.importcvxpyascpimportnumpyasnp# Generate data.m=20n=15np.random.seed(1)A=np.random.randn(m,n)b=np.random.randn(m)# Define and solve the CVXPY problem.x=cp.Variable(n)cost=cp.sum_squares(A@x-b)prob=cp.Problem(cp.Minimize(cost))prob.solve()# Print result.print("\nThe optimal value is",prob.value)print("The optimal x is")print(x.value)print("The norm of the residual is ",cp.norm(A@x-b,p=2).value)

Theoptimalvalueis7.005909828287484Theoptimalxis[0.17492418-0.381025510.347322510.0173098-0.0845784-0.081340190.2931190.270197620.17493179-0.239534490.64097935-0.416336370.127996880.1063942-0.32158411]Thenormoftheresidualis2.6468679280023557