NNLS version 0 -- a MATLAB software for
nuclear norm regularized linear least squares problems
based on an accelerated proximal gradient method
The software was first released on 14 Oct 2009. It was
last updated in 10 Nov 2009
with some minor bugs corrected.
The software is designed to solve nuclear norm regularized linear least
squares problems of the form:
min_X {f(X) + mu*sum(svd(X))}
min_X {f(X) + mu*trace(X) : X psd}
where mu > 0 is a regularization paramter, and f(X) = 0.5*norm(A(X)-b)^2.
Important note:
this is a research software. It is not intended nor designed to be a general
purpose software at the moment.
The solver is expected to work well only for favorable problems
such as nuclear norm regularized
random matrix completion problems.
Being a gradient method, it is quite sensitive to the various
parameters used in the algorithm. The selection of the parameters
typically depend on the class of problems being solved.
For more details, see:
Kim-Chuan Toh and Sangwoon Yun
An accelerated proximal gradient algorithm for nuclear norm regularized
least squares problems, Pacific J. Optimization, 6
(2010), pp. 615--640.
- Copyright:
This version of NNLS is distributed under the GNU General Public License 2.0.
For commercial applications that may be incompatible with this license,
please contact the authors to discuss alternatives.
- User guide: in preparation.
- NNLS-0.zip
Please read.
Welcome to NNLS-0!
The software requires a few Mex files for execution.
You can generate (only need to be done once)
these Mex files
as follows:
- Firstly, unpack the software:
unzip NNLS-0.zip
- Run Matlab in the directory NNLS-0
- In the Matlab command window, type:
>> Installmex
- After that, to see whether you have installed NNLS-0 correctly,
type:
>> startup
>> runRandomMatComp
- By now, NNLS is ready for you to use.
Some segmentation errors have been reported when running NNLS-0 on Windows 64-bit PCs.
We have not observed such errors when running on MATLAB version
7.13.0.564 (R2011b). For example, when running the m-file
runRandomMatComp, we get the following successful run:
>> runRandomMatComp
Create matrix 1 with rank = 10,
Problem: n = 5000, p = 600614, r = 10, p/dr = 6.01e+000, p/n^2 = 2.40e+000%
mu = 1.37e-002, noise ratio, sigma = 0.00e+000, 0.00e+000
nr = 5000, nc = 5000, m = 600614
Lipschitz const = 1.00e+000
mu_target = 1.37e-002
matrix storage format = factors
------------------------------------------------------------------------------------------
it mu tau svp relDist relRes relObjdiff obj time
------------------------------------------------------------------------------------------+
1 1.37e+002 1.00e+000 | 2| 0.00e+000 1.00e+000 1.00e+000| 3.0200e+006| 3.28e-001|+ [0.0e+000]
2 9.62e+001 1.00e+000 | 1 1| 9.86e-001 9.99e-001 5.56e-004| 3.0183e+006| 5.31e-001|+ [0.0e+000]
3 6.74e+001 1.00e+000 | 2 2| 6.83e-001 9.96e-001 3.71e-003| 3.0072e+006| 6.55e-001|+ [0.0e+000]
4 4.72e+001 1.00e+000 | 3 3| 4.70e-001 9.89e-001 1.07e-002| 2.9755e+006| 7.49e-001|+ [0.0e+000]
45 1.37e-002 4.40e-002 | 10 11| 2.61e-004 1.54e-004 1.97e-005| 6.8908e+002| 6.8911e+002| 1.56e+001| [1.1e+004]
46 1.37e-002 4.40e-002 | 10 11| 2.05e-004 1.48e-004 2.89e-005| 6.8906e+002| 6.8908e+002| 1.58e+001| [1.0e+004]
47 1.37e-002 4.40e-002 | 10 11| 1.45e-004 1.37e-004 4.40e-005| 6.8903e+002| 6.8904e+002| 1.60e+001| [8.4e+003]
48 1.37e-002 4.40e-002 | 10 11| 9.63e-005 1.35e-004 3.17e-005| 6.8901e+002|
[a] relDist < 1.00e-004
Finished the main algorithm!
Objective function = 6.89011e+002
Number of iterations = 48
Number of singular values = 10
max singular value = 5.23e+003
min singular value = 4.79e+003
CPU time = 1.61e+001
norm(X-Xold,'fro')/norm(X,'fro') = 9.63e-005
Problem: nr = 5000, nc = 5000, p = 600614, r = 10, p/dr = 6.01e+000, p/n^2 = 2.40e+000%
mu = 1.37e-002, noise ratio, sigma = 0.00e+000, 0.00e+000
-----------------------------------------------------------------------------
problem type : NNLS
randstate : 1
iterations : 48
# singular : 10
obj value : 6.89011e+002
cpu time : 1.62e+001
mean square error : 1.85e-004
------------------------------------------------------------------------------