NNLS version 0 -- a MATLAB software for nuclear norm regularized linear least squares problems based on an accelerated proximal gradient method

Kim-Chuan Toh and Sangwoon Yun

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.



  • 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
    ------------------------------------------------------------------------------