alpyurtsever / sketchycgal Goto Github PK
View Code? Open in Web Editor NEWMATLAB implementation of the Scalable Semidefinite Programming
License: GNU General Public License v3.0
MATLAB implementation of the Scalable Semidefinite Programming
License: GNU General Public License v3.0
--------------------------------------------------------------------------- SketchyCGAL Scalable Semidefinite Programming A.Yurtsever - J.A. Tropp - O. Fercoq - M. Udell - V. Cevher --------------------------------------------------------------------------- This toolbox includes the source code for the numerical experiments in our paper. Please follow <https://github.com/alpyurtsever/SketchyCGAL> for the updates. Please contact "[email protected]" or "[email protected]" for your questions and feedbacks. --------------------------------------------------------------------------- --------------------------------------------------------------------------- INDEX "./@memLog/memLog.m" - implements a class handle to externally monitor memory usage of MATLAB. Works only on UNIX systems. "./FilesMaxcut/data/G/" "./FilesMaxcut/data/DIMACS10/" - Empty folders. You should download the datasets from GSET and DIMACS10 benchmark to run MaxCut experiments. "./FilesMaxcut/data/sedumi_modified/" - Empty folders. Make a copy of "sedumi.m" in this folder, rename it as sedumi_modified.m, and comment out the lines 638-642. "./FilesMaxcut/data/WALDSPURGER/C1.mat" "./FilesMaxcut/data/WALDSPURGER/C2.mat" "./FilesMaxcut/data/WALDSPURGER/C3.mat" "./FilesMaxcut/data/WALDSPURGER/C4.mat" "./FilesMaxcut/data/WALDSPURGER/C5.mat" "./FilesMaxcut/data/WALDSPURGER/C6.mat" "./FilesMaxcut/data/WALDSPURGER/C7.mat" "./FilesMaxcut/data/WALDSPURGER/C8.mat" "./FilesMaxcut/data/WALDSPURGER/C9.mat" "./FilesMaxcut/data/WALDSPURGER/C10.mat" - Datasets constructed by the script provided by Irene Waldspurger. These datasets are the realizations of problems with spurious solutions for Burer-Monteiro factorization methods. See [WW2019] for details. "./FilesPhaseRetrieval/CreateData.m" - This script generates data for the abstract phase retrieval experiments. "./FilesPtychography/data/Cell160.tiff" "./FilesPtychography/data/Cell320.tiff" "./FilesPtychography/data/Cell640.tiff" "./FilesPtychography/data/PIXNIO-39417-2650x1770" "./FilesPtychography/data/PIXNIO-39417-2650x1770.txt" - Cell images used in the Ptychography experiments. These images are cropped from the image downloaded from "https://pixnio.com/science/ microscopy-images/hemorrhagic-fever-marburg-virus/cytoarchitectural- histopathologic-changes-detected-in-a-kidney-sample-taken-from-a-marburg- patient" (Last accessed on December 05, 2019). We thank Dr. J. Lyle Conrad, USCDCP, for sharing this image with CC0 license. "./FilesPtychography/data/CreateData" - This script generates data for the synthetic transition matrices for the ptychography experiments. These matrices are different from the ones we used in the actual experiments. Therefore the results can be different. "./FilesPtychography/FilesQAP/munkres/munkres.m" "./FilesPtychography/FilesQAP/munkres/license.txt" - Munkres (Hungarian) algorithm used in rounding of QAP SDP solution. We use the implementation by Yi Ciao. Reference: "Munkres' Assignment Algorithm, Modified for Rectangular Matrices" http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html "./FilesPtychography/FilesQAP/PartialTrace/TrX.m" "./FilesPtychography/FilesQAP/PartialTrace/license.txt" - This function computes the partial trace from a state vector of density matrix. We use the implementation by Tony Cubitt. "./FilesPtychography/FilesQAP/qapread.m" "./FilesPtychography/FilesQAP/tspread.m" - Functions to load data from QAPLIB and TSPLIB. "./FilesPtychography/FilesQAP/qapdata/" "./FilesPtychography/FilesQAP/tspdata/" - Empty folders. You need to download datasets from QAPLIB and TSPLIB to These folders to run QAP experiments. "./FilesPtychography/solver/CGAL.m" "./FilesPtychography/solver/@NystromSketch/NystromSketch.m" "./FilesPtychography/solver/@NystromSketch/COPYRIGHT.txt" - Implementation of CGAL, ThinCGAL, and SketchyCGAL. NystromSketch class is a minimal version of our SKETCH toolbox. You can find more details on SKETCH toolbox at <https://github.com/alpyurtsever/SKETCH>. "./FilesPtychography/utils/mexPrimitive2.c" "./FilesPtychography/utils/mexPrimitive3.c" "./FilesPtychography/utils/mexSparseMult.c" - Generating sparse matrices is a time consuming process in MATLAB. To avoid regenerating sparse matrices in the QAP experiment, we implement these three MEX files, which directly computes the sparse matrix - dense vector products from indexes. Primitive2 and Primitive3 are used to implement the black-box oracles. mexSparseMult is used in nonnegativity constraints. "./plotter/Figure11_MaxCut.m" "./plotter/Figure71_MaxCut.m" "./plotter/Figure72_PhaseRetrieval.m" "./plotter/Figure74_QAP.m" "./plotter/FigureSM73_MaxCut.m" - These scripts generate the Figures in the paper. Before running these scripts, you should run the associated experiments. These scripts only plot the figures from the saved results of these experiments. "./Test_MaxCut_CGAL.m" "./Test_MaxCut_Mosek.m" "./Test_MaxCut_SDPT3.m" "./Test_MaxCut_SDPNAL.m" "./Test_MaxCut_Sedumi.m" - These files implements the MaxCut experiments that we used to produce Figure 7.1. "./Test_MaxCut_CGAL_Figure71.m" "./Test_MaxCut_SDPT3_GroundTruth.m" - This file implements the MaxCut experiment to produce Figure 7.1. "./Test_MaxCut_Waldspurger.m" - This file implements the numerical demonstration of spurious solutions for Burer-Monteiro factorization methods, present in the supplements. See Figure SM6.2. "./Test_PhaseRetrieval.m" - This file implements the abstract Phase Retrieval experiments to produce Figure 7.3. You shuold run this file for all problem dimensions n, with all methods, and from MC = 1 to 20, for 20 Monte-Carlo trials. "./Test_Ptychography.m" - This file implements the Ptchograph imaging experiments. You can run it for different problem sizes n = {160,320,640}. "./Test_QAP.m" - This file implements the QAP experiments. "./Test_MaxCut_CGAL_PD.m" "./Test_MaxCut_Mosek_PD.m" "./Test_MaxCut_SDPT3_PD.m" "./Test_MaxCut_SDPNAL_PD.m" "./Test_MaxCut_Sedumi_PD.m" "./Test_MaxCut_CGAL_FigureSM71_PD.m" - These files implement the MaxCut experiments for demonstrating the primal-dual convergence. "./COPYRIGHT.txt" "./LICENSE.txt" - License information. "./README.txt" - This README file. --------------------------------------------------------------------------- --------------------------------------------------------------------------- NOTES This code is tested on MATLAB R2018a. It might not work on other versions. "Test_MaxCut_SDPNAL" requires SDPNAL+ (Tested with version 1.0). Visit "https://blog.nus.edu.sg/mattohkc/softwares/sdpnalplus/" to download SDPNAL+. "Test_MaxCut_SDPT3" requires SDPT3. (Tested with version 4.0). Visit "https://blog.nus.edu.sg/mattohkc/softwares/sdpt3/" to download SDPT3. "Test_MaxCut_Sedumi" requires Sedumi. (Tested with version 1.3) Visit "http://sedumi.ie.lehigh.edu/" to download Sedumi. "Test_MaxCut_manopt" and "Test_MaxCut_Waldspurger" require manopt. (Tested with version 5) Visit "https://www.manopt.org/" to download manopt. "Test_MaxCut_Mosek" requires MoSeK. MoSeK requires a license, personal academic license for MoSeK is free. (Tested with version 8) Visit "http://www.mosek.com/" to download MOSEK. --------------------------------------------------------------------------- --------------------------------------------------------------------------- CITATION If you find this toolbox useful in your research, please cite our paper. Yurtsever, A., Tropp, J. A., Fercoq, O., Udell, M., Cevher, V., Scalable Semidefinite Programming, SIAM Journal on Mathematics of Data Science, 3(1):171-200, 2021 --------------------------------------------------------------------------- --------------------------------------------------------------------------- Last edit: Alp Yurtsever - November 25, 2020
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.