Hessian matrix

Last updated

In mathematics, the Hessian matrix or Hessian is a square matrix of second-order partial derivatives of a scalar-valued function, or scalar field. It describes the local curvature of a function of many variables. The Hessian matrix was developed in the 19th century by the German mathematician Ludwig Otto Hesse and later named after him. Hesse originally used the term "functional determinants".

Contents

Definitions and properties

Suppose is a function taking as input a vector and outputting a scalar If all second-order partial derivatives of exist, then the Hessian matrix of is a square matrix, usually defined and arranged as follows:

or, by stating an equation for the coefficients using indices i and j,

If furthermore the second partial derivatives are all continuous, the Hessian matrix is a symmetric matrix by the symmetry of second derivatives.

The determinant of the Hessian matrix is called the Hessian determinant. [1]

The Hessian matrix of a function is the Jacobian matrix of the gradient of the function ; that is:

Applications

Inflection points

If is a homogeneous polynomial in three variables, the equation is the implicit equation of a plane projective curve. The inflection points of the curve are exactly the non-singular points where the Hessian determinant is zero. It follows by Bézout's theorem that a cubic plane curve has at most inflection points, since the Hessian determinant is a polynomial of degree

Second-derivative test

The Hessian matrix of a convex function is positive semi-definite. Refining this property allows us to test whether a critical point is a local maximum, local minimum, or a saddle point, as follows:

If the Hessian is positive-definite at then attains an isolated local minimum at If the Hessian is negative-definite at then attains an isolated local maximum at If the Hessian has both positive and negative eigenvalues, then is a saddle point for Otherwise the test is inconclusive. This implies that at a local minimum the Hessian is positive-semidefinite, and at a local maximum the Hessian is negative-semidefinite.

For positive-semidefinite and negative-semidefinite Hessians the test is inconclusive (a critical point where the Hessian is semidefinite but not definite may be a local extremum or a saddle point). However, more can be said from the point of view of Morse theory.

The second-derivative test for functions of one and two variables is simpler than the general case. In one variable, the Hessian contains exactly one second derivative; if it is positive, then is a local minimum, and if it is negative, then is a local maximum; if it is zero, then the test is inconclusive. In two variables, the determinant can be used, because the determinant is the product of the eigenvalues. If it is positive, then the eigenvalues are both positive, or both negative. If it is negative, then the two eigenvalues have different signs. If it is zero, then the second-derivative test is inconclusive.

Equivalently, the second-order conditions that are sufficient for a local minimum or maximum can be expressed in terms of the sequence of principal (upper-leftmost) minors (determinants of sub-matrices) of the Hessian; these conditions are a special case of those given in the next section for bordered Hessians for constrained optimization—the case in which the number of constraints is zero. Specifically, the sufficient condition for a minimum is that all of these principal minors be positive, while the sufficient condition for a maximum is that the minors alternate in sign, with the minor being negative.

Critical points

If the gradient (the vector of the partial derivatives) of a function is zero at some point then has a critical point (or stationary point ) at The determinant of the Hessian at is called, in some contexts, a discriminant. If this determinant is zero then is called a degenerate critical point of or a non-Morse critical point of Otherwise it is non-degenerate, and called a Morse critical point of

The Hessian matrix plays an important role in Morse theory and catastrophe theory, because its kernel and eigenvalues allow classification of the critical points. [2] [3] [4]

The determinant of the Hessian matrix, when evaluated at a critical point of a function, is equal to the Gaussian curvature of the function considered as a manifold. The eigenvalues of the Hessian at that point are the principal curvatures of the function, and the eigenvectors are the principal directions of curvature. (See Gaussian curvature § Relation to principal curvatures.)

Use in optimization

Hessian matrices are used in large-scale optimization problems within Newton-type methods because they are the coefficient of the quadratic term of a local Taylor expansion of a function. That is,

where is the gradient Computing and storing the full Hessian matrix takes memory, which is infeasible for high-dimensional functions such as the loss functions of neural nets, conditional random fields, and other statistical models with large numbers of parameters. For such situations, truncated-Newton and quasi-Newton algorithms have been developed. The latter family of algorithms use approximations to the Hessian; one of the most popular quasi-Newton algorithms is BFGS. [5]

Such approximations may use the fact that an optimization algorithm uses the Hessian only as a linear operator and proceed by first noticing that the Hessian also appears in the local expansion of the gradient:

Letting for some scalar this gives

that is,

so if the gradient is already computed, the approximate Hessian can be computed by a linear (in the size of the gradient) number of scalar operations. (While simple to program, this approximation scheme is not numerically stable since has to be made small to prevent error due to the term, but decreasing it loses precision in the first term. [6] )

Notably regarding Randomized Search Heuristics, the evolution strategy's covariance matrix adapts to the inverse of the Hessian matrix, up to a scalar factor and small random fluctuations. This result has been formally proven for a single-parent strategy and a static model, as the population size increases, relying on the quadratic approximation. [7]

Other applications

The Hessian matrix is commonly used for expressing image processing operators in image processing and computer vision (see the Laplacian of Gaussian (LoG) blob detector, the determinant of Hessian (DoH) blob detector and scale space). The Hessian matrix can also be used in normal mode analysis to calculate the different molecular frequencies in infrared spectroscopy. [8]

Generalizations

Bordered Hessian

A bordered Hessian is used for the second-derivative test in certain constrained optimization problems. Given the function considered previously, but adding a constraint function such that the bordered Hessian is the Hessian of the Lagrange function [9]

If there are, say, constraints then the zero in the upper-left corner is an block of zeros, and there are border rows at the top and border columns at the left.

The above rules stating that extrema are characterized (among critical points with a non-singular Hessian) by a positive-definite or negative-definite Hessian cannot apply here since a bordered Hessian can neither be negative-definite nor positive-definite, as if is any vector whose sole non-zero entry is its first.

The second derivative test consists here of sign restrictions of the determinants of a certain set of submatrices of the bordered Hessian. [10] Intuitively, the constraints can be thought of as reducing the problem to one with free variables. (For example, the maximization of subject to the constraint can be reduced to the maximization of without constraint.)

Specifically, sign conditions are imposed on the sequence of leading principal minors (determinants of upper-left-justified sub-matrices) of the bordered Hessian, for which the first leading principal minors are neglected, the smallest minor consisting of the truncated first rows and columns, the next consisting of the truncated first rows and columns, and so on, with the last being the entire bordered Hessian; if is larger than then the smallest leading principal minor is the Hessian itself. [11] There are thus minors to consider, each evaluated at the specific point being considered as a candidate maximum or minimum. A sufficient condition for a local maximum is that these minors alternate in sign with the smallest one having the sign of A sufficient condition for a local minimum is that all of these minors have the sign of (In the unconstrained case of these conditions coincide with the conditions for the unbordered Hessian to be negative definite or positive definite respectively).

Vector-valued functions

If is instead a vector field that is,

then the collection of second partial derivatives is not a matrix, but rather a third-order tensor. This can be thought of as an array of Hessian matrices, one for each component of :

This tensor degenerates to the usual Hessian matrix when

Generalization to the complex case

In the context of several complex variables, the Hessian may be generalized. Suppose and write Then the generalized Hessian is If satisfies the n-dimensional Cauchy–Riemann conditions, then the complex Hessian matrix is identically zero.

Generalizations to Riemannian manifolds

Let be a Riemannian manifold and its Levi-Civita connection. Let be a smooth function. Define the Hessian tensor by

where this takes advantage of the fact that the first covariant derivative of a function is the same as its ordinary derivative. Choosing local coordinates gives a local expression for the Hessian as

where are the Christoffel symbols of the connection. Other equivalent forms for the Hessian are given by

See also

Notes

    1. Binmore, Ken; Davies, Joan (2007). Calculus Concepts and Methods. Cambridge University Press. p. 190. ISBN   978-0-521-77541-0. OCLC   717598615.
    2. Callahan, James J. (2010). Advanced Calculus: A Geometric View. Springer Science & Business Media. p. 248. ISBN   978-1-4419-7332-0.
    3. Casciaro, B.; Fortunato, D.; Francaviglia, M.; Masiello, A., eds. (2011). Recent Developments in General Relativity. Springer Science & Business Media. p. 178. ISBN   9788847021136.
    4. Domenico P. L. Castrigiano; Sandra A. Hayes (2004). Catastrophe theory. Westview Press. p. 18. ISBN   978-0-8133-4126-2.
    5. Nocedal, Jorge; Wright, Stephen (2000). Numerical Optimization. Springer Verlag. ISBN   978-0-387-98793-4.
    6. Pearlmutter, Barak A. (1994). "Fast exact multiplication by the Hessian" (PDF). Neural Computation. 6 (1): 147–160. doi:10.1162/neco.1994.6.1.147. S2CID   1251969.
    7. Shir, O.M.; A. Yehudayoff (2020). "On the covariance-Hessian relation in evolution strategies". Theoretical Computer Science. Elsevier. 801: 157–174. doi: 10.1016/j.tcs.2019.09.002 .
    8. Mott, Adam J.; Rez, Peter (December 24, 2014). "Calculation of the infrared spectra of proteins". European Biophysics Journal. 44 (3): 103–112. doi:10.1007/s00249-014-1005-6. ISSN   0175-7571. PMID   25538002. S2CID   2945423.
    9. Hallam, Arne (October 7, 2004). "Econ 500: Quantitative Methods in Economic Analysis I" (PDF). Iowa State.
    10. Neudecker, Heinz; Magnus, Jan R. (1988). Matrix Differential Calculus with Applications in Statistics and Econometrics. New York: John Wiley & Sons. p. 136. ISBN   978-0-471-91516-4.
    11. Chiang, Alpha C. (1984). Fundamental Methods of Mathematical Economics (Third ed.). McGraw-Hill. p.  386. ISBN   978-0-07-010813-4.

    Further reading

    Related Research Articles

    <span class="mw-page-title-main">Divergence</span> Vector operator that measures the expansion or outgoingness of a vector field

    In vector calculus, divergence is a vector operator that operates on a vector field, producing a scalar field giving the quantity of the vector field's source at each point. More technically, the divergence represents the volume density of the outward flux of a vector field from an infinitesimal volume around a given point.

    <span class="mw-page-title-main">Gradient</span> Multivariate derivative (mathematics)

    In vector calculus, the gradient of a scalar-valued differentiable function f of several variables is the vector field whose value at a point is the vector whose components are the partial derivatives of at . That is, for , its gradient is defined at the point in n-dimensional space as the vector

    In particle physics, the Dirac equation is a relativistic wave equation derived by British physicist Paul Dirac in 1928. In its free form, or including electromagnetic interactions, it describes all spin-12 massive particles, called "Dirac particles", such as electrons and quarks for which parity is a symmetry. It is consistent with both the principles of quantum mechanics and the theory of special relativity, and was the first theory to account fully for special relativity in the context of quantum mechanics. It was validated by accounting for the fine structure of the hydrogen spectrum in a completely rigorous way.

    Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize a multivariate quadratic function subject to linear constraints on the variables. Quadratic programming is a type of nonlinear programming.

    In mathematics, a symmetric matrix with real entries is positive-definite if the real number is positive for every nonzero real column vector where is the transpose of . More generally, a Hermitian matrix is positive-definite if the real number is positive for every nonzero complex column vector where denotes the conjugate transpose of

    In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equality constraints. It is named after the mathematician Joseph-Louis Lagrange. The basic idea is to convert a constrained problem into a form such that the derivative test of an unconstrained problem can still be applied. The relationship between the gradient of the function and gradients of the constraints rather naturally leads to a reformulation of the original problem, known as the Lagrangian function.

    In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a scalar function on Euclidean space. It is usually denoted by the symbols , , or . In a Cartesian coordinate system, the Laplacian is given by the sum of second partial derivatives of the function with respect to each independent variable. In other coordinate systems, such as cylindrical and spherical coordinates, the Laplacian also has a useful form. Informally, the Laplacian Δf (p) of a function f at a point p measures by how much the average value of f over small spheres or balls centered at p deviates from f (p).

    In vector calculus, the Jacobian matrix of a vector-valued function of several variables is the matrix of all its first-order partial derivatives. When this matrix is square, that is, when the function takes the same number of variables as input as the number of vector components of its output, its determinant is referred to as the Jacobian determinant. Both the matrix and the determinant are often referred to simply as the Jacobian in literature.

    In the mathematical field of differential geometry, a metric tensor is an additional structure on a manifold M that allows defining distances and angles, just as the inner product on a Euclidean space allows defining distances and angles there. More precisely, a metric tensor at a point p of M is a bilinear form defined on the tangent space at p, and a metric tensor on M consists of a metric tensor at each point p of M that varies smoothly with p.

    In mathematics, the covariant derivative is a way of specifying a derivative along tangent vectors of a manifold. Alternatively, the covariant derivative is a way of introducing and working with a connection on a manifold by means of a differential operator, to be contrasted with the approach given by a principal connection on the frame bundle – see affine connection. In the special case of a manifold isometrically embedded into a higher-dimensional Euclidean space, the covariant derivative can be viewed as the orthogonal projection of the Euclidean directional derivative onto the manifold's tangent space. In this case the Euclidean derivative is broken into two parts, the extrinsic normal component and the intrinsic covariant derivative component.

    In mathematics, more specifically in multivariable calculus, the implicit function theorem is a tool that allows relations to be converted to functions of several real variables. It does so by representing the relation as the graph of a function. There may not be a single function whose graph can represent the entire relation, but there may be such a function on a restriction of the domain of the relation. The implicit function theorem gives a sufficient condition to ensure that there is such a function.

    <span class="mw-page-title-main">Curvilinear coordinates</span> Coordinate system whose directions vary in space

    In geometry, curvilinear coordinates are a coordinate system for Euclidean space in which the coordinate lines may be curved. These coordinates may be derived from a set of Cartesian coordinates by using a transformation that is locally invertible at each point. This means that one can convert a point given in a Cartesian coordinate system to its curvilinear coordinates and back. The name curvilinear coordinates, coined by the French mathematician Lamé, derives from the fact that the coordinate surfaces of the curvilinear systems are curved.

    In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. For the case of a finite-dimensional graph, the discrete Laplace operator is more commonly called the Laplacian matrix.

    In differential geometry, the Laplace–Beltrami operator is a generalization of the Laplace operator to functions defined on submanifolds in Euclidean space and, even more generally, on Riemannian and pseudo-Riemannian manifolds. It is named after Pierre-Simon Laplace and Eugenio Beltrami.

    In mathematics, matrix calculus is a specialized notation for doing multivariable calculus, especially over spaces of matrices. It collects the various partial derivatives of a single function with respect to many variables, and/or of a multivariate function with respect to a single variable, into vectors and matrices that can be treated as single entities. This greatly simplifies operations such as finding the maximum or minimum of a multivariate function and solving systems of differential equations. The notation used here is commonly used in statistics and engineering, while the tensor index notation is preferred in physics.

    In mathematical optimization, the Karush–Kuhn–Tucker (KKT) conditions, also known as the Kuhn–Tucker conditions, are first derivative tests for a solution in nonlinear programming to be optimal, provided that some regularity conditions are satisfied.

    <span class="mw-page-title-main">Maxwell stress tensor</span>

    The Maxwell stress tensor is a symmetric second-order tensor used in classical electromagnetism to represent the interaction between electromagnetic forces and mechanical momentum. In simple situations, such as a point charge moving freely in a homogeneous magnetic field, it is easy to calculate the forces on the charge from the Lorentz force law. When the situation becomes more complicated, this ordinary procedure can become impractically difficult, with equations spanning multiple lines. It is therefore convenient to collect many of these terms in the Maxwell stress tensor, and to use tensor arithmetic to find the answer to the problem at hand.

    <span class="mw-page-title-main">Corner detection</span>

    Corner detection is an approach used within computer vision systems to extract certain kinds of features and infer the contents of an image. Corner detection is frequently used in motion detection, image registration, video tracking, image mosaicing, panorama stitching, 3D reconstruction and object recognition. Corner detection overlaps with the topic of interest point detection.

    In applied mathematics, polyharmonic splines are used for function approximation and data interpolation. They are very useful for interpolating and fitting scattered data in many dimensions. Special cases include thin plate splines and natural cubic splines in one dimension.

    In linear algebra, eigendecomposition is the factorization of a matrix into a canonical form, whereby the matrix is represented in terms of its eigenvalues and eigenvectors. Only diagonalizable matrices can be factorized in this way. When the matrix being factorized is a normal or real symmetric matrix, the decomposition is called "spectral decomposition", derived from the spectral theorem.