The Hölder \(p\)-norm of an \(m\times n\) matrix has no explicit representation unless \(p=1,2\hbox{ or }\infty\). It is shown that the \(p\)- norm can be estimated reliably in \(O(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 a \(p\)-norm estimate correct to the specified accuracy, and the estimate is always within a factor \(n^{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 \textit{A. K. Cline}, \textit{A. R. Conn} and \textit{C. F. Van Loan} [Lect. Notes Math. 905, 73-83 (1982; Zbl 0532.65032)].