Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction to Compressed Sensing and Sparse Filtering Read chapter Read first chapter

2014 | OriginalPaper | Chapter

4. Nuclear Norm Optimization and Its Application to Observation Model Specification

Authors : Ning Hao, Lior Horesh, Misha Kilmer

Published in: Compressed Sensing & Sparse Filtering

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Optimization problems involving the minimization of the rank of a matrix subject to certain constraints are pervasive in a broad range of disciples, such as control theory [6, 26, 31, 62], signal processing [25], and machine learning [3, 77, 89]. However, solving such rank minimization problems is usually very difficult as they are NP-hard in general [65, 75]. The nuclear norm of a matrix, as the tightest convex surrogate of the matrix rank, has fueled much of the recent research and has proved to be a powerful tool in many areas. In this chapter, we aim to provide a brief review of some of the state-of-the-art in nuclear norm optimization algorithms as they relate to applications. We then propose a novel application of the nuclear norm to the linear model recovery problem, as well as a viable algorithm for solution of the recovery problem. Preliminary numerical results presented here motivates further investigation of the proposed idea.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Sparse Signal Recovery with Exponential-Family Noise
next chapter Nonnegative Tensor Decomposition
Footnotes
1
This assumption is not mandatory for primal-dual interior point methods.
 
2
Non-intrusive methods relies upon black-box interface, for which output is received per input.
 
Literature
1.
ACM Sigkdd and Netflix (2007) Proceedings of KDD Cup and Workshop
2.
Alizadeh F (1995) Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J Opt 5:13–51MathSciNetCrossRefMATH
3.
4.
Avron H, Kale S, Prasad S, Sindhwani V (2012) Efficient and practical stochastic subgradient descent for nuclear norm regularization. In: Proceedings of the 29th international conference on machine learning
5.
Barrett R, Berry M, Chan TF, Demmel J, Donato J, Dongarra J, Eijkhout V, Pozo R, Romine C, Van der Vorst H (1994) Templates for the solution of linear systems: building blocks for iterative methods. SIAM, 2 edn
6.
Beck C, D’Andrea, R (1998) Computational study and comparisons of lft reducibility methods. In: Proceedings of the American control conference
7.
Belkin M, Niyogi P (2003) Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput 15:1373–1396CrossRefMATH
8.
9.
Boyd S, Parikh N, Chu E, Peleato B, Eckstein J (2011) Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn 3(1):1–122CrossRef
10.
Boykov Y, Kolmogorov V (2001) An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans Pattern Anal Mach Intell 26:359–374
11.
Boykov Y, Veksler O, Zabih R (2001) Fast approximate energy minimization via graph cuts. IEEE Trans Pattern Anal Mach Intell 23:2001CrossRef
12.
Briggs WL, Henson VE, McCormick SF (2000) A multigrid tutorial, 2 edn Society for Industrial and Applied Mathematics, Philadelphia
13.
Bui-Thanh T, Willcox K, Ghattas O (2008) Model reduction for large-scale systems with high-dimensional parametric input space. SIAM J Sci Comput 30(6):3270–3288MathSciNetCrossRefMATH
14.
Cai J, Candès EJ, Shen Z (2010) A singular value thresholding algorithm for matrix completion. SIAM J Opt 20(4):1956–1982CrossRefMATH
15.
Cai JF, Osher S, Shen Z (2009) Convergence of the linearized bregman iteration for \(\ell _1\)-norm minimization. Math Comp 78:2127–2136MathSciNetCrossRefMATH
16.
Candès EJ, Li XD, Ma Y, Wrightes J (2011) Robust principal component analysis. J ACM 58(11):1–37
17.
18.
Combettes PL, Pesquet J-C (2011) Proximal splitting methods in signal processing. In: Bauschke HH, Burachik RS, Combettes PL, Elser V, Luke DR, Wolkowicz H (eds) Fixed-point algorithms for inverse problems in science and engineering, Springer, Berlin, pp 185–212
19.
Conn AR, Gould N, Toint PhL (1993) Improving the decomposition of partially separable functions in the context of large-scale optimization: a first approach
20.
21.
Courtois PJ (1977) Decomposability : queueing and computer system applications, volume ACM monograph series of 012193750X. Academic Press
22.
Dempster AP, Laird NM, Rubin DB (1977) Maximum likelihood from incomplete data via the em algorithm. J R Stat Soc Ser B 39(1):1–38
23.
24.
25.
26.
Fazel M, Hindi H, Boyd S (2001) A rank minimization heuristic with application to minimum order system approximation. In: Proceedings of the American control conference
27.
Fazel M, Hindi H, Boyd S (2003) Log-Det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices. Proc Am Control Conf 3:2156–2162
28.
Feng C (2010) Localization of wireless sensors via nuclear norm for rank minimization. In: Global telecommunications conference IEEE, pp 1–5
29.
Freund RM, S Mizuno (1996) Interior point methods: current status and future directions. OPTIMA — mathematical programming society newsletter
30.
Fuchs J-J (2004) On sparse representations in arbitrary redundant bases. IEEE Trans Inf Theory 50:1341–1344
31.
Ghaoui LE, Gahinet P (1993) Rank minimization under lmi constraints: a framework for output feedback problems. In: Proceedings of the European control conference
32.
Globerson A, Chechik G, Pereira F, Tishby N (2007) Euclidean embedding of co-occurrence data. J Mach Learn Res 8:2265–2295MathSciNetMATH
33.
Golub GH, Van Loan CF (1996) Matrix computations, 3 edn. Johns Hopkins University Press
34.
Gonzalez-Vega L, Rúa IF (2009) Solving the implicitization, inversion and reparametrization problems for rational curves through subresultants. Comput Aided Geom Des 26(9):941–961CrossRefMATH
35.
Grama A, Karypis G, Gupta A, Kumar V (2003) Introduction to parallel computing: design and analysis of algorithms. Addison-Wesley
36.
Griewank A, Toint PhL (1981) On the unconstrained optimization of partially separable objective functions. In: Powell MJD (ed) Nonlinear optimization. Academic press, London, pp 301–312
37.
Griewank A, Walther A (2008) Evaluating derivatives: principles and techniques of algorithmic differentiation. Soc Indus Appl Math
38.
Grossmann C (2009) System identification via nuclear norm regularization for simulated moving bed processes from incomplete data sets. In: Proceedings of the 48th IEEE conference on decision and control, 2009 held jointly with the 28th Chinese control conference. CDC/CCC 2009
39.
Gugercin S, Willcox K (2008) Krylov projection framework for fourier model reduction
40.
Hansson A, Liu Z, Vandenberghe L (2012) Subspace system identification via weighted nuclear norm optimization. CoRR, abs/1207.0023
41.
Hazan E (2008) Sparse approximation solutions to semidefinite programs. In: LATIN, pp 306–316
42.
Hendrickson B, Leland R (1995) A multilevel algorithm for partitioning graphs. In: Proceedings of the 1995 ACM/IEEE conference on supercomputing, supercomputing 1995, ACM, New York
43.
Horesh L, Haber E (2009) Sensitivity computation of the \(\ell _1\) minimization problem and its application to dictionary design of ill-posed problems. Inverse Prob 25(9):095009MathSciNetCrossRef
44.
Jaggi M, Sulovsky M (2010) A simple algorithm for nuclear norm regularized problems. In: Proceedings of the 27th international conference on machine learning
45.
Ji S, Ye J (2009) An accelerated gradient method for trace norm minimization. In: Proceedings of the 26th annual international conference on machine learning, ICML 2009, ACM, New York, pp 457–464
46.
Kaipio JP, Kolehmainen V, Vauhkonen M, Somersalo E (1999) Inverse problems with structural prior information. Inverse Prob 15(3):713–729
47.
Kanevsky D, Carmi A, Horesh L, Gurfil P, Ramabhadran B, Sainath TN (2010) Kalman filtering for compressed sensing. In: 13th conference on information fusion (FUSION), pp 1–8
48.
Karypis G, Kumar V (1998) A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J Sci Comput 20(1):359–392MathSciNetCrossRef
49.
Lee K, Bresler Y (2010) Admira: atomic decomposition for minimum rank approximation. IEEE Trans Inf Theory 56(9):4402–4416MathSciNetCrossRef
50.
Li HF (2004) Minimum entropy clustering and applications to gene expression analysis. In: Proceedings of IEEE computational systems bioinformatics conference, pp 142–151
51.
Liiv I (2010) Seriation and matrix reordering methods: an historical overview. Stat Anal Data Min 3(2):70–91MathSciNet
52.
Lin ZC, Chen MM, Ma Y (2009) The augmented Lagrange multiplier method for exact recovery of a corrupted low-rank matrices. Technical report
53.
Lin ZC, Ganesh A, Wright J, Wu LQ, Chen MM, Ma Y (2009) Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix. In: Conference version published in international workshop on computational advances in multi-sensor adaptive processing
54.
Liu J, Sycara KP (1995) Exploiting problem structure for distributed constraint optimization. In: Proceedings of the first international conference on multi-agent systems. MIT Press, pp 246–253
55.
Liu Y-J, Sun D, Toh K-C (2012) An implementable proximal point algorithmic framework for nuclear norm minimization. Mathe Program 133:399–436
56.
Liu Z, Vandenberghe L (2009) Interior-point method for nuclear norm approximation with application to system identification. SIAM J Matrix Anal Appl 31:1235–1256MathSciNetCrossRef
57.
Ma SQ, Goldfarb D, Chen LF (2011) Fixed point and bregman iterative methods for matrix rank minimization. Math Program 128:321–353MathSciNetCrossRefMATH
58.
Majumdar A, Ward RK (2012) Nuclear norm-regularized sense reconstruction. Magn Reson Imaging 30(2):213–221CrossRef
59.
Mallat SG (1989) A theory for multiresolution signal decomposition: the wavelet representation. IEEE Trans Pattern Anal Mach Intell 11:674–693CrossRefMATH
60.
Mardani M, Mateos G, Giannakis GB (2012) In-network sparsity-regularized rank minimization: algorithms and applications. CoRR, abs/1203.1570
61.
Mazumder R, Hastie T, Tibshirani R (2010) Spectral regularization algorithms for learning large incomplete matrices. J Mach Learn Res 99:2287–2322MathSciNet
62.
Mesbahi M, Papavassilopoulos GP (1997) On the rank minimization problem over a positive semi-definite linear matrix inequality. IEEE Trans Autom Control 42(2):239–243MathSciNetCrossRefMATH
63.
Mohan K, Fazel M (2010) Reweighted nuclear norm minimization with application to system identification. In: American control conference (ACC), pp 2953–2959
64.
Moore BC (1981) Principal component analysis in linear systems: controllability, observability, and model reduction. IEEE Trans Autom Cont AC-26:17–32
65.
66.
Neal R, Hinton GE (1998) A view of the EM algorithm that justifies incremental, sparse, and other variants. In: Learning in graphical models. Kluwer Academic Publishers, pp 355–368
67.
Nemirovsky AS, Yudin DB (1983) Problem complexity and method efficiency in optimization. Wiley-Interscience series in discrete mathematics, Wiley
68.
Nesterov Y (1983) A method of solving a convex programming problem with convergence rate \({\cal O}\left(\frac{1}{{\sqrt{k}}}\right)\). Sov Math Dokl 27:372–376
69.
Nesterov Y, Nemirovskii A (1994) Interior-point polynomial algorithms in convex programming. In: Studies in applied and numerical mathematics. Soc for Industrial and Applied Math
70.
Olsson C, Oskarsson M (2009) A convex approach to low rank matrix approximation with missing data. In: Proceedings of the 16th Scandinavian conference on image, analysis, SCIA ’09, pp 301–309
71.
Peng YG, Ganesh A, Wright J, Xu WL, Ma Y (2010) RASL: robust alignment by sparse and low-rank decomposition for linearly correlated images. In: IEEE conference on computer vision and pattern recognition (CVPR), pp 763–770
72.
Phillips DL (1962) A technique for the numerical solution of certain integral equations of the first kind. J ACM 9(1):84–97CrossRefMATH
73.
Pichel JC, Rivera FF, Fernández M, Rodríguez A (2012) Optimization of sparse matrix-vector multiplication using reordering techniques on GPUs. Microprocess Microsyst 36(2):65–77CrossRef
74.
Pothen A, Simon HD, Liou K-P (1990) Partitioning sparse matrices with eigenvectors of graphs. SIAM J Matrix Anal Appl 11(3):430–452MathSciNetCrossRefMATH
75.
Recht B, Fazel M, Parillo P (2010) Guaranteed minimum rank solutions to linear matrix equations via nuclear norm minimization. SIAM Rev 52(3):471–501MathSciNetCrossRefMATH
76.
Recht B, Ré C (2011) Parallel stochastic gradient algorithms for large-scale matrix completion. In: Optimization (Online)
77.
Rennie JDM, Srebro N (2005) Fast maximum margin matrix factorization for collaborative prediction. In: Proceedings of the international conference of Machine Learning
78.
Rudin LI, Osher S, Fatemi E (1992) Nonlinear total variation based noise removal algorithms. Phys D 60:259–268CrossRefMATH
79.
Shapiro A, Homem de Mello T (2000) On rate of convergence of Monte Carlo approximations of stochastic programs. SIAM J Opt 11:70–86MathSciNetCrossRefMATH
80.
Shapiro A, Dentcheva D, Ruszczyński A (eds) (2009) Lecture notes on stochastic programming: modeling and theory. SIAM, Philadelphia
81.
82.
Strout MM, Hovland PD (2004) Metrics and models for reordering transformations. In: Proceedings of the 2004 workshop on Memory system performance, MSP ’04, ACM, New York, pp 23–34
83.
Tikhonov AN (1963) Solution of incorrectly formulated problems and the regularization method. Sov Math Dokl 4:1035–1038
84.
Toh K-C, Yun S (2010) An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. Pacific J Optim 6:615–640
85.
Tor AJ (1997) On tikhonov regularization, bias and variance in nonlinear system identification. Automatica 33:441–446CrossRefMATH
86.
Tropp JA (2004) Greed is good: algorithmic results for sparse approximation. IEEE Trans Inform Theory 50:2231–2242MathSciNetCrossRef
87.
Trottenberg U, Oosterlee CW, Schüller A (2000) Multigrid. Academic Press, London
88.
Tseng P (2008) On accelerated proximal gradient methods for convex-concave optimization. SIAM J Optim (submitted)
89.
Weinberger KQ, Saul LK (2006) Unsupervised learning of image manifolds by semidefinite programming. Int J Comput Vis 70(1):77–90CrossRef
90.
Willcox K, Peraire J (2002) Balanced model reduction via the proper orthogonal decomposition. AIAA J 40:2323–2330
91.
Yang JF, Yuan XM (2013) Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization. Math Comp 82(281):301–329MathSciNetCrossRefMATH
92.
Yin W, Osher S, Goldfarb D, Darbon J (2008) Bregman iterative algorithms for l1-minimization with applications to compressed sensing. SIAM J Imaging Sci 1:143–168
93.
94.
Zhang J (1999) A multilevel dual reordering strategy for robust incomplete lu factorization of indefinite matrices
Metadata
Title
Nuclear Norm Optimization and Its Application to Observation Model Specification
Authors
Ning Hao
Lior Horesh
Misha Kilmer
Copyright Year
2014
Publisher
Springer Berlin Heidelberg
Book
Compressed Sensing & Sparse Filtering

Print ISBN: 978-3-642-38397-7

Electronic ISBN: 978-3-642-38398-4

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-642-38398-4_4