Problem 44734. Solve the 2-norm Regularization Problem

Created by Jason Nicholson

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/image","targetMode":"","relationshipId":"rId1","target":"/media/image1.png"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/image","targetMode":"","relationshipId":"rId2","target":"/media/image2.png"}],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>In data fitting, regularization is a technique to stabilize an ill-posed problem.</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://en.wikipedia.org/wiki/Tikhonov_regularization\"><w:r><w:t>Ridge Regression (aka Tikhonov regularizaton)</w:t></w:r></w:hyperlink><w:r><w:t> adds the 2-norm of the coefficient vector to the least squares problem. The cost function looks like this:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>J=1/2*norm(A*x-b,2)^2+norm(alpha*x,2)^2 (MATLAB equation if image doesn't display)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:customXml w:element=\"image\"><w:customXmlPr><w:attr w:name=\"height\" w:val=\"-1\"/><w:attr w:name=\"width\" w:val=\"-1\"/><w:attr w:name=\"relationshipId\" w:val=\"rId1\"/></w:customXmlPr></w:customXml></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>where</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>x</w:t></w:r><w:r><w:t> is the coefficient vector,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>b</w:t></w:r><w:r><w:t> corresponds to observations,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>A</w:t></w:r><w:r><w:t> comes from evaluating terms of an equation, alpha corresponds to a chosen scalar weight value, and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>J</w:t></w:r><w:r><w:t> is the cost. The minimization of this cost function is ridge regression. When alpha is zero and the least squares problem is ill-conditioned, this problem is unstable meaning that small changes in</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>b</w:t></w:r><w:r><w:t> cause large changes in</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>x</w:t></w:r><w:r><w:t>. Choosing alpha appropriately for a given problem stabilizes the problem causing small changes in</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>b</w:t></w:r><w:r><w:t> causes a small change in</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>x</w:t></w:r><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This Cody problem is about solving the Ridge Regression problem. Implement the solution to the ridge regression problem. This is best done by solving a dual problem. Minimizes a different cost function yields the solution that solves the Ridge Regression problem:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>J = 1/2*norm([A;alpha*eye(n)]*x-[b;zeros(1,n)],2)^2 (MATLAB equation if image doesn't display)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:customXml w:element=\"image\"><w:customXmlPr><w:attr w:name=\"height\" w:val=\"-1\"/><w:attr w:name=\"width\" w:val=\"-1\"/><w:attr w:name=\"relationshipId\" w:val=\"rId2\"/></w:customXmlPr></w:customXml></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Therefore, write a function that minimum of the dual problem for a given A, alpha, and b.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"},{"partUri":"/media/image1.png","contentType":"image/png","content":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAALQAAAAgCAIAAAA0WMUwAAAJ1ElEQVR42u1bh1cT2Rfe/2eVkNBESkSKkSoIiyydhF4UBGkCSokCBkRBXFylKNIEEUQBgXVREF1RBFEpolGkCYpl3eKe3d/3y+gwmRSSQBAx59zjeVOYefPed7/73Xvjd//9N79i9u+/r//+++VKvlFjS7HvVgYTr149vXq1ydPT7cCBZM2ia8CxYG/ePI+Lizx+PNfQUC89fa9m0TXgkGJGRgYZGRpwaMAhzYyNN2RkpKztBf34cfbw4YPh4YHOzva1tae/oplDDubk8DFzJye7xsbKLwKONa45CgoEU1PDGHR1terqap8/X/61zDw/P3tmZhSDjo5GFotx6VL1CoPDkM9f4+BA6PTxcSPGlpab/P29v5aZGxjokrM1MzMJDfVfaXBkZCRJJbSYmIjOzksnT+Yrkvs0NFR8wUW8e7czP/8QhSoO/fZbB3l4+nQRPO/zcuvgu5R9fkJC1OTkSGzsrmWfeU9PW2FhLnmI8HfvXhd5WFJS+Ouvl4gxOC8xMYYODlxG1PH393Fzc/bxcd+7N2Z5wwqfLwUcf/wxtWWLOZZ19+7wRR/S1nZBR0f7zZtn6tv+33+fyMzcHxYWkJy8R/JqU1N1cLAfeQgPq6s7I3lbdXWpiYnh5OSQsm+3teUMD9/eutVy2b/r3LkybC55iF1ubq6TvO3MmSI222h6elQ6c2RlpWlrry8qylMDcyRLBQeHA3D8FB0dvihtWFiwMbf5eaH6wPHPP3ODgz1strGvr4fk1YsXa6jgCAvzr6+nC4uJiUeurk4dHRdVeLut7ZaRkV5ra3WAo1QcHF4tLXRwCIUDrq6O3d0tMgUpOENfX+fly8fLOLM//5zeuNEgOTlWFnOUlS3OHNnZqXZ2WwGO588H1Ro7nj17wGRqHT2aJQ0c1UFBC+AICeHRwPHhw1Ri4u4XLx4u+pbQUJ5s5rBY9o+qqQE4Aijg8G5pqaXe8P79BGYOzpCXyoIP7ew4yzitffviQ0MDvL1/5PG8AF6EBglwWCzKHI8f9+3aFXzsWA7AUVlZrFZwFBcXABwDA93SwkpVcDBXDnPAAUhklJUdl/MWc3P2CjMHYiUVHM3NYuBITIyenh4hGBrBRQo4+vu7sfrqEERySIUIK/KZA+JucnIYXygCxyna1Rs3riAWEOPOzstDQ7eXMiUsIjwEqL16tWl8/CENHEFBvlTmoOarkCk2NlucnOwJg5BSARxyNAcmgykR2bKk4auvXWsmxlgNrIn8sHL58gI44uIiqTMHzUgBx5EjmQzG9/X1ZyUvIdAgSsk3cocUN+yBpeVmOFlUVKisezo6GvLyMjGorS3D9ASCNAqNTyYk7M7NzfDz84iPj8S+QodzOBbyvVa+WVhsMjNjg6gKCwXW1lZULCKsBAYuhBWwSF3dQrGrtLQQf0IaiFrOWzZvNpU8idcND/ciztLO41GgXi8vNzzWxWVbWtqnWvODBzc/b1xWWlpiUlKss7MDn5+cnr6Xy/UICPCRxRw8nieVOZAqUmeOVZUCDm9vNz095tzcE8lLyNkCA33lW1HRERXAYWW1WcQcYbJ06M6dQcRCv337XEtrPbaNyigTE0Mi8mhjMNZXVPwMELNYjIICgWrIGB9/BHIiJ3PgQMqmTcbimsOXAg6eypUuGeAAc/TSmOPt23EnJzuBIJ04BHPgA9vbG7F0SJeIFKOi4uTnWssGIvA5OFi7u7vIylZ4PISVc0qUz7ENyCngN8sVMsrLf8a+SrWZmccU5jArLZUJjpwcPp6DBYLNzIxqaa0jwTE391QgyCBLDvr6urgH49evhfgW8gl37lyrri6WY0LhIEVwHMMrSArMyko1MNAjrzY2VgUG+oiHlTOKFUjoc0DkkpwGwRxgPvEU4UdsCtIo8oyVlTmW6/BhPlFWSU1NIL73yZN+Fkurvv4MQTZ//TVDFaRQSOQhlyslW5EHjoGBG3AaAozLYmfPnoyMDJFqVHCAOcrKpIMD4tnd/YeYmJ179vzfwBMgNkdHG8k7waLbt9srOw3CwDpUjYltIw/BzBs26FOYQ0VwVFWdor3U0FBPchoI/NAcHM4Cc4yN3QNPQBNQn7ZtmzXUfURE4MePs+JS+piuLhO+IS1bKaFmK6Kwshg4Hj68Rcq33NyD2trr4MQyErz7iEzyjRRESoYVpLKFUgUpYEHTMfAqmmMRZmpqlJISR4pclQGN7SEXEc5qamoMdFKYo1qOIFXKzMxkaY7b1A/EfmNTLlyooIHD1HRjV1cr7c8R5pDtk11AKtmIBGmAeFiplQcOhHAdHW17+0+Pc3FxhF8SzCxpSO3i46PkW1VVsWqaA8whKUihzDMz99NOUsHx6pWQKFDev9/DZK5vb28gzlNFibKG1QBFEeOWlvMslnZPTxuVOcTrHFwFmUNBzWFjQw8rUDkMxjqkYLRJQuGRYqC8/AThDxYW7NjYT5OHRkHuKVuQei3CHPPzQmzMrVsdogywGfQltWas7lRWVD4/TqtzIHwi0Pb3d9Hux80ANBFN8bVsthEGfH6Knh6ru/uKSOicWEqqkpQUQ2w/Ah8Sy/3748WLYDRw8OrqylVr2ctKZYeGxAQpoclIvQnXRVJmb2/t7+/97t2LkpJCvIjJZFy/3oodNDIySEraQwQjkK5E+TxAVoVUesseZA5AgJBtbTkQX+rYfqzywYP78GKE1V9+uahI+fzEiSOenjuQlXG5nhMTj0jqEq27AwwD8Hlra72fnyfiMcagEDc3Z7AXKVFV/k0GlA0cy8PjB0BBskJKLZ+HhPhTwaFUy97cXCpzcIaH79CyldHRu66uTvjkiIig6OgIuA3kLZwE6qev79rU1AhWCVePHs3CJVdXx8jIUJDfhw9TcnorCCtUcMhs2T99OnDzZruaiAGvTEiIIja4svKUvr7OoUNpkuVzJGPR0WGrv7UtSmW51MYbFQFKtezhjTKKYL3qKZ/TmENMc3yZlj1c2dPTlUQxnBIJ5+zsE4nyedGijbfVYKKuLJfKHFTNsfSWPRAzMtKrjq5sTc3p8PAgcXDUKdGyV4chYCG56uu7ThxmZu5DtgwyVK1lvzrA8Q237Jf9Z5UIW+Qh1JyJyUZqcUbxlv3qCCvfdstefQZhZWioX1paSCvLCoX337+fmJ0dW/3gQHwkWpekoqLpPsVb9jKKSYNwJ/yrhh8xTRKSk6zBwy2VbtmryTCVHTucsrPT1vbPSBVv2a82W7xlrz5kIDlsaqpZ68hQomW/qkyhlr2aLDs79cqV+s+S/qexsb41CQ6lWvaryhRq2avDBAI+Vq2hoZKw7dvtqTV/jX27/+MtLy+TxWIwmVqkOTs7aJZeA45PrZN3715QbSktU42tmP0PtjfDeE6klHYAAAAASUVORK5CYII="},{"partUri":"/media/image2.png","contentType":"image/png","content":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAIgAAAAmCAIAAACQzkSbAAAKeklEQVR42u1aB1cUyRb2B+nA4AyijII8fSCIoiAmJCeHIEgakg4gKiAYcAF1QOISFBOYFsGAEh5rAAzooOgiIKIirLjJ3X2fU0u/prvpaaBn8J3DOffMqa6pDtVf3Xu/+3XN+/vvj0azL1/ew4x5x/9fm2eEe/zxx7v373tqaiqdnOyrqgrnXjqnvXjRXlJy7M6dH4wHTHf3/djYnfn52RLJ/O+/z5/DgG0tLfUaTfa5c2UuLmvd3Fx//31ontHu/euvgyYmCyoq5oDhsHXrVldVnURDq71narogMzPVqMDglpWVBYz+d+9ewNAYHn4Fdyb24cPLmd9xbGyAuuCbN89EnxGuSV3/8+c3/IMxI2rwx48/oWd09PXQ0HM4B9rW1opdu6LR+OWXNwrF4piYMOMBg1vqPIYJTGCgV2CgNxqxsRELF5paWMhhu3fHCA8CxcV5nH8hn5GryeVmrq5Oos/I2dkRVya3QBQinQMDT+/evYkl//btc/rguLhIMhJzTEz8OruMjCRfX4/792/Rh929e8PMzKShocaowOg85iSjX6n0gekePYI0pkQrNmxYp/elHzmSbiBg8vIOMjrPny93d98slUoAD+dZ/v6eZNmlpyf7+U0A5s8/P+BclSrMSMl/IjBMVrZ9uzdMB8xO0hBuoBJSqYmr6zr+YdnZ6XrHTAuYNXl5h9j9O3YEWlpaTHaWv78XiVrp6Sk6j2mk/srJyTx27NBffw1zAHPjRm1ISICPjztm4uGxRa2OFTuUnZwcmIgpAfPpU5+3t5uVlaWt7b/0AgPHEh2Y9es5PAZma2uzbdtGXmCIx6ToPKZxfJFpQJdJu739DrfHpKbuMjGZX1amEZuVzWcDgwQznmPgMVMIZQkJUU1NdfB9uXyhAGCcDAFMTk4Wo7O39zGySFbW3smB8Rj3GOQY93v3voYy/CYmRjc2XoGh4Dt7towbGFDpRYtkIyO9Ys0B7tnf34VQduLEEURSTmDgMaQhxHp62lWqnWj4+GxDBhaQY4zkMVj4SDAREcGhoQHwm/371ewcQ4DJyIDHAJivHrN2rQOIGWW9vY/mcb5EkAdkNhHnEB4eFBzsj+fYvt0XIfjx41bqr4AATxjxmIAAL4EXDA72Gxvr13EHX6l0wcOHzbzApBnCY5ycHHJzmR6DRABaVV9/Ae3BQS3adXXn6QPwEkgoS0tL9vbeRjxGkCTT2npNIllATjaC6YD5iodKFS4QmPLygtLS4+NhKk0imY8IwBvKAMxaumTX0HDhypUzIHU4RAOH0xDxUBWyPWblyuWIN9ShmZkpYwzySmJipC6UqeHuDLrMB0xamhpTra8/P5mew290miEQmPEcEy4klIFEODraFRXlktvBdfC0N29e5Dnl8OE0F5e1FCpqdQzIj1qtcnVdv3OnUqPJhj/Fx0dNHRhHhsf09XWZmUmyslLJoVZ739RUwhgDYBISosl79vWdCjCbN7sgwXz61M/lTA1RUaH8VltbOXWP8RTuMZgV1mBNTQUxvAUAs3fvLn5gnJ3/ASY5OY5ED5ARnHjgQDIaCOspKfHT8BjGS6+pqUIexfIlh4AffIcVyuAxUTpgkry93YUCA+9evNjc3t5WrEiF23t5ubHNz89zHBgvggcq/8BAPcAgK0ZH76D3PHrUChYOGsmf/Cm6jLKONC5frsaJPT0PSVpllN/ffXeAxzo67pDkn5s7IUyB2oCSUYdbtrig1mE8DCZO0WWwsskCDBOY5uZrwBwLXyxgiovzEDTYRq1QeoGpVOoJZaA0fX1P6D3gEXjgpKQ4fQWmE5tt29hYcaaWGzcucj4zZU1NP+iAWcPIHy9fdshkUrgg2levngWHwrphR4jERJWOlSVTdJkbmJaWeqwRcozRWEfV1SWcox89asnMTOU3/jzMNrpWxpNjtNp7oHM2NsuePv2RLiNWVOTjgbEwu7raiCDIycrYwCAQAWbSHh19PV1JJoudoVFCxsdHbtrk3N5+m3Nt8Whl/wNmZOQnUDowv3EKuHrJEnMkWM7RqEj37dvNb9ev105pegK1MkBOrn/8+GGqs7a2in7roaHn/FoZ5pWbm0nwQ8xB5CEDQkMDxdLKdH7T2dHRxOP0k2llTGBWrVrZ2dmky12VUqkJsoIxP0XMRCsTaJRWhprO3FyGYFhQcBTrjwADtnLw4D4RtTJ90XhSrYwZyvBGYmLCIiND4Df09SiiwdXU6ljUmEFBfrduXRJFK6MbVi4qu40b1wMA3IJBsSitrKenAwsWGRQ8G2tx61ZXTHzfPrWIlf+rVw99fNzx9t3dN6NkJvlGiFbGnfzfvXtBkTxDoII3Bf4N8qPRHJHJTAsLc2aulbFNLl9ob7+Cnc+NppX99tvbVatWZGbuIW0vry1Yi0K0stnZjIG1g6VBZeatWzdYWy+doVbGRUxaEYejonbMolZWWVmI1AVIyCGIGQ77+5/p1cpmB5igIF+FwmJ4+BWFhFQqmaFWxrajRzNQzZ05UzKLWhmef80aB3pRCGJFUYyZamWG2L40NjZAHaJ6pb8mIVoZvO3mzYunThWS3QGc5u3tJpdLBwe1erUyEXdQMDzGzm4FOuk9Zmam4eFKcbQygxoqJHPzhXQ2qVcra2m55uhol5QUCyrl6LiK7ExDuGCstWXLljg42OrVykQFhqmVLV++FJ0MYICEOFqZ4ezJkzbkRtTVwrWy5uY6a2tLqlIrLT2+aJFsdLT39Oli+h6Mzs5mnWARolcrE9djWMAo2B7DBmY6WpnhrKvrR9DTgYFnLIliUq1sZKRXoViMgp/qQaLSCROlQUE+RLQfTzAH0H/2bJlerUzc5M/QymxslqKT3oPkT6mC/FoZiHVv72Oys8l4wKDkTkqKo1AhHx/1amUaTTb84OrVanonelByHTq0n5FgECEHB7uFa2ViAMPUyhwdbdHJAIYhPHJqZSiw4EBgaw4O/05NTTQSMJ8/v1EqfcAOiZgGNrJpk7MQrQyHMpkZnTjA4BlYlRQlHU8wlshDPF8wDbZ9aUIoi44ORaqbyOAl1dXFerUyzJTw5tbWekwQ9a8xgMECX7LEnG4JCVFCtDKsIPjBxJ0x/fCYkpLjDGkV82d8DpiVfWWNjZdlMimlf5eVaRSKRYytE5xaGc4iERsLzspKoVKFGZuVTUkr02rvWVpa4JcctrVdB/VEcYrK4NKl0w8e/MMIsrL2Aq3JEoyR95XhveNeCBJ4bBubZTk5mUK0MoQygl939wPMpago95sCJgJseM+eBFhd3Tnyb0PDBTe3jSEhAaGhgZgJEn55eQEoaViY8suX9yBmul1w2zAGZWx8fOTETzX/IVfz8NhsoOTv6bmV3KKrq40quQoLc5RK3+Bgv+vXa6jBV66cISNXr7bj0cqionaAIs1CHcM2EAHU/DrHP4E3SKyoKG/mV759+yp1Qf5vz9OzlJR46votLfX8g/Pzj1KDyT7hY8cORkaG0jcMXbhQgXVGPurPPjBzRqypqQ7EjHzkHhzUzgHzTdjQ0HNEORQVqGb6+rpOnSqcA+abMJQvIGZy+VdDo7OzaQ6Yb8J+/rlvdPQ1Zej5L4MnGSvuavADAAAAAElFTkSuQmCC"}]}

In data fitting, regularization is a technique to stabilize an ill-posed problem. <a href = "https://en.wikipedia.org/wiki/Tikhonov_regularization">Ridge Regression (aka Tikhonov regularizaton)</a> adds the 2-norm of the coefficient vector to the least squares problem. The cost function looks like this:J=1/2*norm(A*x-b,2)^2+norm(alpha*x,2)^2 (MATLAB equation if image doesn't display)<img src = "https://image.ibb.co/n0G5xp/Equation1.png">where <tt>x</tt> is the coefficient vector, <tt>b</tt> corresponds to observations, <tt>A</tt> comes from evaluating terms of an equation, alpha corresponds to a chosen scalar weight value, and <tt>J</tt> is the cost. The minimization of this cost function is ridge regression. When alpha is zero and the least squares problem is ill-conditioned, this problem is unstable meaning that small changes in <tt>b</tt> cause large changes in <tt>x</tt>. Choosing alpha appropriately for a given problem stabilizes the problem causing small changes in <tt>b</tt> causes a small change in <tt>x</tt>.This Cody problem is about solving the Ridge Regression problem. Implement the solution to the ridge regression problem. This is best done by solving a dual problem. Minimizes a different cost function yields the solution that solves the Ridge Regression problem:J = 1/2*norm([A;alpha*eye(n)]*x-[b;zeros(1,n)],2)^2 (MATLAB equation if image doesn't display)<img src = "https://image.ibb.co/hkAZOU/equation2.png">Therefore, write a function that minimum of the dual problem for a given A, alpha, and b.

Solve

Solution Stats

10 Solutions
4 Solvers

Last Solution submitted on Mar 01, 2019

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

goc3 on 19 Sep 2018

The image links (for the equations) are broken.

Jason Nicholson on 20 Sep 2018

The equation view is okay for me from a private browsing session. I am not sure exactly how to fix the image part. The hosting is supposed to be open always. Therefore, I added text versions of the equations in MATLAB language. I hope this helps.

Problem Recent Solvers4

Problem Tags

ridge regression

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!