Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-28T12:06:33.308Z Has data issue: false hasContentIssue false
  • English
  • Français

Choice of norms for data fitting and function approximation

Published online by Cambridge University Press:  07 November 2008

G. A. Watson
G. A. Watson
Affiliation:
Department of Mathematics, University of Dundee, Dundee DD1 4HN, Scotland E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

For the approximation of functions and data, it is often appropriate to minimize a norm. Many norms have been considered, and a review is presented of methods for solving a range of problems using a wide variety of norms.

Type
Research Article
Information
Acta Numerica , Volume 7 , January 1998 , pp. 337 - 377
Copyright
Copyright © Cambridge University Press 1998

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Barrodale, I. and Phillips, C. (1975), An improved algorithm for discrete Chebyshev linear approximation, in Proc. 4th Manitoba Conf. on Numer. Math. (Hartnell, B. L. and Williams, H. C., eds), University of Manitoba (Winnipeg, Canada), pp. 177–190.Google Scholar
Barrodale, I. and Roberts, F. D. K. (1973), ‘An improved algorithm for discrete l 1 linear approximation’, SIAM J. Numer. Anal. 10, 839–848.CrossRefGoogle Scholar
Barrodale, I., Powell, M. J. D. and Roberts, F. D. K. (1972), ‘The differential correction algorithm for rational l ∞ approximation’, SIAM J. Numer. Anal. 9, 493–504.CrossRefGoogle Scholar
Bartels, R., Conn, A. R. and Li, Y. (1989), ‘Primal methods are better than dual methods for solving overdetermined linear systems in the l ∞ sense?’, SIAM J. Numer. Anal. 26, 693–726.Google Scholar
Bartels, R., Conn, A. R. and Sinclair, J. W. (1978), ‘Minimisation techniques for piecewise differentiable functions: the l 1solution to an overdetermined linear system’, SIAM J. Numer. Anal. 15, 224–241.CrossRefGoogle Scholar
Bloomfield, P. and Steiger, W. L. (1983), Least Absolute Deviations, Birkhäuser, Boston.Google Scholar
Boggs, P. T., Byrd, R. H. and Schnabel, R. B. (1987), ‘A stable and efficient algorithm for nonlinear orthogonal distance regression’, SIAM J. Sci. Statist. Comput. 8, 1052–1078.CrossRefGoogle Scholar
Boggs, P. T., Byrd, R. H., Donaldson, J. R. and Schnabel, R. B. (1989), ‘ODRPACK, Software for weighted orthogonal distance regression’, ACM Trans. Math. Software 15, 348–364.CrossRefGoogle Scholar
Boncelet, C. G. Jr and Dickinson, B. W. (1984), ‘A variant of Huber robust regression’, SIAM J. Sci. Statist. Comput. 5, 720–734.CrossRefGoogle Scholar
Braess, D. (1971), ‘Chebyshev approximation by spline functions with free knots’, Numer. Math. 17, 357–366.CrossRefGoogle Scholar
Breuer, P. T. (1987), A new method for real rational uniform approximation, in Algorithms for Approximation (Mason, J. C. and Cox, M. G., eds), Clarendon Press, Oxford, pp. 265–283.Google Scholar
Brosowski, B. and da Silva, A. R. (1992), A general alternation theorem, in Approximation Theory (Anastassiou, G. A., ed.), Marcel Dekker, Inc., New York, pp. 137–150.Google Scholar
Cheney, E. W. and Loeb, H. L. (1961), ‘Two new algorithms for rational approximation’, Numer. Math. 3, 72–75.CrossRefGoogle Scholar
Cheney, E. W. and Powell, M. J. D. (1987), ‘The differential correction algorithm for generalized rational functions’, Constr. Approx. 3, 249–256.Google Scholar
Clark, D. I. (1985), ‘The mathematical structure of Huber' s M-estimator’, SIAM J. Sci. Statist. Comput. 6, 209–219.CrossRefGoogle Scholar
Clark, D. I. and Osborne, M. R. (1986), ‘Finite algorithms for Huber' s M-estimator’, SIAM J. Sci. Statist. Comput. 7, 72–85.CrossRefGoogle Scholar
Coleman, T. and Li, Y. (1992a), ‘A globally and quadratically convergent affine scaling algorithm for l 1 problems’, Math. Prog. 56, 189–222.CrossRefGoogle Scholar
Coleman, T. and Li, Y. (1992b), ‘A globally and quadratically convergent method for linear l ∞ problems’, SIAM J. Numer. Anal. 29, 1166–1186.CrossRefGoogle Scholar
Dax, A. (1989), ‘The minimax solution of linear equations subject to linear constraints’, IMA J Numer. Anal. 9, 95–109.CrossRefGoogle Scholar
Dax, A. (1993), ‘A row relaxation method for large minimax problems’, BIT 33, 262–276.CrossRefGoogle Scholar
Dax, A. and Berkowitz, B. (1990), ‘Column relaxation methods for least norm problems’, SIAM J. Sci. Statist. Comput. 11, 975–989.Google Scholar
Dua, S. N. and Loeb, H. L. (1973), ‘Further remarks on the differential correction algorithm’, SIAM J. Numer. Anal. 10, 123–126.CrossRefGoogle Scholar
Duarte, A. M. and Vanderbei, R. J. (1994), Interior point algorithms for lsad and lmad estimation, Technical Report SOR-94-07, Programs in Operations Research and Statistics, Princeton University.Google Scholar
Ekblom, H. and Nielsen, H. B. (1996), A comparison of eight algorithms for computing M-estimates, Technical Report 1996–15, Technical University of Denmark.CrossRefGoogle Scholar
Golub, G. H. and Van Loan, C. F. (1980), ‘An analysis of the total least squares problem’, SIAM J. Numer. Anal. 17, 883–893.CrossRefGoogle Scholar
Gugat, M. (1996a), ‘An algorithm for Chebyshev approximation by rationals with constrained denominators’, Constr. Approx. 12, 197–221.CrossRefGoogle Scholar
Gugat, M. (1996b), ‘The Newton differential correction algorithm for uniform rational approximation with constrained denominators’, Numer. Algorithms 13, 107–122.Google Scholar
Hettich, R. and Zenke, P. (1990), ‘An algorithm for general restricted rational Chebyshev approximation’, SIAM J. Numer. Anal. 27, 1024–1033.CrossRefGoogle Scholar
Jing, Z. and Fam, A. T. (1987), ‘An algorithm for computing continuous Chebyshev approximations’, Math. Comp. 48, 691–710.CrossRefGoogle Scholar
Jonasson, K. (1993), ‘A projected conjugate gradient method for sparse minimax problems’, Numer. Algorithms 5, 309–323.CrossRefGoogle Scholar
Jonasson, K. and Madsen, K. (1994), ‘Corrected sequential linear programming for sparse minimax optimization’, BIT 34, 372–387.CrossRefGoogle Scholar
Jonasson, K. and Watson, G. A. (1982), A Lagrangian method for multivariate continuous Chebyshev approximation problems, in Multivariate Approximation Theory 2 (Schempp, W. and Zeller, K., eds), Birkhäuser, Basel, pp. 211–221.CrossRefGoogle Scholar
Kaufman, E. H. and Taylor, G. D. (1981), ‘Uniform approximationby rational functions having restricted denominators’, J. Approx. Theory 32, 9–26.CrossRefGoogle Scholar
Kawasaki, H. (1994), ‘A second-order property of spline functions with one free knot’, J. Approx. Theory 78, 293–297.Google Scholar
Li, C. and Watson, G. A. (1997), ‘Strong uniqueness in restrictedrational approximation’, J. Approx. Theory 89, 96–113.CrossRefGoogle Scholar
Li, W. and Swetits, J. J. (1998), ‘Linear l 1 estimatorand Huber M-estimator’, SIAM J. Optim. To appear.CrossRefGoogle Scholar
Li, Y. (1993), ‘A globally convergent method for l p problems’, SIAM J. Optim. 3, 609–629.CrossRefGoogle Scholar
Madsen, K. and Nielsen, H. B. (1993), ‘A finite smoothing algorithm for linear l 1 estimation’, SIAM J. Optim. 3, 223–235.CrossRefGoogle Scholar
Madsen, K., Nielsen, H. B. and Pinar, M. C. (1994), ‘New characterizations of L 1 solutions of overdetermined linear systems’, Operations Research Lett. 16, 159–166.CrossRefGoogle Scholar
Meinardus, G. (1967), Approximation of Functions: Theory and Numerical Methods, Springer, Berlin.CrossRefGoogle Scholar
Meinardus, G., Nürnberger, G. and Walz, G. (1996), ‘Bivariatesegment approximation and splines’, Adv. Comput. Math. 6, 25–45.CrossRefGoogle Scholar
Meinardus, G., Nürnberger, G., Sommer, M. and Strauss, H. (1989), ‘Algorithms for piecewise polynomials and splines with free knots’, Math. Comp. 53, 235–247.CrossRefGoogle Scholar
Meketon, M. S. (1987), Least absolute value regression, Technical report, AT&T Bell Laboratories, Murray Hill, New Jersey.Google Scholar
Micchelli, C. A. (1977), ‘Best L 1 approximation by weak Chebyshev systems and the uniqueness of interpolating perfect splines’, J. Approx. Theory 19, 1–14.CrossRefGoogle Scholar
Moran, P. A. P. (1959), ‘Random processes in economic theory and analysis’, Sankhya 21, 99–126.Google Scholar
Mulansky, B. (1992), ‘Chebyshev approximation by spline functions with free knots’, IMA J. Numer. Anal. 12, 95–105.CrossRefGoogle Scholar
Nürnberger, G. (1987), ‘Strongly unique spline approximation with free knots’, Constr. Approx. 3, 31–42.Google Scholar
Nürnberger, G. (1989), Approximation by Spline Functions, Springer, Berlin.Google Scholar
Nürnberger, G. (1994a), Approximation by univariate and bivariate splines, in Second International Colloquium on Numerical Analysis (Bainov, D. and Covachev, V., eds), VSP, Utrecht, pp. 143–153.Google Scholar
Nurnberger, G. (1994b), ‘Strong unicity in nonlinear approximation and free knot splines’, Constr. Approx. 10, 285–299.Google Scholar
Nürnberger, G. (1996), ‘Bivariate segment approximation and free knot splines: research problems 96–4’, Constr. Approx. 12, 555–558.Google Scholar
Nürnberger, G. (1997), Optimal partitions in bivariate segment approximation, in Surface Fitting and Multiresolution Methods (Le Mehaute, A., Rabut, C. and Schumaker, L. L., eds), Vanderbilt University Press, Nashville, pp. 271–278.Google Scholar
Nürnberger, G. and Sommer, M. (1983), ‘A Remez type algorithm for spline functions’, Numer. Math. 41, 117–146.CrossRefGoogle Scholar
Nürnberger, G., Schumaker, L. L., Sommer, M. and Strauss, H. (1985), ‘Approximation by generalized splines’, J. Math. Anal. Appl. 108, 466–494.Google Scholar
Nürnberger, G., Schumaker, L. L., Sommer, M. and Strauss, H. (1989), ‘Uniform approximation by generalized splines with free knots’, J. Approx. Theory 59, 150–169.CrossRefGoogle Scholar
Nürnberger, G., Sommer, M. and Strauss, H. (1986), ‘An algorithm for segment approximation’, Numer. Math. 48, 463–477.Google Scholar
Osborne, M. R. (1985), Finite Algorithms in Optimisation and Data Analysis, Wiley, Chichester.Google Scholar
Osborne, M. R. (1987), The reduced gradient algorithm, in Statistical Data Analysis Based on the L 1 Norm and Related Methods (Dodge, Y., ed.), North Holland, Amsterdam, pp. 95–107.Google Scholar
Osborne, M. R. and Watson, G. A. (1985), ‘An analysis of the total approximation problem in separable norms, and an algorithm for the total l 1 problem’, SIAM J. Sci. Statist. Comput. 6, 410–424.Google Scholar
Osborne, M. R. and Watson, G. A. (1996), Aspects of M-estimation and l l fitting problems, in Numerical Analysis: A R Mitchell 75th Birthday Volume (Griffiths, D. F and Watson, G. A., eds), World Scientific, Singapore, pp. 247–261.CrossRefGoogle Scholar
Pinkus, A. (1989), On L 1 Approximation, Cambridge University Press, Cambridge.Google Scholar
Rice, J. R. (1967), ‘Characterization of Chebyshev approximation by splines’, SIAM J. Math. Anal. 4, 557–567.Google Scholar
Rosen, J. B., Park, H. and Glick, J. (1996), ‘Total least norm formulation and solution for structured problems’, SIAM J. Matrix Anal. Appl. 17, 110–126.CrossRefGoogle Scholar
Rosen, J. B., Park, H. and Glick, J. (1997), Total least norm for linear and nonlinear structured problems, in Recent Advances in Total Least Squares Techniques and Errors-in-Variables Modeling (Van Huffel, S., ed.), SIAM, Philadelphia, pp. 203–214.Google Scholar
Ruzinsky, S. A. and Olsen, E. T. (1989), ‘l 1 and l ∞ minimization via a variant of Karmarkar' s algorithm’, IEEE Trans. Acoustics, Speech and Signal Processing 37, 245–253.CrossRefGoogle Scholar
Schumaker, L. L. (1968), ‘Uniform approximation by Tchebychefnan spline functions’, J. Math. Mech. 18, 369–378.Google Scholar
Shi, M. and Lukas, M. A. (1996), ‘On the reduced gradient algorithm for L 1 norm minimization with linear constraints’. Research Report, Department of Mathematics and Statistics, Murdoch University, Australia.Google Scholar
Späth, H. and Watson, G. A. (1987), ‘On orthogonal linear L 1 regression’, Numer. Math. 51, 531–543.CrossRefGoogle Scholar
Watson, G. A. (1976), ‘A method for calculating best nonlinear Chebyshev approximations’, J. Inst. Math. Appl. 18, 351–360.Google Scholar
Watson, G. A. (1980), Approximation Theory and Numerical Methods, Wiley, Chichester.Google Scholar
Watson, G. A. (1981), ‘An algorithm for linear L 1 approximation of continuous functions’, IMA J. Numer. Anal. 1, 157–167.Google Scholar
Watson, G. A. (1982), A globally convergent method for (constrained) nonlinear continuous L 1 approximation problems, in Numerical Methods of Approximation Theory 1981 (Collatz, L., Meinardus, G. and Werner, H., eds), Birkhäuser, Berlin, pp. 233–243. ISNM 59.Google Scholar
Watson, G. A. (1983), The total approximation problem, in Approximation Theory IV (Chui, C. K., Schumaker, L. L. and Ward, J. D., eds), Academic Press, New York, pp. 723–728.Google Scholar
Watson, G. A. (1984), The numerical solution of total l p approximation problems, in Numerical Analysis Dundee 1983 (Griffiths, D. F., ed.), Springer, Berlin, pp. 221–238.Google Scholar
Watson, G. A. (1987), Methods for best approximation and regression problems, in The State of the Art in Numerical Analysis (Iserles, A. and Powell, M. J. D., eds), Clarendon Press, Oxford, pp. 139–164.Google Scholar
Watson, G. A. (1988), ‘The smallest perturbation of a submatrix which lowers the rank of the matrix’, IMA J. Numer. Anal. 8, 295–303.CrossRefGoogle Scholar
Watson, G. A. (1991), ‘On a general class of matrix nearness problems’, Constr. Approx. 7, 299–314.Google Scholar
Watson, G. A. (1997), The use of the L 1 norm in nonlinear errors-in-variables problems, in Recent Advances in Total Least Squares Techniques and Errors-in-Variables Modeling (Van Huffel, S., ed.), SIAM, Philadelphia, pp. 183–192.Google Scholar
Watson, G. A. and Yiu, K. F. C. (1991), ‘On the solution of the errors in variables problem using the l 1 norm’, BIT 31, 697–710.Google Scholar
Zhang, Y. (1993), ‘A primal-dual interior point approach for computing the l 1 and l ∞ solutions of overdetermined linear systems’, J. Optim. Theory Appl. 77, 323–341.CrossRefGoogle Scholar