Two curve Chebyshev approximation and its application to signal clustering. (English) Zbl 1428.94038
Summary: In this paper, we extend a number of important results of the classical Chebyshev approximation theory to the case of simultaneous approximation of two or more functions. The need for this extension is application driven, since such kind of problems appears in the area of curve (signal) clustering. In this paper, we propose a new efficient algorithm for signal clustering and develop a procedure that allows one to reuse the results obtained at the previous iteration without recomputing the cluster centres from scratch. This approach is based on the extension of the classical de la Vallée-Poussin procedure originally developed for polynomial approximation. We also develop necessary and sufficient optimality conditions for two curve Chebyshev approximation, which is our core tool for curve clustering. These results are based on application of nonsmooth convex analysis.
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 41A50 | Best approximation, Chebyshev systems |
| 90C47 | Minimax problems in mathematical programming |
| 90C90 | Applications of mathematical programming |
Keywords:
Chebyshev approximation; convex analysis; nonsmooth analysis; linear programming; signal clusteringReferences:
| [1] | MacQueen, J., Some methods for classification and analysis of multivariate observations, Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 281-297 (1967), University of California Press · Zbl 0214.46201 |
| [2] | Späth, H., Cluster Analysis Algorithms for Data Reduction and Classification of Objects (1980), Ellis Horwood Limited: Ellis Horwood Limited Chichester · Zbl 0435.62059 |
| [3] | Bagirov, A.; Ugon, J., Nonsmooth DC programming approach to clusterwise linear regression: optimality conditions and algorithms, Optim. Methods Softw., 33, 1, 194-219 (2018) · Zbl 1390.90436 |
| [4] | Kaufman, L.; Rousseeuw, P., Finding Groups in Data: An Introduction to Cluster Analysis (1990), Wiley · Zbl 1345.62009 |
| [5] | Hastie, T.; Tibshirani, R.; Friedman, J., The Elements of Statistical Learning Data Mining, Inference, and Prediction, Springer Series in Satistics (2008), Springer |
| [6] | Remez, E., General computational methods of Chebyshev approximation, Atom. Energy Transl., 4491, 1-85 (1957) |
| [7] | E. Remez, Foundations of Numerical Methods of Chebyshev Approximation, Naukova Dumka, Kiev.; E. Remez, Foundations of Numerical Methods of Chebyshev Approximation, Naukova Dumka, Kiev. · Zbl 0233.65007 |
| [8] | Rice, J., The Approximation of Functions: Linear Theory, Addison-Wesley Series in Computer Science and Information Processing (1964), Addison-Wesley Pub. Co. · Zbl 0114.27001 |
| [9] | E. Cheney, W. Light, A Course in Approximation Theory, Graduate Studies in Mathematics, American Mathematical Soc.; E. Cheney, W. Light, A Course in Approximation Theory, Graduate Studies in Mathematics, American Mathematical Soc. · Zbl 1167.41001 |
| [10] | Dantzig, G. B., Linear Programming and Extensions (1963), Princeton University Press: Princeton University Press Princeton, New Jersey · Zbl 0108.33103 |
| [11] | Klee, V.; Minty, G. J., How good is the simplex algorithm?, (Shisha, O., Inequalities III (1972), Academic Press Inc.: Academic Press Inc. New York), 159-175 · Zbl 0297.90047 |
| [12] | Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 4, 373-395 (1984) · Zbl 0557.90065 |
| [13] | Nocedal, J.; Wright, S., Numerical Optimization (2006), Springer-Verlag, Inc.: Springer-Verlag, Inc. New York · Zbl 1104.65059 |
| [14] | Sukhorukova, N., An interior point method and Sherman-Morrison formula for solving large scale convex quadratic problems with diagonal Hessians, ANZIAM J., 56, E, E1-E21 (2015) · Zbl 1347.90065 |
| [15] | de la Valle Poussin, C. J., Sur la methode de lapproximation minimum, Ann. Soc. Sci. Brux., 35, 1-16 (1911) · JFM 42.0255.02 |
| [16] | Rockafellar, R., Convex Analysis (1970), Princeton University Press: Princeton University Press Princeton, New Jersey · Zbl 0193.18401 |
| [17] | Zalinescu, C., Convex Analysis in General Vector Spaces (2002), World Scientific · Zbl 1023.46003 |
| [18] | Chebyshev, P., Théorie des mécanismes connus sous le nom de parallélogrammes, 1ère partie, Mémoires Présentés à l’Académie Impériale des Sciences de Saint-Pétersbourg par Divers Savants (1854) |
| [19] | Karlin, S.; Studden, W., Tchebycheff Systems: With Applications in Analysis and Statistics (1966), Interscience Publishers: Interscience Publishers New York · Zbl 0153.38902 |
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.
