×

A general theory of singular values with applications to signal denoising. (English) Zbl 1408.94861

Summary: We study the Pareto frontier for two competing norms \(\|\cdot\|_X\) norms and \(\|\cdot\|_Y\) on a vector space. For a given vector \(c\), the Pareto frontier describes the possible values of \((\| a\|_X,\| b\|_Y)\) for a decomposition \(c=a+b\). The singular value decomposition of a matrix is closely related to the Pareto frontier for the spectral and nuclear norm. We will develop a general theory that extends the notion of singular values of a matrix to arbitrary finite dimensional Euclidean vector spaces equipped with dual norms. This also generalizes the diagonal singular value decompositions (DSVDs) for tensors introduced by the author in previous work. We can apply the results to denoising, where \(c\) is a noisy signal, \(a\) is a sparse signal, and \(b\) is noise. Applications include 1D total variation denoising, 2D total variation Rudin-Osher-Fatemi image denoising, LASSO, basis pursuit denoising, and tensor decompositions.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
15A69 Multilinear algebra, tensor calculus
90C25 Convex programming

Software:

ParNes; condat_tv; PDCO
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. S. Asif and J. Romberg, On the LASSO and Dantzig selector equivalence, in the 44th Conference on Information Sciences and Systems (CISS) (Princeton, NJ, 2010), IEEE, Washington, DC, 2010.
[2] S. Banach, Über homogene Polynome in (\(L^2\)), Studia Math., 7 (1938), pp. 36–44. · Zbl 0018.21902
[3] R. Barlow, D. Bartholomew, J. Bremner, and H. Brunk, Statistical Inference under Order Restrictions, Wiley, New York, 1972. · Zbl 0246.62038
[4] A. Barvinok, A Course in Convexity, Grad. Stud. Math. 54, AMS, Providence, RI, 2002. · Zbl 1014.52001
[5] A. Belle, S. Asgari, M. Spadafore, V. A. Convertino, K. R. Ward, H. Derksen, and K. Najarian, A signal processing approach for detection of hemodynamic instability before decompensation, PLoS ONE, 11 (2016), e0148544.
[6] E. van den Berg and M. P. Friedlander, Probing the Pareto frontier for basic pursuit solutions, SIAM J. Sci. Comput., 31 (2008), pp. 890–912, . · Zbl 1193.49033
[7] M. Bläser, On the complexity of the multiplication of matrices of small formats, J. Complexity, 19 (2003), pp. 43–60. · Zbl 1026.68062
[8] J. D. Carroll and J. Chang, Analysis of individual differences in multidimensional scaling via an \(N\)-way generalization of an Eckart-Young decomposition, Psychometrika, 35 (1970), pp. 283–319. · Zbl 0202.19101
[9] S. S. Chen, D. L. Donoho, and M. A. Saunders, Atomic decomposition by basis pursuit, SIAM Rev., 43 (2001), pp. 129–159, . · Zbl 0979.94010
[10] A. Chambolle, An algorithm for total variation minimization and applications, J. Math. Imag. Vis., 20 (2004), pp. 89–97. · Zbl 1366.94048
[11] L. Condat, A direct algorithm for \textup1D total variation denoising, IEEE Signal Process. Lett., 20 (2013), pp. 1054–1057.
[12] E. Candès and B. Recht, Exact matrix completion via convex optimization, Found. Comput. Math., 9 (2009), pp. 717–772. · Zbl 1219.90124
[13] E. J. Candès and T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory, 51 (2005), pp. 4203–4215. · Zbl 1264.94121
[14] E. J. Candès and T. Tao, The Dantzig selector: Statistical estimation when \(p\) is much larger than \(n\), Ann. Statist., 35 (2007), pp. 2313–2351. · Zbl 1139.62019
[15] E. J. Candès and T. Tao, The power of convex relaxation: Near-optimal matrix completion, IEEE Trans. Inform. Theory, 56 (2010), pp. 2053–2080. · Zbl 1366.15021
[16] E. J. Candès, J. K. Romberg, and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math., 59 (2006), pp. 1207–1223. · Zbl 1098.94009
[17] I. Daubechies, M. Defrise, and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math., 57 (2004), pp. 1413–1457. · Zbl 1077.65055
[18] P. L. Davies and A. Kovac, Local extremes, runs, strings and multiresolution, Ann. Statist., 29 (2001), pp. 1–65. · Zbl 1029.62038
[19] H. Derksen, On the nuclear norm and the singular value decomposition of tensors, Found. Comput. Math., 16 (2016), pp. 779–811. · Zbl 1343.15016
[20] D. L. Donoho, De-noising by soft thresholding, IEEE Trans. Inform. Theory, 41 (1995), pp. 613–627. · Zbl 0820.62002
[21] B. Efron, I. Johnstone, T. Hastie, and R. Tibshirani, Least angle regression, Ann. Statist., 32 (2004), pp. 407–499.
[22] S. Friedland, Best rank-one approximation of real symmetric tensors can be chosen symmetric, Front. Math. China, 8 (2013), pp. 19–40. · Zbl 1264.15026
[23] S. Friedland and L.-H. Lim, Nuclear norm of higher-order tensors, Math. Comp., 87 (2018), pp. 1255–1281. · Zbl 1383.15018
[24] T. Goldstein and S. Osher, The split Bregman method for L\(1\)-regularized problems, SIAM J. Imaging Sci., 2 (2009), pp. 323–343, . · Zbl 1177.65088
[25] A. Grothendieck, Produits tensoriels topologiques et espaces nucléaires, Mem. Amer. Math. Soc., 1955 (1955), 16.
[26] M. Gu, L.-H. Lim, and C. J. Wu, ParNes: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals, Numer. Algorithms, 64 (2013), pp. 321–347. · Zbl 1284.65055
[27] P. C. Hansen, Analysis of discrete ill-posed problems by means of the L-curve, SIAM Rev., 34 (1992), pp. 561–580, . · Zbl 0770.65026
[28] P. C. Hansen and D. P. O’Leary, The use of the \(L\)-curve in the regularization of discrete ill-posed problems, SIAM J. Sci. Comput., 14 (1993), pp. 1487–1503, . · Zbl 0789.65030
[29] R. A. Harshman, Foundations of the PARAFAC procedure: Model and conditions for an explanatory multi-mode factor analysis, UCLA Working Papers in Phonetics, 16 (1970), 1.
[30] J. H\aa stad, Tensor rank is NP-complete, J. Algorithms, 11 (1990), pp. 644–654.
[31] F. L. Hitchcock, The expression of a tensor or a polyadic as a sum of products, J. Math. Phys., 6 (1927), pp. 164–189. · JFM 53.0095.01
[32] C. J. Hillar and L.-H. Lim, Most tensor problems are NP-hard, J. ACM, 60 (2013), 45. · Zbl 1281.68126
[33] S.-J. Kim, K. Koh, S. Boyd, and D. Gorinevsky, \(ℓ_1\) trend filtering, SIAM Rev., 51 (2009), pp. 339–360, .
[34] Y. Klinger, Relation between continental strike-slip earthquake segmentation and thickness of the crust, J. Geophys. Res., 115 (2010), B07306.
[35] J. Laderman, A noncommutative algorithm for multiplying \(3×3\) matrices using 23 multiplication, Bull. Amer. Math. Soc., 82 (1976), pp. 180–182.
[36] C. L. Lawson and R. J. Hanson, Solving Least Squares Problems, Classics Appl. Math. 15, SIAM, Philadelphia, 1995, ; first published by Prentice–Hall, 1974. · Zbl 0860.65028
[37] L.-H. Lim and P. Comon, Multiarray signal processing: Tensor decomposition meets compressed sensing, C. R. Acad. Sci. Paris Ser. IIB Mech., 338 (2010), pp. 311–320. · Zbl 1220.94018
[38] L. H. Lim and P. Comon, Blind multilinear identification, IEEE Trans. Inform. Theory, 60 (2014), pp. 1260–1280. · Zbl 1364.94139
[39] E. Mammen and S. van de Geer, Locally adaptive regression spines, Ann. Statist., 25 (1997), pp. 387–413. · Zbl 0871.62040
[40] K. Najarian, A. Belle, K. Ward, and H. Derksen, Early Detection of Hemodynamic Decompensation Using Taut-String Transformation, U.S. Provisional Patent Ser. 62/018,336; filed June 26, 2015.
[41] H. Ohlsson, F. Gustafsson, L. Ljung, and S. Boyd, Smoothed state estimates and abrupt changes using sum of norms regularization, Automatica J. IFAC, 48 (2012), pp. 595–605. · Zbl 1238.93105
[42] M. R. Osborne, B. Presnell, and B. A. Turlach, A new approach to variable selection in least square problems, IMA J. Numer. Anal., 20 (2000), pp. 389–404. · Zbl 0962.65036
[43] M. R. Osborne, B. Presnell, and B. A. Turlach, On the LASSO and its dual, J. Comput. Graph. Statist., 9 (2000), pp. 319–337.
[44] D. L. Phillips, A technique for the numerical solution of certain integral equations of the first kind, J. ACM, 9 (1962), pp. 84–97. · Zbl 0108.29902
[45] B. Recht, M. Fazel, and P. A. Parillo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52 (2010), pp. 471–501, . · Zbl 1198.90321
[46] L. I. Rudin, S. Osher, and E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D, 60 (1992), pp. 259–268. · Zbl 0780.49028
[47] R. Schatten, A Theory of Cross-Spaces, Princeton University Press, Princeton, NJ, 1950. · Zbl 0041.43502
[48] H. N. Tehrani, A. McEwan, C. Jin, and A. van Schaik, L1 regularization method in electrical impedance tomography by using the L1-curve (Pareto frontier curve), Appl. Math. Model., 36 (2012), pp. 1095–1105. · Zbl 1243.78041
[49] R. Tibshirani, Regression shrinkage and selection via the lasso, J. Roy. Statist. Soc. Ser. B, 58 (1996), pp. 267–288. · Zbl 0850.62538
[50] A. N. Tikhonov, Solution of incorrectly formulated problems and the regularization method, Soviet Math. Dokl., 4 (1963), pp. 1035–1038; English translation of Dokl. Akad. Nauk. SSSR, 151 (1963), pp. 501–504. · Zbl 0141.11001
[51] C. Wunsch, Toward a midlatitude ocean frequency—wavenumber spectral density and trend determination, J. Physical Oceanography, 40 (2010).
[52] H. Yamada and L. Jin, Japan’s output gap estimation and \(ℓ_1\) trend filtering, Empirical Econom., 45 (2013), pp. 81–88.
[53] H. Yamada and G. Yoon, When Grilli and Yang meet Prebisch and Singer: Piecewise linear trends in primary commodity prices, J. Internat. Money Finance, 42 (2014), pp. 193–207.
[54] M. Zhu and T. Chan, An Efficient Primal-Dual Hybrid Gradient Algorithm for Total Variation Image Restoration, UCLA CAM Report 08-34, UCLA, Los Angeles, CA, 2008.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.