Polynomial matrix spectral factorization information
Polynomial matrices are widely studied in the fields of systems theory and control theory and have seen other uses relating to stable polynomials. In stability theory, Spectral Factorization has been used to find determinantal matrix representations for bivariate stable polynomials and real zero polynomials.[1] A key tool used to study these is a matrix factorization known as either the Polynomial Matrix Spectral Factorization or the Matrix Fejer–Riesz Theorem.
Given a univariate positive polynomial , a polynomial which takes on non-negative values for any real input , the Fejer–Riesz Theorem yields the polynomial spectral factorization . Results of this form are generically referred to as Positivstellensatz. Considering positive definiteness as the matrix analogue of positivity, Polynomial Matrix Spectral Factorization provides a similar factorization for polynomial matrices which have positive definite range. This decomposition also relates to the Cholesky decomposition for scalar matrices . This result was originally proven by Norbert Wiener[2] in a more general context which was concerned with integrable matrix-valued functions that also had integrable log determinant. Because applications are often concerned with the polynomial restriction, simpler proofs and individual analysis exist focusing on this case.[3] Weaker positivstellensatz conditions have been studied, specifically considering when the polynomial matrix has positive definite image on semi-algebraic subsets of the reals.[4] Many publications recently have focused on streamlining proofs for these related results.[5][6] This article roughly follows the recent proof method of Lasha Ephremidze[7] which relies only on elementary linear algebra and complex analysis.
Spectral Factorization is used extensively in linear–quadratic–Gaussian control. Because of this application there have been many algorithms to calculate spectral factors.[8] Some modern algorithms focus on the more general setting originally studied by Wiener.[9] In the case the problem is known as polynomial spectral factorization, or Fejer-Riesz Theorem, and has many classical algorithms. Some modern algorithms have used Toeplitz matrix advances to speed up factor calculations.[10]
^Anatolii Grinshpan, Dmitry S. Kaliuzhnyi-Verbovetskyir, Victor Vinnikov, Hugo J. Woerdeman (2016). "Stable and real-zero polynomials in two variables". Multidimensional Systems and Signal Processing. 27: 1–26. CiteSeerX 10.1.1.767.8178. doi:10.1007/s11045-014-0286-3. S2CID 254860436.{{cite journal}}: CS1 maint: multiple names: authors list (link)
^N. Wiener and P. Masani (1957). "The prediction theory of multivariate stochastic processe". Acta Math. 98: 111–150. doi:10.1007/BF02404472.
^Tim N.T. Goodman Charles A. Micchelli Giuseppe Rodriguez Sebastiano Seatzu (1997). "Spectral factorization of Laurent polynomials". Advances in Computational Mathematics. 7 (4): 429–454. doi:10.1023/A:1018915407202. S2CID 7880541.
^Aljaž Zalar (2016). "Matrix Fejér–Riesz theorem with gaps". Journal of Pure and Applied Algebra. 220 (7): 2533–2548. arXiv:1503.06034. doi:10.1016/j.jpaa.2015.11.018. S2CID 119303900.
^Zalar, Aljaž (2016-07-01). "Matrix Fejér–Riesz theorem with gaps". Journal of Pure and Applied Algebra. 220 (7): 2533–2548. arXiv:1503.06034. doi:10.1016/j.jpaa.2015.11.018. S2CID 119303900.
^Lasha Ephremidze (2009). "A Simple Proof of the Matrix-Valued Fejer–Riesz Theorem". Journal of Fourier Analysis and Applications. 15: 124–127. arXiv:0708.2179. CiteSeerX 10.1.1.247.3400. doi:10.1007/s00041-008-9051-z. S2CID 115163568. Retrieved 2017-05-23.
^Ephremidze, Lasha (2014). "An Elementary Proof of the Polynomial Matrix Spectral Factorization Theorem". Proceedings of the Royal Society of Edinburgh, Section A. 144 (4): 747–751. CiteSeerX 10.1.1.755.9575. doi:10.1017/S0308210512001552. S2CID 119125206.
^Thomas Kailath, A. H. Sayed (2001). "A survey of spectral factorization methods". Numerical Linear Algebra Techniques for Control and Signal Processing. 8 (6–7): 467–496. doi:10.1002/nla.250. S2CID 30631226.
^Gigla Janashia, Edem Lagvilava, Lasha Ephremidze (2011). "A New Method of Matrix Spectral Factorization". IEEE Transactions on Information Theory. 57 (4): 2318–2326. arXiv:0909.5361. doi:10.1109/TIT.2011.2112233. S2CID 3047050.{{cite journal}}: CS1 maint: multiple names: authors list (link)
^D.A. Bini, G. Fiorentino, L. Gemignani, B. Meini (2003). "Effective Fast Algorithms for Polynomial Spectral Factorization". Numerical Algorithms. 34 (2–4): 217–227. Bibcode:2003NuAlg..34..217B. doi:10.1023/B:NUMA.0000005364.00003.ea. S2CID 9800222.{{cite journal}}: CS1 maint: multiple names: authors list (link)
and 25 Related for: Polynomial matrix spectral factorization information
definiteness as the matrix analogue of positivity, PolynomialMatrixSpectralFactorization provides a similar factorization for polynomial matrices which...
linear algebra, eigendecomposition is the factorization of a matrix into a canonical form, whereby the matrix is represented in terms of its eigenvalues...
characteristic polynomial to zero. In spectral graph theory, the characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix. In...
The Chebyshev polynomials are two sequences of polynomials related to the cosine and sine functions, notated as T n ( x ) {\displaystyle T_{n}(x)} and...
analysis, a spectral theorem is a result about when a linear operator or matrix can be diagonalized (that is, represented as a diagonal matrix in some basis)...
multiplication operator by a trigonometric polynomial, compressed to a finite-dimensional space, can be represented by such a matrix. Similarly, one can represent...
decomposition or Cholesky factorization (pronounced /ʃəˈlɛski/ shə-LES-kee) is a decomposition of a Hermitian, positive-definite matrix into the product of...
square root may be used for any factorization of a positive semidefinite matrix A as BTB = A, as in the Cholesky factorization, even if BB ≠ A. This distinct...
from a p-variate Wishart distribution with scale matrix V and n degrees of freedom is the factorization: X = L A A T L T , {\displaystyle \mathbf {X} ={\textbf...
of a given matrix is numerically computed by the QR algorithm or its variants. In other words, the roots of the characteristic polynomial corresponding...
In mathematics, the Zernike polynomials are a sequence of polynomials that are orthogonal on the unit disk. Named after optical physicist Frits Zernike...
biadjacency matrix. A remarkable theorem of Kasteleyn states that the number of perfect matchings in a planar graph can be computed exactly in polynomial time...
sparse Cholesky, and other factorization methods) can be sufficient for meshes with a hundred thousand vertices. The matrix L {\displaystyle L} is usually...
representation. Such an approach is called a spectral method. Suppose we wish to compute the polynomial product c(x) = a(x) · b(x). The ordinary product...
the FFT as a recursive factorization of the polynomial z n − 1 {\displaystyle z^{n}-1} , here into real-coefficient polynomials of the form z m − 1 {\displaystyle...
inverse covariance matrix of x {\displaystyle \mathbf {x} } . The Tikhonov matrix is then given as a factorization of the matrix Q = Γ T Γ {\displaystyle...
offer a major advantage: the results of matrix arithmetic operations like matrix multiplication, factorization or inversion can be approximated in O (...
matrix RRQR factorization — rank-revealing QR factorization, can be used to compute rank of a matrix Polar decomposition — unitary matrix times positive-semidefinite...
ax + by = c Integer factorization: breaking an integer into its prime factors Congruence of squares Dixon's algorithm Fermat's factorization method General...
applications to cyclotomic polynomials (and their logarithms). The referenced article by Mousavi and Schmidt (2017) develops a factorization-theorem-like treatment...
… , v n − 1 ) {\displaystyle (v_{0},\ldots ,v_{n-1})} with a formal polynomial p v ( x ) = v 0 + v 1 x + v 2 x 2 + ⋯ + v n − 1 x n − 1 . {\displaystyle...
regions into which these curves subdivide the plane). In contrast with the polynomial-time recognition of planar graphs, it is NP-complete to determine whether...
The Herglotzian definition yields polynomials which may, if one wishes, be further factorized into a polynomial of z {\displaystyle z} and another of...
graph with a 1-factor. factorization A graph factorization is a partition of the edges of the graph into factors; a k-factorization is a partition into k-factors...