Minimum-length least squares

This notebook shows how to solve a minimum-length least squares problem, which finds a minimum-length vector $x \in \mathbf{R}^n$ achieving small mean-square error (MSE) for a particular least squares problem:

\begin{equation*} \begin{array}{ll} \mbox{minimize} & \mathrm{len}(x) \\ \mbox{subject to} & \frac{1}{n}\|Ax - b\|_2^2 \leq \epsilon, \end{array} \end{equation*}

where the variable is $x$ and the problem data are $n$, $A$, $b$, and $\epsilon$.

This is a quasiconvex program (QCP). It can be specified using disciplined quasiconvex programming (DQCP), and it can therefore be solved using CVXPY.



In [0]:

    
!pip install --upgrade cvxpy



In [0]:

    
import cvxpy as cp
import numpy as np

The below cell constructs the problem data.



In [0]:

    
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.



In [24]:

    
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)









    



Is problem DQCP?:  True
Found a solution, with length:  8.0



In [15]:

    
print("MSE: ", mse.value)









    



MSE:  0.00926009328813662



In [17]:

    
print("x: ", x.value)









    



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]



In [18]:

    
print("x_star: ", x_star)









    



x_star:  [-0.44712856  1.2245077   0.40349164  0.59357852 -1.09491185  0.16938243
  0.74055645 -0.9537006  -0.26621851  0.03261455]