×

On orthogonal linear \(\ell_1\) approximation. (English) Zbl 0633.65010

By using a special approach to a given data fitting problem the authors arrive at a minimization problem of the following form: minimize \(\| Zv\|_ 1\) subject to \(v\in {\mathbb{R}}^ n\) and \(\| v\|_ 2=1\), where Z is a given \(m\times n\)-matrix. This problem is equivalent to a concave quadratic programming problem. A characterization of local solutions and a result on the stability of these solutions under small perturbations of the matrix Z is given. Moreover, an algorithm for solving the minimization problem is presentd and its convergence to a special solution is shown. Finally, the performance of the algorithm is illustrated by applying the method to some examples known in the literature.
Reviewer: G.Nürnberger

MSC:

65D10 Numerical smoothing, curve fitting
41A50 Best approximation, Chebyshev systems
65K05 Numerical mathematical programming methods
90C20 Quadratic programming
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Barrodale, I., Roberts, F.D.K.: An improved algorithm for discrete ?1 linear approximation. SIAM J. Numer. Anal.10, 839-848 (1973) · Zbl 0266.65016 · doi:10.1137/0710069
[2] Bartles, R.H., Conn, A.R., Sinclair, J.W.: Minimization techniques for piecewise differentiable functions: the ?1 solution to an overdetermined linear system. SIAM J. Numer. Anal15, 224-241 (1978) · Zbl 0376.65018 · doi:10.1137/0715015
[3] Daniel, C., Wood, F.S.: Fitting Equations to Data. New York: John Wiley 1971 · Zbl 0264.65011
[4] Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Res. Log. Quart.3, 95-110 (1956) · doi:10.1002/nav.3800030109
[5] Golub, G.H., van Loan, C.F.: An analysis of the total least squares problem. SIAM J. Numer. Anal.17, 883-893 (1980) · Zbl 0468.65011 · doi:10.1137/0717073
[6] Osborne, M.R., Watson, G.A.: An analysis of the total approximation problem in separable norms, and an algorithm for the total ?1 problem. SIAM J. Sci. Stat. Comp.6, 410-424 (1985) · Zbl 0581.41019 · doi:10.1137/0906029
[7] Späth, H.: Algorithmen für multivariable Ausgleichsmodelle. Munich: R. Oldenbourg 1974 · Zbl 0327.65016
[8] Späth, H.: On discrete linear orthogonalL p approximation. ZAMM62, 354-355 (1982)
[9] Watson, G.A.: Approximation Theory and Numerical Methods. Chichester: John Wiley 1980 · Zbl 0442.65005
[10] Watson, G.A.: Numerical methods for linear orthogonalL p approximation. IMA J Numer. Anal.2, 275-287 (1982) · Zbl 0489.65012 · doi:10.1093/imanum/2.3.275
[11] Watson, G.A.: The total approximation problem. In: Approximation Theory IV (C.K. Chui, L.L. Schumaker, J.D. Ward, eds.) New York: Academic Press, 1983 · Zbl 0539.41035
[12] Wulff, A.: Numerische Verahren zur linearen orthogonalenL p?Regression. Diplomarbeit Universität Oldenburg 1983
[13] Zoutendijk, G.: Mathematical Programming Methods. Amsterdam: North Holland 1976 · Zbl 0337.90036
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.