Minimum-length least squares ============================ This notebook shows how to solve a *minimum-length least squares* problem, which finds a minimum-length vector :math:x \in \mathbf{R}^n achieving small mean-square error (MSE) for a particular least squares problem: .. math:: \begin{array}{ll} \mbox{minimize} & \mathrm{len}(x) \\ \mbox{subject to} & \frac{1}{n}\|Ax - b\|_2^2 \leq \epsilon, \end{array} where the variable is :math:x and the problem data are :math:n, :math:A, :math:b, and :math:\epsilon. This is a quasiconvex program (QCP). It can be specified using disciplined quasiconvex programming (DQCP __), and it can therefore be solved using CVXPY. .. code:: !pip install --upgrade cvxpy .. code:: import cvxpy as cp import numpy as np The below cell constructs the problem data. .. code:: n = 10 np.random.seed(1) A = np.random.randn(n, n) x_star = np.random.randn(n) b = A @ x_star epsilon = 1e-2 And the next cell constructs and solves the QCP. .. code:: x = cp.Variable(n) mse = cp.sum_squares(A @ x - b)/n problem = cp.Problem(cp.Minimize(cp.length(x)), [mse <= epsilon]) print("Is problem DQCP?: ", problem.is_dqcp()) problem.solve(qcp=True) print("Found a solution, with length: ", problem.value) .. parsed-literal:: Is problem DQCP?: True Found a solution, with length: 8.0 .. code:: print("MSE: ", mse.value) .. parsed-literal:: MSE: 0.00926009328813662 .. code:: print("x: ", x.value) .. parsed-literal:: x: [-2.58366030e-01 1.38434327e+00 2.10714108e-01 9.44811159e-01 -1.14622208e+00 1.51283929e-01 6.62931941e-01 -1.16358584e+00 2.78132907e-13 -1.76314786e-13] .. code:: print("x_star: ", x_star) .. parsed-literal:: x_star: [-0.44712856 1.2245077 0.40349164 0.59357852 -1.09491185 0.16938243 0.74055645 -0.9537006 -0.26621851 0.03261455]