Summary
The Hölderp-norm of anm×n matrix has no explicit representation unlessp=1,2 or ∞. It is shown here that thep-norm can be estimated reliably inO(mn) operations. A generalization of the power method is used, with a starting vector determined by a technique with a condition estimation flavour. The algorithm nearly always computes ap-norm estimate correct to the specified accuracy, and the estimate is always within a factorn 1−1/p of ‖A‖ p . As a by-product, a new way is obtained to estimate the 2-norm of a rectangular matrix; this method is more general and produces better estimates in practice than a similar technique of Cline, Conn and Van Loan.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Anderson, E., Bai, Z., Bischof, C.H., Demmel, J.W., Dongarra, J., Du Croz, J.J., Greenbaum, A., Hammarling, S.J., McKenney, A., Ostrouchov, S., Sorensen, D.C. (1992): LAPACK Users' Guide, Society for Industrial and Applied Mathematics, Philadelphia (to appear)
Bartels, S.G. (1991): Two topics in matrix analysis: Structured sensitivity for Vandermondelike systems and a subgradient method for matrix norm estimation. M.Sc. Thesis, University of Dundee, Scotland
Boyd, D.W. (1974): The power method forl p norms. Linear Algebra and Appl.9, 95–101
Cline, A.K. (1972): Rate of convergence of Lawson's algorithm. Math. Comput.26, 167–176
Cline, A.K., Conn, A.R., Van Loan, C.F. (1982): Generalizing the LINPACK condition estimator. In: J.P. Hennart, ed., Numerical Analysis, Mexico 1981. Lecture Notes in Mathematics 909. Springer, Berlin Heidelberg New York, pp. 73–83
Fletcher, R. (1987): Practical Methods of Optimization, 2nd Ed. Wiley, Chichester
Fletcher, R., Grant, J.A., Hebden, M.D. (1971): The calculation of linear bestL p approximations, Comput. J.14, 276–279
Gastinel, N. (1970): Linear Numerical Analysis. Academic Press, London
Gilbert, J.R., Moler, C.B., Schreiber, R.S. (1992): Sparse matrices in MATLAB: Design and implementation. SIAM J. Matrix Anal. Appl.13, 333–356
Gillespie, T.A. (1991): Noncommutative variations on theorems of Marcel Riesz and others, In: J.H. Ewing, F.W. Gehring, eds., Paul Halmos: Celebrating 50 Years of Mathematics. Springer, Berlin Heidelberg New York
Goldberg, M., Straus, E.G. (1983): Multiplicativity ofl p norms for matrices. Linear Algebra Appl.52/53, 351–360
Golub G.H., Van Loan, C.F. (1989): Matrix Computations, 2nd Ed. Johns Hopkins University Press, Baltimore, Maryland
Hager, W.W. (1984): Condition estimates. SIAM J. Sci. Stat. Comput.5, 311–316
Hardy, G.H., Littlewood, J.E., Pólya, G. (1952): Inequalities, 2nd Ed. Cambridge University Press, Cambridge
Higham, N.J. (1987): A survey of condition number estimation for triangular matrices. SIAM Rev.29, 575–596
Higham, N.J. (1988): FORTRAN codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation (Algorithm 674). ACM Trans. Math. Soft.14, 381–396
Higham, N.J. (1990): Experience with a matrix norm estimator. SIAM J Sci. Stat. Comput.11, 804–809
Higham, N.J. (1993): Optimization by direct search in matrix computations, Numerical Analysis Report No. 197, University of Manchester, England, January 1991; SIAM J. Matrix Anal. Appl. (to appear)
Higham, N.J. (1991): Algorithm 694: A collection of test matrices in Matlab, ACM Trans. Math. Soft.17, 289–305
Horn R.A., Johnson, C.R. (1985): Matrix Analysis. Cambridge University Press, Cambridge
Kato, T. (1976): Perturbation Theory for Linear Operators, 2nd Ed. Springer, Berlin Heidelberg New York
Li, Y. (1991): A globally convergent method forL p problems. Technical Report 91-1212. Department of Computer Science, Cornell University, Ithaca, NY
Merle, G., Späth, H. (1974): Computational experiences with discreteL p -approximation. Computing12, 315–321
Moler, C.B., Little, J.N., Bangert, S. (1989); 386-Matlab User's Guide. The Math Works, Inc., 24 Prime Parkway, Natick, MA
Osborne, M.R. (1985): Finite Algorithms in Optimization and Data Analysis. Wiley, Chichester
Osborne, M.R., Watson, G.A. (1985): An analysis of the total approximation problem in separable norms, and an algorithm for the totall 1 problem. SIAM J. Sci. Stat. Comput.6, 410–424
Späth, H., Watson, G.A. (1987): On orthogonal linearl 1 approximation. Numer. Math.51, 531–543
Schneider, H., Strang, W.G. (1962): Comparison theorems for supremum norms. Numer. Math.4, 15–20
Pham Dinh Tao, (1984): Convergence of a subgradient method for computing the bound norm of matrices [in French]. Linear Algebra Appl.62, 163–182
Todd, J. (1977): Basic Numerical Mathematics, Vol. 2. Numerical Algebra. Birkhäuser, Basel; Academic Press, New York
Van Loan, C.F. (1987): On estimating the condition of eigenvalues and eigenvectors. Linear Algebra Appl.88/89, 715–732
Watson, G.A. (1980): Approximation Theory and Numerical Methods. Wiley, Chichester
Watson, G.A. (1983): The total approximation problem. In C.K. Chui, L.L. Schumaker, J.D. Ward, eds., Approximation Theory IV. Academic Press, New York, pp. 723–728
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Higham, N.J. Estimating the matrixp-norm. Numer. Math. 62, 539–555 (1992). https://doi.org/10.1007/BF01396242
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01396242