{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "minimum_length_least_squares.ipynb",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qrszGAl2pAR3",
        "colab_type": "text"
      },
      "source": [
        "# Minimum-length least squares\n",
        "\n",
        "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:\n",
        "\n",
        "\\begin{equation*}\n",
        "\\begin{array}{ll}\n",
        "\\mbox{minimize} & \\mathrm{len}(x) \\\\\n",
        "\\mbox{subject to} & \\frac{1}{n}\\|Ax - b\\|_2^2 \\leq \\epsilon,\n",
        "\\end{array}\n",
        "\\end{equation*}\n",
        "\n",
        "where the variable is $x$ and the problem data are $n$, $A$, $b$, and $\\epsilon$.\n",
        "\n",
        "This is a quasiconvex program (QCP). It can be specified using disciplined quasiconvex programming ([DQCP](https://www.cvxpy.org/tutorial/dqcp/index.html)), and it can therefore be solved using CVXPY."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YU-tLzgKnh73",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!pip install --upgrade cvxpy"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OlMzge_Pnn06",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import cvxpy as cp\n",
        "import numpy as np"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3YF1kje9qGj4",
        "colab_type": "text"
      },
      "source": [
        "The below cell constructs the problem data."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aH0enIo3noZ2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "n = 10\n",
        "np.random.seed(1)\n",
        "A = np.random.randn(n, n)\n",
        "x_star = np.random.randn(n)\n",
        "b = A @ x_star\n",
        "epsilon = 1e-2"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cFPK3R8yqMIM",
        "colab_type": "text"
      },
      "source": [
        "And the next cell constructs and solves the QCP."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "I1FOl5BSqLhO",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 51
        },
        "outputId": "fca8744a-e094-4082-c5f5-d8b34f99b3bf"
      },
      "source": [
        "x = cp.Variable(n)\n",
        "mse = cp.sum_squares(A @ x - b)/n\n",
        "problem = cp.Problem(cp.Minimize(cp.length(x)), [mse <= epsilon])\n",
        "print(\"Is problem DQCP?: \", problem.is_dqcp())\n",
        "\n",
        "problem.solve(qcp=True)\n",
        "print(\"Found a solution, with length: \", problem.value)"
      ],
      "execution_count": 24,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Is problem DQCP?:  True\n",
            "Found a solution, with length:  8.0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NriM3YJlofVh",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "fb7a9efc-bdce-46dc-8259-19887f64e268"
      },
      "source": [
        "print(\"MSE: \", mse.value)"
      ],
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "MSE:  0.00926009328813662\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "v57uXYOHoj0m",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 68
        },
        "outputId": "c454ed16-f34f-4e5e-bbc6-1664656f2694"
      },
      "source": [
        "print(\"x: \", x.value)"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "x:  [-2.58366030e-01  1.38434327e+00  2.10714108e-01  9.44811159e-01\n",
            " -1.14622208e+00  1.51283929e-01  6.62931941e-01 -1.16358584e+00\n",
            "  2.78132907e-13 -1.76314786e-13]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YwksuTSxoluj",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 51
        },
        "outputId": "9fbec3d6-d23f-472b-8258-3c94170f904c"
      },
      "source": [
        "print(\"x_star: \", x_star)"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "x_star:  [-0.44712856  1.2245077   0.40349164  0.59357852 -1.09491185  0.16938243\n",
            "  0.74055645 -0.9537006  -0.26621851  0.03261455]\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}