PFOpt is a MATLAB toolbox for solving large-scale low-rank optimization problems using polynomial-filtered subspace extraction.
PFOpt can be plugged into any optimization solver in which eigenvalue decompositions are required. We provide two example solvers PFPG (polynomial-filtered proximal gradient), and PFGAUGE (polynomial-filtered GAUGE) in the package.
PFPG is used for solving
Evaluating f(x)
and the gradient of f(x)
only requires part of the
eigenvalues and eigenvectors.
PFGAUGE is modified based on the solver GAUGE (by MP Friedlander). The solver is designed for the maximal eigenvalue problem:
This code uses the GAUGE software package described here:
- Low-rank spectral optimization via gauge duality. M. P. Friedlander and I. Macêdo. SIAM J. on Scientific Computing, 38(3):A1616-A1638, 2016
PFAM is used for solving standard or non-linear SDPs. The polynomial filters are applied to perform projections on to the semi-define space.
The sample codes included are designed for solving:
First download the source code and unzip anywhere you like.
Then launch MATLAB and run
>> cd PFOpt
>> pf_setup
You are ready to go!
Feel free to run the examples under the examples
folder. Please read the
instructions in the corresponding folders, see README.md
.
simple
: simple test routines, seetest_pf.m
.ncm
: nearest correlation matrix problems, seetest_synthetic.m
andtest_real.m
.maxeig
: maximal eigenvalue problems, seetest_phaselift.m
.pfam-ext
: PFAM for non-linear SDPs, seecryoEMADM.m
.
If your own solver contains eigenvalue decompositions, you can simply plug PFOpt into your codes by following just two steps:
- At the beginning of your solver, initialize a workspace for PFOpt.
Parameters can be set according to
work = struct(); work.degree = 8; work.k = -1;
eig_inexact.m
optionally. - Replace all your
eig
oreigs
calls withor[U, d, work] = eig_inexact(A, work);
if A is a function handle. Note that the workspace[U, d, work] = eig_inexact(A, work, n);
work
should be passed through alleig_inexact
calls. Probably you have to makework
as one extra parameter ifeig
oreigs
also appear in one or more subroutines.
Currently PFOpt is able to extract all positive eigenvalues or k largest eigenvalues of a given matrix A. If all negative or k smallest eigenvalues are needed, change A into -A.
- Yongfeng Li, Haoyang Liu, Zaiwen Wen, and Yaxiang Yuan. Low-rank Matrix Optimization Using Polynomial-filtered Subspace Extraction.
- Friedlander M. P. and Macêdo, I. Low-rank Spectral Optimization via Gauge Duality. SIAM Journal on Scientific Computing (2016): A1616-A1638.
- Lanhui Wang, Amit Singeer, and Zaiwen Wen. Orientation Determination of Cryo-EM Images Using Least Unsquared Deviations. SIAM Journal on Imaging Sciences (2013): 2450-2483.
- Zaiwen Wen and Yin Zhang. Accelerating Convergence by Augmented Rayleigh--Ritz Projections For Large-Scale Eigenpair Computation. SIAM Journal on Matrix Analysis and Applications (2017): 273-296.
We hope that the package is useful for your applications. Please feel free to contact the authors if you have any comments or bug reports.
- Haoyang Liu ([email protected])
- Zaiwen Wen ([email protected])
PFOpt
Copyright (C) 2019 Haoyang Liu ([email protected]) Zaiwen Wen ([email protected])
This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.