{"nbformat_minor": 0, "worksheets": [{"cells": [{"source": ["Matrix Completion with Nuclear Norm Minimization\n", "================================================\n", "\n*Important:* Please read the [installation page](http://gpeyre.github.io/numerical-tours/installation_matlab/) for details about how to install the toolboxes.\n", "$\\newcommand{\\dotp}[2]{\\langle #1, #2 \\rangle}$\n", "$\\newcommand{\\enscond}[2]{\\lbrace #1, #2 \\rbrace}$\n", "$\\newcommand{\\pd}[2]{ \\frac{ \\partial #1}{\\partial #2} }$\n", "$\\newcommand{\\umin}[1]{\\underset{#1}{\\min}\\;}$\n", "$\\newcommand{\\umax}[1]{\\underset{#1}{\\max}\\;}$\n", "$\\newcommand{\\umin}[1]{\\underset{#1}{\\min}\\;}$\n", "$\\newcommand{\\uargmin}[1]{\\underset{#1}{argmin}\\;}$\n", "$\\newcommand{\\norm}[1]{\\|#1\\|}$\n", "$\\newcommand{\\abs}[1]{\\left|#1\\right|}$\n", "$\\newcommand{\\choice}[1]{ \\left\\{  \\begin{array}{l} #1 \\end{array} \\right. }$\n", "$\\newcommand{\\pa}[1]{\\left(#1\\right)}$\n", "$\\newcommand{\\diag}[1]{{diag}\\left( #1 \\right)}$\n", "$\\newcommand{\\qandq}{\\quad\\text{and}\\quad}$\n", "$\\newcommand{\\qwhereq}{\\quad\\text{where}\\quad}$\n", "$\\newcommand{\\qifq}{ \\quad \\text{if} \\quad }$\n", "$\\newcommand{\\qarrq}{ \\quad \\Longrightarrow \\quad }$\n", "$\\newcommand{\\ZZ}{\\mathbb{Z}}$\n", "$\\newcommand{\\CC}{\\mathbb{C}}$\n", "$\\newcommand{\\RR}{\\mathbb{R}}$\n", "$\\newcommand{\\EE}{\\mathbb{E}}$\n", "$\\newcommand{\\Zz}{\\mathcal{Z}}$\n", "$\\newcommand{\\Ww}{\\mathcal{W}}$\n", "$\\newcommand{\\Vv}{\\mathcal{V}}$\n", "$\\newcommand{\\Nn}{\\mathcal{N}}$\n", "$\\newcommand{\\NN}{\\mathcal{N}}$\n", "$\\newcommand{\\Hh}{\\mathcal{H}}$\n", "$\\newcommand{\\Bb}{\\mathcal{B}}$\n", "$\\newcommand{\\Ee}{\\mathcal{E}}$\n", "$\\newcommand{\\Cc}{\\mathcal{C}}$\n", "$\\newcommand{\\Gg}{\\mathcal{G}}$\n", "$\\newcommand{\\Ss}{\\mathcal{S}}$\n", "$\\newcommand{\\Pp}{\\mathcal{P}}$\n", "$\\newcommand{\\Ff}{\\mathcal{F}}$\n", "$\\newcommand{\\Xx}{\\mathcal{X}}$\n", "$\\newcommand{\\Mm}{\\mathcal{M}}$\n", "$\\newcommand{\\Ii}{\\mathcal{I}}$\n", "$\\newcommand{\\Dd}{\\mathcal{D}}$\n", "$\\newcommand{\\Ll}{\\mathcal{L}}$\n", "$\\newcommand{\\Tt}{\\mathcal{T}}$\n", "$\\newcommand{\\si}{\\sigma}$\n", "$\\newcommand{\\al}{\\alpha}$\n", "$\\newcommand{\\la}{\\lambda}$\n", "$\\newcommand{\\ga}{\\gamma}$\n", "$\\newcommand{\\Ga}{\\Gamma}$\n", "$\\newcommand{\\La}{\\Lambda}$\n", "$\\newcommand{\\si}{\\sigma}$\n", "$\\newcommand{\\Si}{\\Sigma}$\n", "$\\newcommand{\\be}{\\beta}$\n", "$\\newcommand{\\de}{\\delta}$\n", "$\\newcommand{\\De}{\\Delta}$\n", "$\\newcommand{\\phi}{\\varphi}$\n", "$\\newcommand{\\th}{\\theta}$\n", "$\\newcommand{\\om}{\\omega}$\n", "$\\newcommand{\\Om}{\\Omega}$\n"], "metadata": {}, "cell_type": "markdown"}, {"source": ["This numerical tour explore the use of convex relaxation to recover low\n", "rank matrices from a few measurements.\n", "\n", "\n", "Special thanks to Jalal Fadili for useful comments and advices."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 2, "cell_type": "code", "language": "python", "metadata": {}, "input": ["addpath('toolbox_signal')\n", "addpath('toolbox_general')\n", "addpath('solutions/sparsity_3_matrix_completion')"]}, {"collapsed": false, "outputs": [], "prompt_number": 3, "cell_type": "code", "language": "python", "metadata": {}, "input": ["n = 100;"]}, {"source": ["Rank $r$ of the matrix."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 4, "cell_type": "code", "language": "python", "metadata": {}, "input": ["r = 10;"]}, {"source": ["Generate a random matrix $x_0 \\in \\RR^{n \\times n} $ of rank $r$,\n", "as the product of Gaussian vectors."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 5, "cell_type": "code", "language": "python", "metadata": {}, "input": ["x0 = randn(n,r)*randn(r,n);"]}, {"source": ["Display the singular values. Only $r$ are non zero, and they are\n", "clustered around the value $n$."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "png": "iVBORw0KGgoAAAANSUhEUgAAAkAAAAGwCAIAAADOgk3lAAAACXBIWXMAAAsSAAALEgHS3X78AAAA\nIXRFWHRTb2Z0d2FyZQBBcnRpZmV4IEdob3N0c2NyaXB0IDguNTRTRzzSAAAK60lEQVR4nO3d0Vbi\nSgJA0dQs//+Xax4YmTQirbaQnGTvB5c03kutgDlWUcCYcy4AUPOfrQcAAD8hYAAkCRgASQIGQJKA\nAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIG\nQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkHTxgYyxjbD0IAJ7gbesBvMIQ\nMYBvmnNuPYS/OEXANrkbxhh7uPsNwzAe2MlIDGOfw9h6CH938CXEZQncBwD8wOEDBsAxCRgASbtY\nbH2eMUbhmUiAfdnJU3GPmYEBkCRgACQdP2Bzei0zwAEdP2AAHJKAAZAkYAAkCRgASQIGQJKAAZAk\nYAAknSJgXgoGcDynCBgAxyNgACQJGABJAgZAkoABkCRgACS9bT2A71l/SOh43xp/+ZebizcuO+l3\n//miAHxVJmDj3iu51ulah23/n4QNwD/KLCHOOW+ypFIAZ5aZgX3mMt+6Oz+7/sD7t9PkDOAzD06k\n+xQO2M3K4WdWS4smbQCfWp8hEzHLLCHeJUgAp1WdgV3+OljvPHy8CxGAg4kF7Bqnj5XSLYBTaS8h\nfosPVQE4khMFDIAjOVHALtMvkzCAYzhRwC48UwZwDCcKmHQBHMmJArbYxwFwIOcKGACHIWAAJJ0u\nYFYRAY7hdAED4BgEDICkMwbMKiLAAZwxYAAcgIABkHTSgFlFBKg7acAAqDt1wEzCALpOHTAAus4b\nMG9OD5B23oABkCZgACQJGABJAgZAkoABkCRgACSdOmDeUAqg69QBA6BLwABIEjAAkgQMgCQBAyBJ\nwABIOnvA7KQHiDp7wACIEjAAkgQMgCQBAyBJwABIEjAAkgTMTnqAJAEDIEnAAEgSMACSBAyAJAED\nIEnAAEh623oA3zPGmHNev798c/mXm4vfctlJ//3/DoDNZAI2/nyt1seSrS/+oGEAtGSWEOecz8uS\nFzID5GRmYD92M3V7UEGriMCZjdrf8scP2Ffmbdd3k9Iw4LTWZ8tEzI4fsC+63nEaBpBQDdic8xd3\nIf75f/7fbEzGAPYsFrB1nG5CZechwKlkdiG+khQC7J+A3edDwgB2TsA+pWEAeyZgACQJ2CMmYQC7\nJWB/N4aMAeyOgAGQJGB/cdlSb2M9wN4IGABJAvZ3tnIA7JCAAZAkYAAkCRgASQL2JZ4GA9gbAQMg\nScAASBIwAJIEDIAkAfsq+zgAdkXAAEgSMACSBAyAJAEDIEnAvsE+DoD9EDAAkgQMgCQB+zariAB7\nIGAAJAnY98y59QgAWJZFwACIEjAAkgQMgCQBAyBJwL7N+3EA7IGAAZAkYAAkCRgASQIGQJKAAZAk\nYD9hIyLA5gQMgCQBAyBJwABIEjAAkgQMgCQB+yEbEQG2JWAAJL1tPYB/MsZYlmXOef3+ehGAYwsH\nbIyxTte1W9d/B+DALCECkBSegS2rudf4fEPFzVUmZwB3PTiR7lM1YOt1wscH/XnFumxEFETgGNZn\ny0TMLCH+XOH+BTis6gxsvWy47S5EkzCATVQDtnwI1euf3LKECLAhS4j/xPtxAGxFwABIEjAAkgTs\nX1lFBNiEgAGQJGAAJAnYL7CKCPB6AgZAkoABkCRgACQJ2O/wNBjAiwkYAEkC9ptMwgBeRsAASBKw\nX+NzVQBeScAASBIwAJIEDIAkAftNXg0G8DICBkCSgAGQJGAAJAkYAEkCBkCSgP0yGxEBXkPAAEgS\nMACSBAyAJAEDIEnAfp99HAAvIGAAJAkYAEkCBkCSgAGQJGBPYR8HwLMJGABJAvYUl+mXSRjA8wgY\nAEkC9hRz/v8rAM8gYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQNLb1gP4ufH+Rhdzzo8XATi2asAu\nuVqn69qtMYaGARxeewlxjCFXAOdUnYEtf065HvzYzbVqB3DX43PpDoUD9kWKBfAV67NlImbtJUQA\nTqs6A5tz2oUIcGbVgC0fQqVbAKdiCRGAJAEDIEnAAEgSsGeZcylsQwWoEjAAkgQMgCQBAyBJwABI\nEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJ\nwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQB\nAyBJwABIEjAAkgQMgCQBe6I5lzG2HgTAQQkYAEkCBkCSgAGQJGAAJOUDNt63SYx3244HgNd423oA\n/2Rdrznnx+8BOKpwwC6h+uuU6+YHtA3grtwKVjhgX6RYAF+xPlsmYlZ9DuxycNdfATiVasDmu8Uc\nC+CUDrKEuH4yTM8AziAfsGuudAvgVKpLiACcnIABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZA\nkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJ\nAgZAkoABkCRgzzXnMsbWgwA4IgEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgS\nMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACS3rYewM+NMS7fzDk/XgTg2MIBW/5M17Vb\nYwwNAzi88BKiSgGcWXsGtrzPt67rh3d/YH1R9gDuenAi3adwwG5WDj+jWABfsT5bJmIWXkJcxAng\nxKozsMtfB+udh3YhApxKNWAfK6VbAKfSXkIE4LQEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIw\nAJIEDIAkAQMgScCebs6l8LkEADECBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQ\nJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCS\ngAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgD3LGGPrISyLYfzJMG7sZCSGsbaTYSQIGABJ\nAgZAkoBt4MEKwa9ftSyzOwyAB8acn55ZDmA3q8lHPsjAUe28D29bD+C5dpLnS0YvY7kmdX3xX666\n+5OuOsNVd3/SA8xVv/gA27mDz8AAOCrPgQGQJGAAJAkYAEkH38SxiTH+/8zidRvkK59r/HijZx7G\n9aZ3cjSut7vV0bi53c2PxuWmt31sLO6Uh78jG947jwnYb7r5tbx5QLzyvr8+7C6nhpMPY32/bH40\nth3Gx5P1JsO4ORTbPjY2Pxofy/HiYTw+cb1+PF9nCfE3zTn3cO/uYQzLboaxn1+5y5l661Esy4dm\nbDuSPQzj5HZy4voBM7DD2sOpYSfn651Yz0c3H8bi3nl3nWRsfkA2H0COgB3Qzax/QzcL6K93uenr\n1w2PyR7ujr3ZvOV3n/V5vWs79xDRFkuIx7T56XInv4fz3bLpMdnJ0WCfLh3d/He2aPtVpuPZdsPb\nx/1dmwzj7o3ahbjs4GjsZIPZzfTL0dh8GMVdiAIGQJIlRACSBAyAJAEDIEnAAEgSMACSBAyAJAED\nIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyA\nJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyApP8C6THAv0kp5yIA\nAAAASUVORK5CYII=\n", "output_type": "display_data"}], "prompt_number": 6, "cell_type": "code", "language": "python", "metadata": {}, "input": ["plot(svd(x0), '.-');\n", "axis tight;"]}, {"source": ["Matrix Completion\n", "-----------------\n", "We consider here a simple measurement operator $\\Phi : \\RR^{n \\times n} \\rightarrow \\RR^P$ that retains only a\n", "sub-set of the entries of the matix.\n", "$$ \\Phi x = ( x_i )_{i \\in I} $$\n", "where $\\abs{I}=P$ is the set of extracted indexes.\n", "\n", "\n", "One can of course consider other linear measurement operators.\n", "\n", "\n", "Number $P$ of measurements."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 7, "cell_type": "code", "language": "python", "metadata": {}, "input": ["P = round( n*log(n)*r*1 );"]}, {"source": ["We use here a set of random sampling locations."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 8, "cell_type": "code", "language": "python", "metadata": {}, "input": ["I = randperm(n*n); I = I(1:P); I = I(:);"]}, {"source": ["Measurement operator and its adjoint."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 9, "cell_type": "code", "language": "python", "metadata": {}, "input": ["Phi  = @(x)x(I);\n", "PhiS= @(y)reshape( accumarray(I, y, [n*n 1], @sum), [n n]);"]}, {"source": ["Measurement $y=\\Phi x_0$."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 10, "cell_type": "code", "language": "python", "metadata": {}, "input": ["y = Phi(x0);"]}, {"source": ["The low-rank matrix completion corresponds to the following non-convex\n", "minimization.\n", "$$ x^{\\star} \\in \\uargmin{\\Phi x = y} \\text{rank}(x). $$\n", "\n", "\n", "Noiseless Completion using Douglas Rachford\n", "-------------------------------------------\n", "To obtain fast algorithm, it is possible to convexify the objective\n", "function and use the nuclear norm $ \\norm{x}_{\\star} $\n", "$$ x^{\\star} \\in \\umin{\\Phi x = y} \\norm{x}_{\\star} = \\sum_i s_i(x) $$\n", "This is a convex problem, that can be solved efficiently, as we show next.\n", "\n", "\n", "\n", "It is shown in\n", "\n", "\n", "_The Power of Convex Relaxation: Near-Optimal Matrix Completion_\n", "E. J. Candes and T. Tao,\n", "IEEE Trans. Inform. Theory, 56(5), 2053-2080, 2009.\n", "\n", "\n", "that if the columns of $U(x_0)$ and $V(x_0)$ have a small enough $\\ell^\\infty$ norm,\n", "and if $P \\geq C r n \\log(n)$ for some absolute constant $C$ then\n", "$x^\\star=x_0$.\n", "\n", "\n", "This minimization can be written as\n", "$$ \\umin{ x } F(x) + G(x) \\qwhereq\n", "\\choice{\n", "      F(x) = i_{\\Cc}(x), \\\\\n", "      G(x) = \\norm{x}_{\\star}.\n", "  }$\n", "$$\n", "where $\\Cc = \\enscond{x}{\\Phi x =y}$.\n", "\n", "\n", "One can solve this problem using the Douglas-Rachford iterations\n", "$$ \\tilde x_{k+1} = \\pa{1-\\frac{\\mu}{2}} \\tilde x_k +\n", "  \\frac{\\mu}{2} \\text{rPox}_{\\gamma G}( \\text{rProx}_{\\gamma F}(\\tilde x_k)  )\n", "  \\qandq x_{k+1} = \\text{Prox}_{\\gamma F}(\\tilde x_{k+1},) $$\n", "\n", "\n", "We have use the following definition for the proximal and\n", "reversed-proximal mappings:\n", "$$ \\text{rProx}_{\\gamma F}(x) = 2\\text{Prox}_{\\gamma F}(x)-x $$\n", "$$ \\text{Prox}_{\\gamma F}(x) = \\uargmin{y} \\frac{1}{2}\\norm{x-y}^2 + \\ga F(y). $$\n", "\n", "\n", "One can show that for any value of $\\gamma>0$, any $ 0 < \\mu < 2 $,\n", "and any $\\tilde x_0$, $x_k \\rightarrow x^\\star$\n", "which is a solution of the minimization of $F+G$.\n", "\n", "\n", "$$ \\text{Prox}_{\\gamma F}(x) = \\uargmin{y} \\frac{1}{2}\\norm{x-y}^2 + \\ga F(y). $$\n", "\n", "\n", "The proximal operator of $F$ is the orthogonal projection on $\\Cc$.\n", "It is computed as\n", "$$ \\text{Prox}_{\\ga F}(x) = x + \\Phi^*(y-\\Phi x). $$"], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 11, "cell_type": "code", "language": "python", "metadata": {}, "input": ["ProxF = @(x,gamma)x + PhiS(y-Phi(x));"]}, {"source": ["The proximal operator of $G$ is the soft thresholding of the singular\n", "values\n", "$$ \\text{Prox}_{\\ga F}(x) = U(x) \\rho_\\la( S(x) ) V(x)^*  $$\n", "where, for $ S=\\text{diag}(s_i)_i $\n", "$$ \\rho_\\la(S) = \\diag\\pa{ \\max(0,1-\\la/\\abs{s_i}) s_i  }_i. $$\n", "\n", "\n", "Define $\\rho_\\la$ as a diagonal operator."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 12, "cell_type": "code", "language": "python", "metadata": {}, "input": ["SoftThresh = @(x,gamma)max(0,1-gamma./max(abs(x),1e-10)).*x;"]}, {"source": ["Display it in 1-D."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "png": "iVBORw0KGgoAAAANSUhEUgAAAkAAAAGwCAIAAADOgk3lAAAACXBIWXMAAAsSAAALEgHS3X78AAAA\nIXRFWHRTb2Z0d2FyZQBBcnRpZmV4IEdob3N0c2NyaXB0IDguNTRTRzzSAAANCElEQVR4nO3d227b\nOhBAUeog///LOg9uHdVxEl8ocma41kPhBEFD6MJtMgK87fveACCb/2YPAABeIWAApCRgAKQkYACk\nJGAApCRgAKQkYACkJGAApCRgAKQkYACkJGAApCRgAKQkYACkJGAApCRgAKQkYACkJGAApCRgAKQk\nYACkJGAApCRgAKQkYACkJGAApCRgAKQkYACkJGAApCRgAKQkYACkJGAApCRgAKQkYACk9DF7AOfa\ntm32EABS2vd99hB+UTxgLcY52LbNMOKMwTCijcEwoo2hJXn3bwsRgJQEDICUBAyAlEJstp4nyG4y\nQC4pJk8rMABSEjAAUhIwAFISMABSEjAAUhIwAFISMABSEjAAUhIwAFISMABSEjAAUhIwAFISMABS\nEjAA/pHh05hbEzAAjv7WK/pnqTQBA+Aqy9rrQsAAaO22XglSJmAA/FOv8B/F/IeAAawuY72agAEs\nLmm9moABrCxvvZqAASwrdb2agAGsKXu9moABLKhAvZqAAaymRr2agAEspUy9moABrKNSvZqAASyi\nWL2agAGsoF69moABlFeyXk3AAGqrWq8mYACFFa5XEzCAqmrXq7X2MXsAPW3Xj8Iuea4AHla+Xq3S\nCuxSr33f933fcn0sNkBXK9SrFVuBtUPGZg8EYI5F6tWKBezarW3bjq/v/gxAPe/UK93eVamA3aVY\nwCLeXHsdZ8sUMavzNzCAla2zc3hVZwV2fHbDqgtYyoL1apUC1nQLWNKa9Wq2EAFSW7ZeTcAA8lq5\nXk3AAJJavF5NwAAyUq8mYADpqNeFgAFkol5XAgaQhnodCRhADup1Q8AAElCvrwQMIDr1ukvAAEJT\nr+8IGEBc6vUDAQMISr1+JmAAEanXrwQMIBz1eoSAAcSiXg8SMIBA1OtxAgYQhXo9RcAAQlCvZwkY\nwHzq9QIBA5hMvV4jYAAzqdfLBAxgGvV6h4ABzKFebxIwgAnU630CBjCaenUhYABDqVcvAgYwjnp1\nJGAAg6hXXwIGMIJ6dSdgAKdTrzMIGMC51OskAgZwIvU6j4ABnEW9TiVgAKdQr7MJGEB/6jWAgAF0\npl5jFAzYdrx2AMZSr2GqBUy9gInUa6RSAdu2bXfJAJOo12Afswdwups1mcIBZyhQr3Q7WHWWLHdD\nZU0GDFCgXjdSTJ51VmDXY53iuANl1KtXFqX+BgYwmHpNVDBgll/AGOo1V8GAAQygXtMJGMDT1CsC\nAQN4jnoFIWAAT1CvOAQM4FHqFYqAATxEvaIRMIDfqVdAAgbwC/WKScAAfqJeYQkYwLfUKzIBA7hP\nvYITMIA71Cs+AQO4pV4pCBjAP9QrCwED+KReiQgYwB/qlYuAAbSmXgkJGIB6pSRgwOrUKykBA5am\nXnkJGLAu9UpNwIBFqVd2AgasSL0KEDBgOepVg4ABa1GvMgQMWIh6VSJgwCrUqxgBA5agXvUIGFCf\nepUkYEBx6lWVgAGVqVdhAgaUpV61CRhQk3qVJ2BAQeq1AgEDqlGvRQgYUIp6rUPAgDrUaykfswfQ\n0/b34t1dubAe9VpNtRXYvu/7vm/HCxlYgHotqNQK7O7C6yZmFmdQj3p1ke6tf6mAXWzbdqyUYkFt\n6tXLcbZMEbNSAbscccWCdajXygr+DWz2EIBB1GtxdVZgl+WXBxFhEepFnYApFqxDvWj1thCB8tSL\nCwEDMlEvrgQMSEO9OBIwIAf14oaAAQmoF18JGBCdenGXgAGhqRffETAgLvXiBwIGBKVe/EzAgIjU\ni18JGBCOevEIAQNiUS8eJGBAIOrF4wQMiEK9eIqAASGoF88SMGA+9eIFAgZMpl68RsCAmdSLlwkY\nMI168Q4BA+ZQL94kYMAE6sX7BAwYTb3oQsCAodSLXgQMGEe96EjAgEHUi74EDBhBvehOwIDTqRdn\nEDDgXOrFSQQMOJF6cR4BA86iXpxKwIBTqBdnEzCgP/ViAAEDOlMvxhAwoCf1YhgBA7pRL0YSMKAP\n9WKwj9kD6Gn7ewPt7h4YS70Yr07Atm27duv4GjibejGFLUTyOU6XTKdezFJnBfad7d/ZzsostevJ\n1LCA3FvZbdnuq/oBU6wyst1ca3GfFXCcLVPErH7AqME+FXCjTsD2ffcUYlXqBXxVJ2BNt4pSL+Au\nTyESmnoB3xEw4lIv4AcCRlDqBfxMwIhIvYBfCRjhqBfwCAEjFvUCHiRgBKJewOMEjCjUC3iKgBGC\negHPEjDmUy/gBQLGZOoFvEbAmEm9gJcJGNOoF/AOAWMO9QLeJGBMoF7A+wSM0dQL6ELAGEq9gF4E\njHHUC+hIwBhEvYC+BIwR1AvoTsA4nXoBZxAwzqVewEkEjBOpF3AeAeMs6gWcSsA4hXoBZxMw+lMv\nYAABozP1AsYQMHpSL2AYAaMb9QJGEjD6UC9gMAGjA/UCxhMw3qVewBQCxlvUC5hFwHidegETCRgv\nUi9gLgHjFeoFTCdgPE29gAg+Zg+gp+3vzLqbVk+jXkAQ1VZg+77v+74dZ1n6US8gjlIBs/A6lXoB\noZTaQrzYtu1YspvVmMi9Rr2gvHR7V1kDdjdLl2/eJEqx3qdesIIf3vrHlDVg32VJrrpTLyCmrAH7\n6vJ+wYOIfakXEFadgClWd+oFRFbqKUQ6Ui8gOAHjDvUC4hMwbqkXkIKA8Q/1ArIQMD6pF5CIgPGH\negG5CBitqReQkIChXkBKArY69QKSErClqReQl4CtS72A1ARsUeoFZCdgK1IvoAABW456ATUI2FrU\nCyhDwBaiXkAlArYK9QKKEbAlqBdQj4DVp15ASQJWnHoBVQlYZeoFFCZgZakXUJuA1aReQHkCVpB6\nASsQsGrUC1iEgJWiXsA6BKwO9QKWImBFqBewGgGrQL2ABQlYeuoFrEnAclMvYFkClph6ASsTsKzU\nC1icgKWkXgAClo96ATQBS0e9AC4ELBP1ArgqGLDtOM0Xol4AR9UCpl4Ai/iYPYCetm3b9/2mYTdf\n7gmnf/UCBki3ACgVsLsyFutIvYAxjrNliphlDdjXddXlO9d/s3frQr0AvpM1YF/7dP2OegGsoNpD\nHGWoF8DPCgaswPJLvQB+VTBg2akXwCMELBb1AniQgAWiXgCPE7Ao1AvgKQIWgnoBPEvA5lMvgBcI\n2GTqBfAaAZtJvQBeJmDTqBfAOwRsDvUCeJOATaBeAO8TsNHUC6ALARtKvQB6EbBx1AugIwEbRL0A\n+hKwEdQLoDsBO516AZxBwM6lXgAnEbATqRfAeQTsLOoFcCoBO4V6AZxNwPpTL4ABBKwz9QIYQ8B6\nUi+AYQSsG/UCGEnA+lAvgMEErAP1AhhPwN6lXgBTCNhb1AtgFgF7nXoBTCRgL1IvgLkE7BXqBTCd\ngD1NvQAiELDnqBdAEAL2BPUCiEPAHqVeAKF8zB5AT9vfyOy9C6NeANHUWYFd6rXv+77v2zE4Hf7n\nz9fqBRBEqRVYO2Ss33/4+Vq9AOIoFbBrt7ZtO76++zOPUC9gHX33rgbIGrDHs/Tyaky9gKUcZ8sU\nMcsasO6PadxQL4Dgsgbsq+OzG2/mTb0A4qsTsNZpWaZeACnUeYy+C/UCyELAPqkXQCIC9od6AeQi\nYK2pF0BCAqZeACmtHjD1Akhq6YCpF0Be6wZMvQBSWzRg6gWQ3YoBUy+AApYLmHoB1LBWwNQLoIyF\nAqZeAJWsEjD1AihmiYCpF0A99QOmXgAllQ/YZ7LUC6CS8gH7Q70AiikfsK2pF0BF5QOmXgA11Q8Y\nACUJGAApCRgAKQkYACkJGAApCRgAKQkYACkJGAApCRgAKQkYACkJGAApCRgAKQkYACkJ2Ajb8WOh\n54kwjAhjaIYRbAzNMIKNIQsBAyAlAQMgJQEDIKVtL/2JxXaTAV4Tvw7FAwZAVbYQAUhJwABIScAA\nSEnAAEjpY/YAzrJtn8+nXJ9FnPXEymUAE5+XmX4Ejo6nZtYALi+ckSDDuJh7YcQ5FBGmiziT588K\nBuzm0fmbkzH+NFx/6az783g/xInHXNPPyNxr8siF0SLdI3Oni2iT568KbiHu+x7wQE+3bdv0S3D6\nAC4ijCGIIIciyIUR4R6ZK93kWXAFFtD0PYHgb6OmcCiuHIoW6R6ZPl0kkj5gN2veCFfe1b7vU9bg\nEbbp7h6K6/dnHYrr5kybfakEEeFQTLkwYoq/ZRdN+oCFOsdBBnMzjCk9+3ooptyZ3/2iIGcqgumH\nwpTNy8peMXEepInwGE+EMVxN/yP58cu5D6ZOHEALcyiuglwYEdajc4cRZ/L8VdmAAVBbwacQAViB\ngAGQkoABkJKAAZCSgAGQkoABkJKAAZCSgAGQkoABkJKAAZCSgAGQkoABkJKAAZCSgAGQkoABkJKA\nAZCSgAGQkoABkJKAAZCSgAGQkoABkJKAAZCSgAGQkoABkJKAAZCSgAGQkoABkJKAAZCSgAGQkoAB\nkJKAAZCSgAGQkoABkJKAAZDS/06voL6fSJe/AAAAAElFTkSuQmCC\n", "output_type": "display_data"}], "prompt_number": 13, "cell_type": "code", "language": "python", "metadata": {}, "input": ["t = linspace(-10,10,1000);\n", "h = plot(t, SoftThresh(t,3)); axis tight; axis equal;\n", "set(h, 'LineWidth', 2);"]}, {"source": ["Define the proximal mapping $\\text{Prox}_{\\ga F}$."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 14, "cell_type": "code", "language": "python", "metadata": {}, "input": ["prod = @(a,b,c)a*b*c;\n", "SoftThreshDiag = @(a,b,c,gamma)a*diag(SoftThresh(diag(b),gamma))*c';\n", "ProxG = @(x,gamma)apply_multiple_ouput(@(a,b,c)SoftThreshDiag(a,b,c,gamma), @svd, x);"]}, {"source": ["Compute the reversed prox operators."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 15, "cell_type": "code", "language": "python", "metadata": {}, "input": ["rProxF = @(x,gamma)2*ProxF(x,gamma)-x;\n", "rProxG = @(x,gamma)2*ProxG(x,gamma)-x;"]}, {"source": ["Value for the $0 < \\mu < 2$ and $\\gamma>0$ parameters.\n", "You can use other values, this might speed up the convergence."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 16, "cell_type": "code", "language": "python", "metadata": {}, "input": ["mu = 1;\n", "gamma = 1;"]}, {"source": ["__Exercise 1__\n", "\n", "Implement the Douglas-Rachford iterative algorithm.\n", "Keep track of the evolution of the nuclear norm $G(x_k)$."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "png": "iVBORw0KGgoAAAANSUhEUgAAAkAAAAGwCAIAAADOgk3lAAAACXBIWXMAAAsSAAALEgHS3X78AAAA\nIXRFWHRTb2Z0d2FyZQBBcnRpZmV4IEdob3N0c2NyaXB0IDguNTRTRzzSAAAPZ0lEQVR4nO3d4Xba\nuAKFUXRX3v+VdX+48Tg2GIeApSPvvbo64KaD6hK+SFZoqbXeACDN/1oPAABeIWAARBIwACIJGACR\nBAyASAIGQCQBAyCSgAEQScAAiCRgAEQSMAAiCRgAkQQMgEgCBkAkAQMgkoABEEnAAIgkYABEEjAA\nIgkYAJEEDIBIAgZAJAEDIJKAARBJwACIJGAARBIwACIJGACRBAyASAIGQCQBAyDSV+sBfFYp//7b\ndhgAcWqtrYfwxOABm7T9ayil9PA8MIzehtHDGAyjw2H0MIZpGK2H8JwlRAAiCRgAkQQMgEhdLLZ+\nzrSKO/QfEeD9OrkUt6/3TRzzSVxeUVwdmc/y9sj3cQ0DGE2/AdvugVlmafnVwXR7e+SccQLQRL/X\nwGqtm4lUidjZCcAJ+p2Bbc0rhy/Mrh6tLgIwiZshxATsj+HRLYB9q8s0DUdyUL9LiEsRpxKAM2XM\nwKY9GvPtg0cAGFjvAZtTtG3SkSMAjCpjCREAVgQMgEjDB8zuD4AxDR8wAMYkYABEEjAAIgkYAJEE\nDIBIAgZApKsEzJspAgzmKgEDYDACBkAkAQMgkoABEEnAAIgkYABEEjAAIo0fMP9KM8CQxg8YAEMS\nMAAiCRgAkQQMgEgCBkCkCwXMG9IDjOSr9QCeKKXUxUb45d2yKNJ0cD5S7Z0HGF2/ASubGdP2yE7b\nNAxgbP0uIdZaH/VpeXBbNQCuoN8Z2BHzyuHOfKuUcruZmQE8ETcfyAjYdFrnn6cIHUxRrXX+S1Ev\ngEdWi14NR3JQv0uIS/XbbbNfA4BrypiBbdVaV3sOt0cAGFjvAVulaHl3W6lH3arVN4EBjCZjCREA\nVgQMgEgCBkAkAQMgkoABEOlaAbMXEWAY1woYAMMQMAAiCRgAkQQMgEgCBkAkAQMg0lUC5u3pAQZz\nlYABMBgBAyCSgAEQScAAiHS5gHk7RIAxXC5gAIxBwACIJGAARBIwACIJGACRBAyASL0HrPzc9r68\nW77tHFnydogAI/lqPYCHth1atap+F2m6vT1yzjgBaKLfGVitdRkhTQJgqd8Z2Lv8nMlJIMB9j66/\ndCsjYNNpnX/+1VTs5zTu7UMDGMRq0avhSA7KCNh7L26VYkMHQLyMgG1Nuzbm23ePADCw3gO2StHy\n7rZSugVwHf3uQgSAHQIGQCQBAyDStQLmGhnAMK4VMACGIWAARBIwACJdNGAJb5ICwJ6LBgyAdAIG\nQCQBAyCSgAEQScAAiHS5gHkzDoAxXC5gAIxBwACIJGAARBIwACJdN2DeTQog2nUDBkA0AQMgkoAB\nEEnAAIh0xYB5Mw6AAXy1HsATpZRa63RjOlK/+1MW+wgffQwAo+o3YGWzz32u1NynZaiWx5e3ARhS\nvwE7MqmafnW/VasQChvAXdtpQ+f6DdjWkTnZ1s4vleJ6GMA/qzWthiM5KGkTR611eX7NpQCuLCNg\n268FIr46AOBzMpYQa62ri2FHjgAwsN4DdnfD4fEjAIwqYwnx7ZQOIN1FAwZAOgEDINLVA2YzI0Co\nqwcMgFACBkAkAQMgkoABEOm6AfOtYADRrhswAKIJGACRBAyASALme5kBIgkYAJEEDIBIAgZApEsH\nzLeCAeS6dMAAyCVgAEQSsNvNTnqAQAIGQCQBAyCSgAEQ6av1AJ4opdRapxvTkfq9+f3IkadqdQEM\nIFK/ASubsMwlq7XOYds5cuZoAThZv0uItdZlhAQJgKV+Z2Bb2znZC7/rUQhL8cYcwKW99hrbUFLA\nVhfDfvW7ANi3fLWMiFm/S4hLEacSgDNlzMCmPRrz7YNHABhY7wGbU7Rt0pEjxx7CTnqAPBlLiACw\nImAARBKw/1hIBAgiYABEEjAAIgkYAJEE7Ha7eRMpgDwCBkAkAQMgkoD9YCc9QAoBAyCSgAEQScAA\niCRg/9hJD5BFwACIJGBrNiICRBAwACIJGACRBAyASAL2HxsRAYIIGACRBOwOGxEB+idgAEQSMAAi\nfbUewBOllFrrdGM6Ur/3WpTFSt+jj/mtWq0fAmToN2BlU5K5UnOflqFaHl/eBmBI/S4h1lqXEbob\npFLKtnNvYR4G0Ll+Z2B3raZW2znZ3d+yvGtmBnDXh+YDnxMTsOnMPp2TbSkWwBGrizINR3JQv0uI\nW3EnF4DPyZiBTblabjKsta72HG6PvMZGRIAIvQdsjtOjX9o/AsCokpYQT2YeBtAzAQMgkoABEEnA\n7nApDaB/AgZAJAHbYx8HQLcEDIBIAgZAJAG7zz4OgM4JGACRBOwJ+zgA+iRgAEQSMAAiCdhD9nEA\n9EzAAIgkYM/ZxwHQIQEDIJKAARBJwPbYxwHQLQE7xGUwgN4IGACRBAyASAL2hMtgAH0SsKNcBgPo\nylfrATxRSqm1TjemI/V7TnTkCACj6jdgZTPlmUtWa53DtnPkzNECcLJ+lxBrrcsINQySFAJ0qN8Z\n2F0vTK1WMzkzM4C7tutenYsJ2HRmX8jPG4tVitkYMKzlq2VEzPpdQtwyeQJgljEDm74WWG4ynHZt\nzHenn+1CBLiO3gM2x+nRL+0fed8wfB8YQF+SlhB7IGMAnRAwACIJ2FEuqwF0RcAAiCRgv+YyGEAP\nBAyASAL2Cy6DAfRDwACIJGCvcBkMoDkBAyCSgP2Oy2AAnRCwF1lFBGhLwACIJGAARBKwX3MZDKAH\nAvY6l8EAGhIwACIJ2CusIgI0J2B/YhURoBUBAyCSgAEQScBe5DIYQFsC9lcugwE08dV6AE+UUupi\nsrO8WxbpmA7OR6r5EcDo+g1Y+Tm1KfdmOjttO6FhtZp+ATTT7xJirXUZodXdSSnlbthO1sEQAC6n\n3xnYEfPK4c58a1U4q4sAd/UwH/iV4IAdTNFHi2UVERjG6qJMw5Ec1O8S4r7eTm5nwwEYX+oMrNa6\n2nO4PQLAwHoP2CpFq20d+x98DquIAE2kLiF2SMYAziRgAEQSsDdwxQ3gfAL2TlYRAU4jYABEErD3\nmFcRTcIAziFgAEQSMAAiCdjbWEUEOJOAARBJwN7JN4QBnEbAPsIqIsCnCRgAkQTszWzlADiHgAEQ\nScAAiCRg72cVEeAEAgZAJAH7CJMwgE8TMAAiCdineFcOgI8SsI+zigjwCQIGQCQB+yBbOQA+p/eA\nlZ+v/cu75dvOEQBG9dV6AA/tpGu6W78nONPt7ZFzxrmv1n/Tr1Js6wB4p35nYLXWZYRWdwG4uH5n\nYO+ymrqdX8F5EgbQs7jrL+MHrJ95m1VEoGfLV8uImPW7hDgS3QJ4u9QZ2LRrY75990iHTMIA3qX3\ngK1StNrWsf/BXXElDOC9LCGeTcYA3kLAAIgkYOfxzlIAbyRgAEQSsFOZhAG8i4CdTcMA3kLAAIgk\nYA2YhAH8nYABEEnA2jAJA/gjAQMgkoA1YxIG8BcC1gUNA/gtAWup43fPB+idgDVmIRHgNQIGQCQB\na88kDOAFAtYXDQM4SMC6YDcHwG8JWC8sJAL8ioD1SMMAnhKwjlhIBDhOwPpiIRHgIAHrl4YB7Phq\nPYAnSim11unGdKR+T1LK4gX+0cckqlW6AJ7rN2DLPs0ZW91ehurRxySaG1aKC2MA9/W7hFhrfRqh\nUkoZdLbiYhjAvn5nYEfMK4c7qVsVLnFmZh4GnCBuPhAcsIMpSizWxMUw4EyrizINR3JQv0uI+yJO\n7t9ZSAR4JGMGVmtd7TA8cmQwFhIBlrJ36z2Vvh1xspx+5f9pgAARL56pS4iXsnwWWUsEmAhYhu6/\nEgI4m4DFsKEDYEnAkmgYwEzAwmgYwETAgmkYcGUClsemRICbgIXSMAABS6VhwMUJWDANA65MwLJp\nGHBZAhZPw4BrErARaBhwQQI2CA0DrkbAxqFhwKUI2FA0DLgOARtNrT/eL1HGgFEJ2JhMxYDhCdiw\nNAwYm4CNTMOAgQnY4FYNkzFgGAI2vmXDbqZiwCgE7BKWWxNvGgYMQcAuxHIiMJKv1gN4opRSa51u\nTEfq98vwkSOsTCdmTlcp6wVGgBT9BqwsJghzxubbR46cPOAgtf5o2G1znQygf/0GbDXxetnq/yBs\nk2XDbqZiwDteb0/Wb8DeRbEe2S4n3kzF4MKWr5YRMbOJ4+q2GxQTnrcAAsbtdvO9YkCgjCXEaY/G\nfPvgEX7FiiKQZfDderYjvmA7/XIK4WoiXjwtIbK2uip2c2EM6JKAcZ+MAZ0TMPbIGNCtjE0ctLXa\n37G83f0iOTAsMzCO2s7GbiZkQDtmYPzO3LDthMxsDDiTgPEi64pAWwLGn2wzdlMy4BQCxhvcXVe8\nKRnwSQLGOykZcBoB4yPuLi2ujogZ8BcCxget/qGWFdMy4C8EjJM8Wl28mZYBLxEwznZwWrb9YIAl\nAaOlnWnZ3eN6BswEjC4c/Ceh/VtlwMx7IX5c6eO9ArOGMb3v4vxj939458e7hvFRPYzhZhg/9TCM\nHsaQwgyMAAfnZ0c+wIwNhiFg5LkboYNftn5/WN2PXCn333pf/6AfAsYgHqXlhfWY6bfc/Y1vWd25\nm8bbZkvL3Xnndg/n9nvGHwV4q5Tb7bb+OJ0mRalDP1WtJnPAyJ8C8LL+4zD4DGzsPNO/aTYzT5V8\nQQVvNPgMDIBR2UYPQCQBAyCSgAEQafBNHK0sdz9OVxnnI6dddCzlvwucq0c/czDzMFqdk6d/9hOG\nsfOgOwM7cxg9/I2cPIx5MA2fGKsx3Fo/MR496PkvXwcJ2Kcs/6ZXT9ATPh9Wd1efHucMZvs9DK3O\nyfKTcPWgpw1jHsP8EE3OxnIYrZ4Yt83ZaPXEmJ+i2wc9bRidfJrsPOjtxCfGb1lC/JRSSqvvQqu1\n9vAk2w6jyTnp5FRsD55/Nno4Fbd7w2jyxOjhtfjuGFqdjcTvmjUD+5TtV9w0PCfzl9UnP+52DPPd\nJmejkxep1TB8siw1ORuhfwUC9hFZT4JztDonqzWQTsbQajzby07Nh9HkVEwPvfy5+Ri2q6mnyX29\nsoT4fs1fHTrU9pz08Pm5usZw/gA6eVpuL9A2GUb9dmv6xcRqDFd+YrwmbMKYouGOpuUY+tyF2GT7\n3/xA5w/j0XLZycM48qDX2Re6HEzzYex8qp4zjE6eGC8QMAAiWUIEIJKAARBJwACIJGAARBIwACIJ\nGACRBAyASAIGQCQBAyCSgAEQScAAiCRgAEQSMAAiCRgAkQQMgEgCBkAkAQMgkoABEEnAAIgkYABE\nEjAAIgkYAJEEDIBIAgZAJAEDIJKAARBJwACIJGAARBIwACIJGACRBAyASAIGQCQBAyCSgAEQ6f8L\n/JuqfhPobAAAAABJRU5ErkJggg==\n", "output_type": "display_data"}], "prompt_number": 17, "cell_type": "code", "language": "python", "metadata": {}, "input": ["exo1()"]}, {"collapsed": false, "outputs": [], "prompt_number": 18, "cell_type": "code", "language": "python", "metadata": {}, "input": ["%% Insert your code here."]}, {"source": ["In this case, the matrix is recovered exactly, $A^\\star=A_0$."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["|A-A_0|/|A_0| = 2e-07\n"], "output_type": "display_data"}], "prompt_number": 19, "cell_type": "code", "language": "python", "metadata": {}, "input": ["disp(['|A-A_0|/|A_0| = ' num2str(norm(x-x0)/norm(x), 2)]);"]}, {"source": ["__Exercise 2__\n", "\n", "Compute, for several value of rank $r$, an empirical estimate of\n", "the ratio of rank-$r$ random matrice than are exactly recovered using\n", "nuclear norm minimization."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "png": "iVBORw0KGgoAAAANSUhEUgAAAkAAAAGwCAIAAADOgk3lAAAACXBIWXMAAAsSAAALEgHS3X78AAAA\nIXRFWHRTb2Z0d2FyZQBBcnRpZmV4IEdob3N0c2NyaXB0IDguNTRTRzzSAAANgklEQVR4nO3dzXbi\nuBqGUXRW7v+WdQYENzEufoxt+ZX2HvSioQaqJPjhEwpVaq0XAEjzv9YLAIA1BAyASAIGQCQBAyCS\ngAEQScAAiCRgAEQSMAAiCRgAkQQMgEgCBkAkAQMgkoABEEnAAIgkYABEEjAAIgkYAJEEDIBIAgZA\nJAEDIJKAARBJwACIJGAARBIwACIJGACRBAyASAIGQCQBAyCSgAEQScAAiCRgAET6ab2AfZVSWi8B\nIFKttfUSXug8YJedvwellPN/j5+w/rasv6HoxV/2X3/Eq39biABEEjAAIgkYAJGyd4FfSt/mBmgi\n4uJpAgMgkoABEEnAAIgkYABEEjAAIgkYAJEEDIBIHQYs4iO8APhSVx/mK10A4+gqYNffG59lrIOo\nnf7X4QEa6CpgvZoarGTAfuI2sfoPWPRFf/bjpGTAfu4//DAiZv0HLNr046RkADMClkHJAGY6DNj5\n/wmAbygZwFWHARuEkgGDE7B4SgaMScD6oWTAUASsQ0oGjEDAeqZkQMcEbAhKBvRHwMaiZEA3BGxQ\nSgakE7DRKRkQSsD4pWRAFgFjTsmACALGPykZcGYCxmtKBpyQgPEBJQPOQ8BYQ8mA5gSMrygZ0IqA\nsY3nJZMxYHMCxsYWSyZjwOb+13oBdKvWebFKmc9nAKsJGPuSMWAnAsYRZAzYnIBxHBkDNiRgHE3G\ngE0IGG3IGPClvGP05XaRqw+Hsp88xDldv1EO3AMrhAWslDLF6f7284c4ORkDVrCFyFnYVAQ+EjaB\nvaP8vebN/tdkdnKmMWilpL1g7CdgtdbrV3+6Md3fblGsJGNwvNmbMg1X8qZ+AuZ9r/7IGPBEWMDu\np6vZkY3Fh+iAjAGLwgJ2WYrTdI9udUzGgBmnEEnipCIwETDyyBhwETByyRgMTsDIJmMwLAGjBzIG\nAxIw+iFjMBQBozcyBoMQMPokY9A9AaNnMgYdEzD6J2PQJQFjFDIGnREwxiJj0A0BY0QyBh0QMMYl\nYxBNwBidjEEoAYPLRcYgkIDBfxYzBpyTgMHcY8aAExIwWDY1zBAG5yRgAEQSMPgnQxicmYABEEnA\n4BlDGJyWgAEQKS9g5ebJowcvib4ZwuCcflov4DOllHq7nNzfnt3z+BBsohS/IgZnkTeBwfFEC04o\nbAJ76bp/eD9+zXYUTWasU+vvFqIhjF7Fvf/ST8D+tbuoWADvePLS/5xsIcK7nOaAUwmbwGqt0+uC\n2by1+BAAvQoL2GUpTnYLOYx3wuA8bCECEEnA4DPeCYOTEDAAIgkYfMwQBmcgYABEEjBYwxAGzQkY\nrKRh0JaAARBJwGA9Qxg0JGAARBIw+IohDFoRMAAiCRh8yxAGTQgYAJEEDDZgCIPjCRgAkQQMtmEI\ng4MJGGxGw+BIAgZAJAGDLRnC4DACBkAkAYONGcLgGAIGQCQBg+0ZwuAAP60X8LFyuyTU6SLx9/7F\nRwHoTFjASilTme5vX/4Wq3jdS2u1/o5fpVy8moI9dLiFOAsbAF0Km8BWsLVIK4YwssTtXfUWsMfx\nS7E4Aw3j/OLeiOlwCxHOQ7RgP2EBq7WWm/vTHNMN8xZn40g97CRvC/ExUdM96gUwjrAJDBIZwmAP\nAgZAJAGDIxjCYHMCBkAkAYODGMJgWwIGQCQBg+MYwmBDAgZtaBh8ScDgUH7bHrYiYHA0G4mwCQED\nIJKAQQOGMPiegAEQScCgDUMYfEnAAIgkYNCMIQy+IWAARBIwaMkQBqsJGACRBAwaM4TBOgIG7WkY\nrCBgAEQSMDgFQxh8SsAAiPTTegEfK7cXqPXhH1Z68hCcX62/41cp/tkweC0sYKWUKU73ty+3el3v\nmT0EQH9620IspagXubwTBu8Lm8CeWxzOyt8rgbYBLCppr5u6CtgixSKLd8Jo5fFNmZPrbQsRgEGE\nTWC11sejhtcNw8WHIJEhDN4RFrDLUpyme3SLbmgYvGQLEYBIAgYn5Ug9PCdgAEQSMDgvQxg8IWAA\nRBIwODVDGPyLgAEQScDg7AxhsEjAAIgkYBDAEAaPBAzCaBhcCRhk8ImIMCNgEMNGItwTMAAiCRgk\nMYTBRMAAiCRgEMYQBlcCBkAkAYM8hjC4CBgAoQQMIhnCQMAgnoYxJgGDVD5cisEJGASzkcjIflov\n4GPl9kytD68/y92T+PFRAHoSFrBSylSm+9sT3WI0tf6OX6XYVGQsvW0hllKKzRSAAYRNYC9dJ7DZ\noPb4B6AnhjA2Effqv6uALcZJsQDecX+1jIhZP1uIEV9u2InjiAwobAKrtT6eQrxuGC4+BECvwgJ2\nWYrTdI9uMTLvhDGafrYQARiKgEE/vBPGUAQMuqJhjEPAAIgkYNAbQxiDEDAAIgkYdMgQxggEDIBI\nAgZ98rvMdE/AoHN2EemVgAEQScCgW45y0DcBAyCSgEHPDGF0TMAAiCRg0Dnn6emVgMEo7CLSGQED\nIJKAQf8c5aBLAgZAJAGDIRjC6I+AARBJwGAUztPTGQGD4dhFpA95ASs3T/7AkesBoImwgJVS6s1i\nqNQLnnCUg56EBey5a95arwKAI/y0XsDuZjOZwjG4Wn/Hr1Ic6+CPuB2sfgJ2/dJP/51CpVgA77i/\nWkbErJ+ATV96G4nw3DSEQbSwgN2f3VAs+JJdRKKFBeyytCU4u0fMAEbQ1SlE4E3O09MBAQMgkoDB\noAxhpBMwACIJGIzLgSeiCRhgF5FIAgZAJAGDoTnKQS4BAyCSgMHoDGGEEjAAIgkY4Dw9kQQM+I9d\nRIIIGACRBAy4XBzlIJCAARBJwIBfhjCyCBgAkQQM+I/z9AQRMGCBXUTOT8AAiCRgwB+OcpBCwACI\nJGDAnCGMCD+tF/CxcntK1YfzUk8eAqAzYQErpUxxur89ud6z+BAAPelqC1G0YCt2ETm/sAnspfLw\nbJvdI3IAix6vnyfXW8CmLcTZPcCnav0dv0rxCR1DuL9aRsSsny3EiC83AFsJm8BqrY9HDa9HNhYf\nAr5hCOPMwgJ2WYrTdI9uAYyjny1EAIYiYMAzztNzWgIGQCQBA14whHFOAgZAJAEDXnPClxMSMOAD\ndhE5DwEDIJKAAW9xlIOzETAAIgkY8C5DGKciYABEEjDgA87Tcx4CBqxhF5HmBAyASAIGfMZRDk5C\nwACIJGDAxwxhnIGAARBJwIA1nKenOQEDvmIXkVYEDIBIAgas5CgHbQkYAJF+Wi/gY+X2Yq8+vIn8\n5CFgD7X+jl+lONbB0cICVkqZ4nR/e3K9Z/EhAHrS1RaiaMHxPO1oJWwCe8ds/Cp/318WOdiJXcR0\nJe00TlcBu371Z4lSLIB3PHnpf05dbSFe5ApacJ6eJsImsFrr41HD657h9X4HEQEGERawy1KZrvco\nFjTkPD3H620LEYBBCBiwDYMXBxMwYGOOcnAMAQMgkoABm3GeniMJGACRBAzYkiGMwwgYAJEEDNiY\n8/QcQ8CAvdhFZFcCBkAkAQO25ygHBxAwACIJGLALQxh7EzAAIgkYsBfn6dmVgAG7s4vIHgQMgEgC\nBuzIUQ72I2AARBIwYF+GMHYiYABEEjBgd87TswcBA45jF5EN5QWs3Dz5A0euB4Amflov4DOllHrb\njLi/Pd3TYlHAa7X+jl+l2FFkG3kT2BO11uqZATCGsAlshdlYpnDQiiHs5OI2sfoPmGIBvOP+ahkR\ns662EAEYR1jAaq3TKcT70xxtVwW8yadysKG8LcTHLcHZPfYMAUYQNoEB6QxhbEXAAIgkYMDRDGFs\nQsAAiCRgAEQSMKABu4h8T8AAiCRgQBuGML4kYABEEjCgGR+bwzcEDGjPLiIrCBgAkQQMaMlRDlYT\nMAAiCRjQmCGMdQQMgEgCBrTnPD0rCBhwInYReZ+AARBJwIBTcJSDTwkYAJEEDDgLQxgfETAAIgkY\ncCLO0/O+n9YL2FK57TtUTwIIV4qY8UI/ASulTN26vw1Al2whAufiKAdv6mcC+5fy90lgMoMgGtZO\nwKWy/4ApFsSpVbp4rf+AAYm88myrlHL+IayfgNVanUIEGEc/AbvoFsBInEIEIJKAARBJwACIJGAA\nRBIwACIJGACRBAyASAL2lRL+cTfW35b1NxS9+Ev++jchYABEEjAAIgkYAJE6/5eLbRMDrHP+OnQe\nMAB6ZQsRgEgCBkAkAQMgkoABEEnA1is3rReyXu76p2WHfhe6Wf/i/57c/WoTv/6PX/ys9W/op/UC\nUl1/Yq5nOEuJPMw5LTtr/bOrz7TylL/F47Um67vwuP6gq+did4O+/otf/KD1b07AvnL/BOAY09O1\n9UJWmq0/7odntv7rdTPl27H4wxP0LE7/4d+cgK0X99r/UdBTt2+5P0LpPIujCdigEjffuhR99bku\nfvpv6N8il2exgEFjudedwa+eNCdgK93v+yc+ddPXf5X+t7ifYC6Zf4Vo6T8/6ev/ntdNAETye2AA\nRBIwACIJGACRBAyASAIGQCQBAyCSgEEbI3+IOGxCwKAZv4UJ3xAwACIJGACRBAyASD4LEYBIJjAA\nIgkYAJEEDIBIAgZAJAEDIJKAARBJwACIJGAARBIwACIJGACRBAyASAIGQCQBAyCSgAEQScAAiCRg\nAEQSMAAiCRgAkQQMgEgCBkAkAQMgkoABEOn/JyPcO5N8wtAAAAAASUVORK5CYII=\n", "output_type": "display_data"}], "prompt_number": 20, "cell_type": "code", "language": "python", "metadata": {}, "input": ["exo2()"]}, {"collapsed": false, "outputs": [], "prompt_number": 21, "cell_type": "code", "language": "python", "metadata": {}, "input": ["%% Insert your code here."]}, {"source": ["Noisy Completion using Forward-Backward\n", "---------------------------------------\n", "In the case where $x_0$ does not have low rank but a fast decreasing\n", "set\n", "of singular values $ (s_i(x_0))_i $, and if one has noisy observations\n", "$y = \\Phi x_0 + w$, where $w \\in \\RR^P$ is some noise perturbation,\n", "then it makes sense to consider a Lagrangian minimization\n", "$$ \\umin{x \\in \\RR^{n \\times n}} \\frac{1}{2}\\norm{y-\\Phi x}^2 + \\la \\norm{x}_{\\star} $$\n", "where $\\la>0$ controls the sparsity of the singular values of the\n", "solution.\n", "\n", "\n", "Construct a matrix with decaying singular values."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 22, "cell_type": "code", "language": "python", "metadata": {}, "input": ["alpha = 1;\n", "[U,R] = qr(randn(n));\n", "[V,R] = qr(randn(n));\n", "S = (1:n).^(-alpha);\n", "x0 = U*diag(S)*V';"]}, {"source": ["Display the spectrum."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "png": "iVBORw0KGgoAAAANSUhEUgAAAkAAAAGwCAIAAADOgk3lAAAACXBIWXMAAAsSAAALEgHS3X78AAAA\nIXRFWHRTb2Z0d2FyZQBBcnRpZmV4IEdob3N0c2NyaXB0IDguNTRTRzzSAAAM60lEQVR4nO3d3XLa\nvAKGUWtP7v+WtQ8o/qhxzE/B0iutddBhbBpUSPxUsgOl1roAQJr/tR4AALxDwACIJGAARBIwACIJ\nGACRBAyASAIGQCQBAyCSgAEQScAAiCRgAEQSMAAiCRgAkQQMgEgCBkAkAQMgkoABEEnAAIgkYABE\nEjAAIgkYAJEEDIBIAgZAJAEDIJKAARBJwACIJGAARBIwACINGLBSSushAPB1P60H8EnSBTCPoWZg\ntdZaa+tRAHCGoWZg965TMjMzgNf0Px8YPGAXTV6GUkoPL79hGMaBTkZiGH0Oo/UQHhtqCRGAeQgY\nAJEGDFgPs28Avq2LxdbvuaziDv1PBPi8Tk7FHRtwBgbADAQMgEgCBkAkAQMgkoABEEnAAIgkYABE\nmiJgCe/pBcBrpggYAOMRMAAiCRgAkQQMgEgCBkAkAQMgkoABEEnAAIgkYABEEjAAIgkYAJEEDIBI\nAgZAJAEDIJKAARBJwACIJGAARBIwACIJGACRfloP4GWllMuNWusTu8qybO8GwADCAlZKWeN0e/t4\nFwDjsYQIQKSwGdgz1oXE3Y1mZgC7dg+ePRsnYLXWy7O/3tjsbTEogBibkzINR/KkcQLmvBfAVMIC\ndju72lyysbsLgFGFBWzZi9O6RbcA5uEqRAAiCRgAkQQMgEgCBkAkAQMgkoABEEnAAIgkYABEEjAA\nIgkYAJEEDIBIAgZApFkClvDRNgC8YJaAATAYAQMgkoABEEnAAIgkYABEEjAAIgkYAJEEDIBIAgZA\nJAEDIJKAARBJwACIJGAARBIwACL9tB7Ay8r1k1Fqrb/t3d0FwEjCAlZKWeN0e3uz5X4XAIOxhAhA\npLAZ2EMHS4hWFwEOlLSPrh8nYMeri4t0ARy6PUhGxGz8JUTZAhhS2Ays1np/FeJlvrW7C4BRhQVs\n2YvTukW3AOYx/hIiAEMSMAAiCRgAkQQMgEgCBkAkAQMgkoABEEnAAIgkYABEEjAAIgkYAJEEDIBI\nAgZAJAEDIJKAARBJwACINFHArh/XDMAIJgoYACMRMAAiCRgAkQQMgEgCBkAkAQMgkoABEEnAAIgk\nYABEEjAAIgkYAJF+Wg/gZeX6noa11t3tu3sBGExYwEopa5luby9/F6t4416A0Q24hLgJGwBDCpuB\nvaGUsiz7kzYAVnFrV6MF7D5Rtdb1RVEvgN/EnYgZcAkRgBmEzcBqrfdXIa6zLiuEAPMIC9iytwy4\nblEvgHlYQgQg0hQBMzEDGM8UAQNgPAIGQCQBAyCSgAEQScAAiCRgAEQSMAAiCRgAkQQMgEgCBkAk\nAQMgkoABEEnAAIgkYABEEjAAIgkYAJEEDIBIAgZApLkCVkrrEQDwIXMFDIBhCBgAkQQMgEgCBkAk\nAQMgkoABEOmn9QBeVq7Xwtdan98FwGDCAlZKWeN0e3u51uuyZbMLgPGEBeyh24wBMLChArY7Obuu\nK0oawJGS9mZFQwVs13VRsfU4APp2f1Kmc65CBCBS2Ays1np/qeFlwXB3FwCjCgvYshendYtuAczD\nEiIAkQQMgEgCBkAkAQMgkoABEGmWgLk+EWAwswQMgMEIGACRBAyASAIGQCQBAyCSgAEQScAAiCRg\nAEQSMAAiCRgAkQQMgEgCBkAkAQMgkoABEEnAAIgkYABEEjAAIgkYAJEEDIBI0wWslNYjAOATpgsY\nAGMQMAAi/bQewMvKdRGw1vrbrt29AIwkLGCllLVMt7dXugUwidGWEEspxXUaABMIm4E9dJmBbSZq\n685GgwIIEPe//6ECtrt+eFOyc0cDEOX2EBoRs3GWECOebgA+JWwGVmu9vwrxsmC4uwuAUYUFbNmL\n07pFtwDmMc4S4kPqBjCSiQIGwEgEDIBIAgZAJAEDIJKAARBpxoD5jWeAAcwYMAAGIGAARBIwACIJ\nGACRBAyASAIGQKS5Aub9fAGGMVfAABiGgAEQScAAiCRgAEQSMAAiTRow7+cLkG7SgAGQTsAAiCRg\nAEQSMAAiCRgAkQQMgEjTBcz7+QKMYbqAATCGvICVq4M7nDkeAJr4aT2A15RS6nUR8Pb27R1OHxQA\nDeTNwA7sJg2AIYXNwN6wmZMpHMCuuBWscQJ2eerXP9dQ/VasUlyRCPCf26NlRMzGCdjxuTEABhMW\nsFrr+v8CxQKYWVjAlr0lwc0WMQOYwVBXIQIwDwEDIJKAARBJwACINGPAXOQBMIAZAwbAAAQMgEgC\nBkAkAQMgkoABEGnqgCW82zIA+6YOGAC5BAyASAIGQCQBAyCSgAEQScAAiDRpwLyfL0C6SQMGQDoB\nAyCSgAEQafaAeTcpgFCzBwyAUAIGQKR5A+ZKeoBo8wYMgGgCBkCkn9YDeFm5XjhY7xYBD3YdfkHL\niQB5wgJWSlnjdHt7ddmyuwuAkQy1hChaAPMIm4E9VO5+M3mzReQAdt0fPzs3WsDWJcTNll/u7J04\nAP64PVpGxGycJcSIpxuATwmbgdVa7y81vFyysbsLgFGFBWzZi9O65e1uuZIeIM44S4gATEXAAIgk\nYABEmj1gTn0BhJo9YACEErA//BYZQBYBAyCSgAEQScAAiCRgLkQEiCRgAEQSMAAiCdh/XEkPEETA\nAIgkYABEErBlcSEiQCAB+4vTYAApBAyASAIGQCQB+8NpMIAsArblNBhABAEDIJKAARBJwP7jNBhA\nEAHb4TQYQP8EDIBIAgZAJAH7i9NgACl+Wg/gZeV6hqre1eZg1+uPImYAXQsLWClljdPt7dVly+4u\nAEYy1BKiaAHMI2wG9ozN9Kv8fVH8w8jV6jJ6YEYl7dg3VMAuz/4mUW9Py5wGA6Zy8F//Pg21hLhY\nRQSYRtgMrNZ6f6nhZc3wsv0jFyKuq4gmYQDdCgvYslemyxZzL4CpjLaE+ClqCNA5AXsg4UQmwIwE\nDIBIAvardRXRJAygQwIGQCQBAyCSgB2xigjQLQEDIJKAPWASBtAnAQMgkoA9ZhIG0CEBAyCSgD3F\nJAygNwIGQCQBe5ZJGEBXBOwdGgbQnIC9wIeEAfRDwF5jIRGgEwL2Pg0DaEjAXmYhEaAHAvYOC4kA\nzQnYmzQMoC0B+wANAzifgL3v9mSYhgGcTMD+iYYBtCJg/0rDAJoQsA/QMIDz5QWsXB3c4czxXGgY\nwMl+Wg/gNaWUem3F7e11S4tB/VHrf+kqxe87A3xX3gzsQK21Nu2GeRjAacJmYG/YTMu+XTjzMCBU\n20WsN4wfsPPnZJuGLd4+EUhwe7SMiNlQS4j9qNVyIsB3hc3Aaq3r/wsOrubohKkYwPeEBWzZWxLc\nbOkqZrcNW5wVA/gcS4hfd7+caEUR4N8J2ElkDOCzBOxUm/VDGQN4m4CdbTMVW2QM4C15F3GM4dKw\nzfUdt7sAOGYG1tL9bGwxIQN4jhlYe/ezscWEDOARAevFGiolA3iGgHVHyQCeIWD9eliyRcyAiQlY\ngN9KtogZMDEBS3JQskXMgMkIWKSHn9Wy2ahnwHgELN4zHzymZ8B4BGwo929StWt3u6oBWQRsZE/2\n7GCvqgHdErCJ7L5t1bHf7iBsQHMCNrXdDj3zTowH99E24BwCxtbbVXvyngoHfISA8ZSD6rz63vlP\n3l/ngGMCxr86Ls3bHw3z0l9UO5iQgPFdD9PykQ8/+5cvIn4QSsBo7KV+fOOjPj/7NeUQTiNg31JK\nqR0czAYbxhtf4+SPt/7qw338lRzs28MwZiNgDO7vt9p689BwcgV/84Vh1De+pqMrnRAweOyzh+xS\nyrIER6BtR48/k+H4rzAYAYMGzjykdjJ9/JQ3/jlP/5V35qNfcDSMgzfvfmNXetoHX2wtfXw/AodG\nPgrl6j8Og8/Axs4zEOTfJ0xsDD4DA2BU/2s9AAB4h4ABEEnAAIg0+EUcTdz+tux6GeSZ5xrvH3Tm\nYawP3cmzsT5uq2dj87jNn43LQ7f93li8KIc/Iw1fnWMC9kmbH8vNN8SZr/36bXc5NEw+jNvXpfmz\n0XYY9wfrJsPYPBVtvzeaPxv35Th5GMcHrvPH8zxLiJ9Ua+3h1e1hDEs3w+jnR+5ypG49imW5a0bb\nkfQwjMl1cuB6gxnYsHo4NHRyvO7E7Xy0+TAWr87VOslo/oQ0H0AcARvQZtbf0GYB/XyXh17/bPic\n9PBy9KZ5y3fP+pxvbWcPEc1iCXFMzQ+Xnfwc1qul6XPSybNBny4dbf4zm6j9KtN42l7wdn99V5Nh\n7D6oqxCXDp6NTi4w20y/PBvNh5F4FaKAARDJEiIAkQQMgEgCBkAkAQMgkoABEEnAAIgkYABEEjAA\nIgkYAJEEDIBIAgZAJAEDIJKAARBJwACIJGAARBIwACIJGACRBAyASAIGQCQBAyCSgAEQScAAiCRg\nAEQSMAAiCRgAkQQMgEgCBkAkAQMgkoABEEnAAIgkYABEEjAAIgkYAJEEDIBI/wf6O2LLMuCW4wAA\nAABJRU5ErkJggg==\n", "output_type": "display_data"}], "prompt_number": 23, "cell_type": "code", "language": "python", "metadata": {}, "input": ["clf;\n", "h = plot(S); axis tight;\n", "set(h, 'LineWidth', 2);"]}, {"source": ["Number of measurements."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 24, "cell_type": "code", "language": "python", "metadata": {}, "input": ["P = n*n/4;"]}, {"source": ["Measurement operator."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 25, "cell_type": "code", "language": "python", "metadata": {}, "input": ["I = randperm(n*n); I = I(1:P); I = I(:);\n", "Phi  = @(x)x(I);\n", "PhiS= @(y)reshape( accumarray(I, y, [n*n 1], @sum), [n n]);"]}, {"source": ["Noise level."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 26, "cell_type": "code", "language": "python", "metadata": {}, "input": ["sigma = std(x0(:))/5;"]}, {"source": ["Measurements $y=\\Phi x_0 + w$ where $w \\in \\RR^P$ is a Gaussian white noise."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 27, "cell_type": "code", "language": "python", "metadata": {}, "input": ["y = Phi(x0)+sigma*randn(P,1);"]}, {"source": ["It is possible to find a minimizer of the Lagrangian minimization problem using the\n", "forward-backward method:\n", "$$ x_{k+1} = \\text{Prox}_{\\ga \\lambda G}\\pa{ x_k - \\ga\\Phi^*(\\Phi x_k - y) }. $$\n", "where $\\ga < 2/\\norm{\\Phi^* \\Phi} = 2. $\n", "\n", "\n", "Value for $\\lambda$."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 28, "cell_type": "code", "language": "python", "metadata": {}, "input": ["lambda = .01;"]}, {"source": ["__Exercise 3__\n", "\n", "Implement the forward-backward method, monitor the decay of the enrgy\n", "minimized by the algorithm."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "png": "iVBORw0KGgoAAAANSUhEUgAAAkAAAAGwCAIAAADOgk3lAAAACXBIWXMAAAsSAAALEgHS3X78AAAA\nIXRFWHRTb2Z0d2FyZQBBcnRpZmV4IEdob3N0c2NyaXB0IDguNTRTRzzSAAANp0lEQVR4nO3d0bqa\nugKFUThf3/+VORe2bgREVCSZyRgX3Zbarmyl/k2IrnGapgEA0vyv9AAA4BMCBkAkAQMgkoABEEnA\nAIgkYABEEjAAIgkYAJEEDIBIAgZAJAEDIJKAARBJwACIJGAARBIwACIJGACRBAyASAIGQCQBAyCS\ngAEQScAAiCRgAEQSMAAiCRgAkQQMgEgCBkAkAQMgkoABEEnAAIgkYABEEjAAIv0pPYDfGse//y07\nDIA40zSVHsILjQfspuDTMI5jDSeBYRhGtWMwjGqHUXoIr1lCBCCSgAEQScAAiFTFYuvv3FZxm/5f\nBDhfJZfi9pmBARCpul2I960vi/jvHL8deXaHYRjG0SQMoDV1BWw+aT14e/7b7yWrf+YLwJeClxAX\noRItgK7UNQP73rPp184CIwBDyJuX51IDdnug7z9O03S7/axPugWwb/46GRGz1IBtXhJTKYB+1BWw\n+0RqWCVqfw1wPiF7dh8AWtL4hr37JLjp/0uAk0Vs5w7ehQhAzwQMgEjNByxgIw0AH2g+YAC0ScAA\niCRgAEQSMAAiCRgAkQQMgEgCBkAkAQMgkoABEKmXgCV8axsA3tBLwABojIABEEnAAIgkYABEEjAA\nIgkYAJEEDIBIAgZAJAEDIFL7AZum0iMA4AfaDxgATRIwACIJGACRBAyASAIGQCQBAyCSgAEQScAA\niNRRwMax9AgAOE9HAQOgJQIGQCQBAyCSgAEQScAAiCRgAETqImC+JRhAe7oIGADtETAAIgkYAJEE\nDIBIAgZAJAEDIFJfAfOB9ADN6CtgADRDwACIJGAARBIwACIJGACRBAyASH9KD+C18d/m9+nxU+U3\nj4/jOG19+Pw02UMP0JTaAzYP0svbo0YBdKOdJcRncy8AmlT7DOx7s2mZvAE8FbeI1UjAbo/7/cf5\nVGy20lhkaAAZFvsJCo7koEYCtnltDICG1R6waZoWuw1viVofB6ArtQdsWPXp/tMn2+VfxGwcB70D\naEA7uxAB6IqAARBJwACIJGAARBIwACJ1FDCbDwFa0lHAAGiJgAEQScAAiCRgAETqMWAJH7IMwAs9\nBgyABggYAJEEDIBIAgZAJAEDIJKAARCpr4D5OESAZvQVMACaIWAARBIwACIJGACROg2Yj0MESNdp\nwABIJ2AARBIwACIJGACRBAyASN0FzKdJAbShu4AB0AYBAyCSgAEQqd+A+TAOgGj9BgyAaAIGQCQB\nAyCSgAEQqceAeS8zQAN6DBgADRAwACIJGACRug6Y9zID5Oo6YADkEjAAIgkYAJEEDIBIAgZApE4D\n5sM4ANJ1GjAA0gkYAJF6D5j3MgOE6j1gAIQSMAAi/Sk9gKXx36Le9LhTcH382ZHJFkOADtQVsHEc\n5zV6eft243bkfnx+BwBaFbyE+GWlNA4gWl0zsHeNj5sIN5cQF/cxOQPYNKZty84O2H3N8Nka46BY\nAMfMXy0jYpa6hHjig5vwNAGwVNcM7LYX4377duO+R2N+fH3k2fZFAJpUV8CGrfzci7V/T90C6Erq\nEiIAnRMwACJ1HTCLjgC5ug4YALkEDIBIAjYM3goGEEjAAIgkYABEEjAAIvUeMDvpAUL1HjAAQgkY\nAJEE7C876QGyCBgAkQQMgEgCBkAkAbOTHiCSgAEQScAAiCRg/7GTHiCIgAEQScAAiCRgw2AjIkAg\nAQMgkoABEEnAHtiICJBCwACIJGAARBKwv2xEBMgiYABEEjAAIgnYko2IABEEDIBIAgZAJAH7j42I\nAEEEDIBIArbBPg6A+gkYAJEEDIBIAvbAPg6AFAIGQCQB22YfB0DlBAyASAIGQCQBW7KPAyCCgAEQ\nScCeso8DoGYCBkAkAQMgkoBtsI8DoH4CBkAkAdtjHwdAtf6UHsDS+C8a0+NC3vr44siz3whAk+oK\n2DiO8z69vL2ZrvkdAGhVXQF7y7pSt5KdUq9psn4IULXggA2zudfwuLQ4b9j4GKJ38zaONiUCXRjT\n/tmeHbDFEuLOfQDYt/NP/zql7kKMeHAB+J26ZmDTNG3uNlwfXx85fReiy2AANWt8w96XOxLvAWv6\nQQJYitjOnbqECEDnBAyASAK2p/oJNEC/BOwQuzkAaiNgAEQSMAAiCdgLLoMB1EnAjnIZDKAqAgZA\nJAEDIJKAveYyGECFBOwNLoMB1EPAAIgkYIdYRQSojYC9xyoiQCUEDIBIAgZAJAE7ymUwgKoI2Ntc\nBgOogYABEEnA3mAVEaAeAvYJq4gAxQkYAJEE7D1WEQEqIWAfsooIUJaAARBJwN5mFRGgBgL2OauI\nAAUJGACRBOwTVhEBihOwr1hFBChFwACIJGAfsooIUJaAfcsqIkARAgZAJAH73H0V0SQM4HoCBkAk\nAQMgkoB9xSoiQCkCBkAkAfuWN4QBFCFgp7GKCHAlAQMgkoCdwFYOgOsJGACRBOwcJmEAFxMwACIJ\nGACRBOw0VhEBriRgAEQSsDOZhAFcRsAAiCRgJzMJA7jGn9IDWBr/vfBPj5+Suz6+ec9xHCcfrwvQ\ngboCNs/Pkdu3G/cjYx2znmn6O/0aR59VD/ArdQXsLesp2jRN64YtjpifAWyqZA5wXHDAhmMPd5Fi\nmYQBcRaXYwqO5KDsTRzTNM0XD+c/AtC21ICtFwbvMatkkdB2RICfqmsJcX4Ra7FrY3F8854A9KPx\nTefFd9Xfp19NP8xAa4q/eB6RuoQIQOcE7LdcCQP4EQEDIJKA/ZxJGMAvCBgAkQTsCiZhAKcTsKtp\nGMApBOwi1b+hAiCMgF3HQiLAiQQMgEgCdimTMICzCFgxGgbwDQG7mt0cAKcQsAIsJAJ8T8AK0zCA\nzwhYGRYSAb4kYMVYSAT4hoBVQcMA3iVgJVlIBPiYgBVmIRHgMwJWEQ0DOE7AyrOQCPABAauChUSA\ndwlYLTQM4C0CViMNA3hJwCriYhjAcQJWFwuJAAcJWHU0DOAIAauahgE8I2A1ml8M0zCATQJWKQ0D\n2Cdg9dIwgB0CVjUb6wGeEbDa2ZQIsEnAAmgYwJqAZdAwgAUBi6FhAHMClkTDAO4ELIyGAdwIWB4N\nAxgELNS8YTIG9EnAUvmcDqBzAhZMw4CeCVg2DQO6JWDxNAzok4C1QMOADglYIxYNkzGgeQLWjmky\nFQM6ImCt0TCgEwLWIMuJQA8ErE2Lb+WsYUB7BKxZLokBbftTegBL478X2ulxErE+vjjy7Dd2bpr+\nS9fthocHaENdARvHcd6nl7fv6brdWPyUm9uDMc+YhwdoQPAS4qJSorXPzg6gMXXNwN41rl6G19Ov\nxX167tx8OXGwogg8Wr+iVi47YPOrX7cf133quVhri+XEwYoi8M/81TIiZqlLiJsPrlYdtN6gmHCu\nAjyoawY2TdPmbsP18cWR+SRsULJjrCgC0RrfsGdH4hGL6ZcHDIh48UxdQuREVhSBRALGXzIGZBEw\nHqw/RFHGgDoJGEuLqdggY0CV6tqFSD023zE2/yWAsszA2LOejQ0mZEAdzMB47d4w7xsD6mEGxhtc\nHgPqYQbG21weA2ogYHxonbFByYALCRhf2bw8NigZ8HuugXGOzf2Kg4tkwM+YgXEmEzLgMgLGT7ws\n2SBmwHcEjN96VrLBtAz4joBxESUDziVgXO1IyQYxA14RMIpZfPuxBTED9gkYVdiZlg1iBmwRMOqy\nPy1bH9Qz6JaAUa+XMRtMzqBjAkaG9afgr5mcQVcEjEjvTs7WvwtIJ2DEOzI5e/ZLkga5BIzWHO/Z\ns19VNYggYDRuXaOXn46vahBBwOjOs2/7su/ZHYQNShEwGIaPJmov76Zt8FMCBtue5ef49+fcv6e8\nwZcEDN6zE563vvf0wTvrHDwjYHCas9r22W+UOnojYL81juNUweuKYRQfxtY1todhfFy4L/+ECp6Q\nrk+MaocRQcCgCsdfsr5P3Sl/2jR5vwGFCRiE+aAQ5zZv/8/86GtNLze8bH7Q5e2gZHZLwKB9z3dU\nHl2t+kUCj9v/fqfnje1FR0/7Mi82uD59Ru7DO9jsd+8fp/HF1rHsXzvgqMUL0bjzOs416o9D4zOw\ntvMM7ar6b+7OzObIL3GWxmdgALTqf6UHAACfEDAAIgkYAJEa38RRxH3r4/364vrIlYO5fdFSY1h8\n3bIPRdlh7DwXV46ntmGsf3rZMHa+aNmH4uJhvDwTCv613SdgP3F/1qdpWvwlufgVc/11rxzD+q9i\nwYei4DDmb+dYPxeXPTvrd5UUOVHXw9h/fC4YQ6kTdfOhKHKi7pwJVw7jXZYQz1fJE1zPqTaOYz2D\nKWKaphr+9xfDKDWkxTAKfTTlxjNy/Ylaz4lReggfMgP7lc5fsu/WixKl3P8tWXwkVXGi3jhRE88E\nATvfYtJdcAzzH3u2eamDCk/UuBfQc5U6UWs4Ez4jYD9R/FRYX2UpOx7qVNuJWnYwPQt98AXsZItJ\nz22Nu/genlJjWH/dnofxbDBFnp06T9Sh0KNRyRlSZBhHzoQaToxN/tUDQCS7EAGIJGAARBIwACIJ\nGACRBAyASAIGQCQBAyCSgAEQScAAiCRgAEQSMAAiCRgAkQQMgEgCBkAkAQMgkoABEEnAAIgkYABE\nEjAAIgkYAJEEDIBIAgZAJAEDIJKAARBJwACIJGAARBIwACIJGACRBAyASAIGQCQBAyCSgAEQScAA\niCRgAET6P1uISczX5mAPAAAAAElFTkSuQmCC\n", "output_type": "display_data"}], "prompt_number": 29, "cell_type": "code", "language": "python", "metadata": {}, "input": ["exo3()"]}, {"collapsed": false, "outputs": [], "prompt_number": 30, "cell_type": "code", "language": "python", "metadata": {}, "input": ["%% Insert your code here."]}, {"source": ["__Exercise 4__\n", "\n", "Plot the error $\\norm{x^\\star-x_0}/\\norm{x_0}$ as a function of the mutiplier\n", "$\\lambda$."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 31, "cell_type": "code", "language": "python", "metadata": {}, "input": ["exo4()"]}, {"collapsed": false, "outputs": [], "prompt_number": 32, "cell_type": "code", "language": "python", "metadata": {}, "input": ["%% Insert your code here."]}], "metadata": {}}], "nbformat": 3, "metadata": {"kernelspec": {"name": "matlab_kernel", "language": "matlab", "display_name": "Matlab"}, "language_info": {"mimetype": "text/x-matlab", "name": "matlab", "file_extension": ".m", "help_links": [{"url": "https://github.com/calysto/metakernel/blob/master/metakernel/magics/README.md", "text": "MetaKernel Magics"}]}}}