{ "cells": [ { "cell_type": "markdown", "id": "5257bb27", "metadata": {}, "source": [ "# Robust PCA\n", "\n", "Solve the robust PCA problem taken from Xinyang Yi, et al. [\"Fast algorithms for robust PCA via gradient\n", "descent.\"](https://papers.nips.cc/paper/2016/hash/b5f1e8fb36cd7fbeb7988e8639ac79e9-Abstract.html) Advances in neural information processing systems. 2016.\n" ] }, { "cell_type": "markdown", "id": "a2ca043d", "metadata": {}, "source": [ "## Problem Description" ] }, { "cell_type": "markdown", "id": "5ae4094e", "metadata": {}, "source": [ "$$\\min_{M,S}||M||_{\\text{nuc}}+\\lambda||S||_1,$$\n", "$$\\text{s.t. }Y=M+S,$$\n", "where $M,S\\in R^{d_1,d_2}$ are matrix form optimization variables, $Y\\in R^{d_1,d_2}$ is a given matrix, and $||\\cdot||_{\\text{nuc}}$ denotes the nuclear norm." ] }, { "cell_type": "markdown", "id": "08dfdd50", "metadata": {}, "source": [ "## Modules Importing\n", "Import all necessary modules and add PyGRANSO src folder to system path." ] }, { "cell_type": "code", "execution_count": 1, "id": "90ed32f9", "metadata": {}, "outputs": [], "source": [ "import time\n", "import torch\n", "from pygranso.pygranso import pygranso\n", "from pygranso.pygransoStruct import pygransoStruct" ] }, { "cell_type": "markdown", "id": "17a1b7fe", "metadata": {}, "source": [ "## Data Initialization \n", "Specify torch device, and generate data.\n", "\n", "Use GPU for this problem. If no cuda device available, please set *device = torch.device('cpu')*" ] }, { "cell_type": "code", "execution_count": 2, "id": "8b4842e1", "metadata": {}, "outputs": [], "source": [ "device = torch.device('cuda')\n", "d1 = 3\n", "d2 = 4\n", "torch.manual_seed(1)\n", "eta = .05\n", "# All the user-provided data (vector/matrix/tensor) must be in torch tensor format. \n", "# As PyTorch tensor is single precision by default, one must explicitly set `dtype=torch.double`.\n", "# Also, please make sure the device of provided torch tensor is the same as opts.torch_device.\n", "Y = torch.randn(d1,d2).to(device=device, dtype=torch.double)" ] }, { "cell_type": "markdown", "id": "ec80716b", "metadata": {}, "source": [ "## Function Set-Up\n", "\n", "Encode the optimization variables, and objective and constraint functions.\n", "\n", "Note: please strictly follow the format of comb_fn, which will be used in the PyGRANSO main algortihm." ] }, { "cell_type": "code", "execution_count": 3, "id": "fb360e75", "metadata": {}, "outputs": [], "source": [ "# variables and corresponding dimensions.\n", "var_in = {\"M\": [d1,d2],\"S\": [d1,d2]}\n", "\n", "\n", "def user_fn(X_struct,Y):\n", " M = X_struct.M\n", " S = X_struct.S\n", " \n", " # objective function\n", " f = torch.norm(M, p = 'nuc') + eta * torch.norm(S, p = 1)\n", "\n", " # inequality constraint, matrix form\n", " ci = None\n", " \n", " # equality constraint \n", " ce = pygransoStruct()\n", " ce.c1 = M + S - Y\n", "\n", " return [f,ci,ce]\n", "\n", "comb_fn = lambda X_struct : user_fn(X_struct,Y)" ] }, { "cell_type": "markdown", "id": "f0f55ace", "metadata": {}, "source": [ "## User Options\n", "Specify user-defined options for PyGRANSO" ] }, { "cell_type": "code", "execution_count": 4, "id": "f3a65b57", "metadata": {}, "outputs": [], "source": [ "opts = pygransoStruct()\n", "opts.torch_device = device\n", "opts.print_frequency = 10\n", "opts.x0 = .2 * torch.ones((2*d1*d2,1)).to(device=device, dtype=torch.double)\n", "opts.opt_tol = 1e-6" ] }, { "cell_type": "markdown", "id": "8bca18c7", "metadata": {}, "source": [ "## Main Algorithm" ] }, { "cell_type": "code", "execution_count": 5, "id": "632976b3", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "\n", "\u001b[33m╔═════ QP SOLVER NOTICE ════════════════════════════════════════════════════════════════════════╗\n", "\u001b[0m\u001b[33m║ PyGRANSO requires a quadratic program (QP) solver that has a quadprog-compatible interface, ║\n", "\u001b[0m\u001b[33m║ the default is osqp. Users may provide their own wrapper for the QP solver. ║\n", "\u001b[0m\u001b[33m║ To disable this notice, set opts.quadprog_info_msg = False ║\n", "\u001b[0m\u001b[33m╚═══════════════════════════════════════════════════════════════════════════════════════════════╝\n", "\u001b[0m═════════════════════════════════════════════════════════════════════════════════════════════════════════════════╗\n", "PyGRANSO: A PyTorch-enabled port of GRANSO with auto-differentiation ║ \n", "Version 1.2.0 ║ \n", "Licensed under the AGPLv3, Copyright (C) 2021-2022 Tim Mitchell and Buyun Liang ║ \n", "═════════════════════════════════════════════════════════════════════════════════════════════════════════════════╣\n", "Problem specifications: ║ \n", " # of variables : 24 ║ \n", " # of inequality constraints : 0 ║ \n", " # of equality constraints : 12 ║ \n", "═════╦═══════════════════════════╦════════════════╦═════════════════╦═══════════════════════╦════════════════════╣\n", " ║ <--- Penalty Function --> ║ ║ Total Violation ║ <--- Line Search ---> ║ <- Stationarity -> ║ \n", "Iter ║ Mu │ Value ║ Objective ║ Ineq │ Eq ║ SD │ Evals │ t ║ Grads │ Value ║ \n", "═════╬═══════════════════════════╬════════════════╬═════════════════╬═══════════════════════╬════════════════════╣\n", " 0 ║ 1.000000 │ 9.26721133015 ║ 0.81282032303 ║ - │ 1.922768 ║ - │ 1 │ 0.000000 ║ 1 │ 2.502220 ║ \n", " 10 ║ 0.071790 │ 0.03336327939 ║ 0.46473565836 ║ - │ 1.67e-15 ║ S │ 1 │ 1.000000 ║ 1 │ 11.88437 ║ \n", " 20 ║ 0.011973 │ 0.00404030852 ║ 0.33746530772 ║ - │ 1.33e-15 ║ S │ 1 │ 1.000000 ║ 1 │ 0.002421 ║ \n", " 30 ║ 0.004175 │ 0.00139375036 ║ 0.33386777336 ║ - │ 7.99e-15 ║ S │ 2 │ 0.500000 ║ 1 │ 112.4975 ║ \n", " 40 ║ 0.001997 │ 6.6642624e-04 ║ 0.33376748890 ║ - │ 2.20e-14 ║ S │ 4 │ 0.125000 ║ 4 │ 3.07e-05 ║ \n", "═════╩═══════════════════════════╩════════════════╩═════════════════╩═══════════════════════╩════════════════════╣\n", "F = final iterate, B = Best (to tolerance), MF = Most Feasible ║ \n", "Optimization results: ║ \n", "═════╦═══════════════════════════╦════════════════╦═════════════════╦═══════════════════════╦════════════════════╣\n", " F ║ │ ║ 0.33375284367 ║ - │ 6.48e-14 ║ │ │ ║ │ ║ \n", " B ║ │ ║ 0.33375284367 ║ - │ 6.48e-14 ║ │ │ ║ │ ║ \n", " MF ║ │ ║ 1.30399559824 ║ - │ 1.11e-16 ║ │ │ ║ │ ║ \n", "═════╩═══════════════════════════╩════════════════╩═════════════════╩═══════════════════════╩════════════════════╣\n", "Iterations: 46 ║ \n", "Function evaluations: 104 ║ \n", "PyGRANSO termination code: 0 --- converged to stationarity and feasibility tolerances. ║ \n", "═════════════════════════════════════════════════════════════════════════════════════════════════════════════════╝\n", "Total Wall Time: 2.862501621246338s\n" ] } ], "source": [ "start = time.time()\n", "soln = pygranso(var_spec = var_in,combined_fn = comb_fn,user_opts = opts)\n", "end = time.time()\n", "print(\"Total Wall Time: {}s\".format(end - start))" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.7" } }, "nbformat": 4, "nbformat_minor": 5 }