Abstract
We describe a simple algorithm for estimating the elements of a matrix as well as its decomposition under the condition that only the product of this matrix with a vector is accessible. The algorithm is based on application of the stochastic simultaneous perturbation method. Theoretical results on the convergence of the proposed algorithm are proven. Numerical experiments are presented to show the efficiency of the proposed algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Anderson, T. W. (2003). An introduction to multivariate statistical analysis. London: Wiley-Interscience.
Arulampalam, M., Maskell, S., Gordon, N., & Clapp, T. (2002). A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking. IEEE Transactions on Signal Processing, 50(2), 174–188.
Bai, J., & Shi, S. (2011). Estimating high dimensional covariance matrices and its applications. Annals of Economics and Finances, 12–2, 199–215.
Beu, T. A. (2015). Introduction to numerical programming. Oxfordshire: Taylor and Francis Group.
Chicone, C. (2006). Ordinary differential equations with applications. New York: Springer.
Cooper, M., & Haines, K. (1996). Altimetric assimilation with water property conservation. Journal of Geophysical Research, 101, 1059–1077.
Daley, R. (1991). Atmospheric data analysis. New York: Cambridge University Press.
Del Moral, P. (1996). Non linear filtering: Interacting particle solution. Markov Processes and Related Fields, 2(4), 555–580.
Del Moral, P., Doucet, A., & Jasra, A. (2012). On adaptive resampling procedures for sequential Monte Carlo methods. Bernoulli, 18(1), 252–278.
Delijani, E. B., Pishvaie, M. R., & Boozarjomehry, R. B. (2014). Subsurface characterization with localized ensemble Kalman filter employing adaptive thresholding. Advances in Water Resources, 69, 181–196.
Ding, F., & Zhang, H. M. (2014). Gradient-based iterative algorithm for a class of the coupled matrix equations related to control systems. IET Control Theory and Applications, 8(15), 1588–1595.
El Karoui, N. (2008). Operator norm consistent estimation of large dimensional sparse covariance matrices. Annals of Statistics, 36, 2717–2756.
Evensen, G. (2007). Data assimilation: The ensemble Kalman filter. Berlin: Springer.
Fukumori, I., & Malanotte-Rizzoli, P. (1995). An approximate Kalman filter for ocean data assimilation: An example with an idealized Gulf Stream model. Journal of Geophysical Research, 100(C4), 6777–6793.
Golub, G. H., & van Loan, C. F. (1996). Matrix computations. Cambridge: Cambridge University Press.
Gordon, N. J., Salmond, D. J., & Smith, A. F. M. (1993). Novel approach to nonlinear/non-Gaussian Bayesian state estimation. IEE Proceedings of Radar and Signal Processing, F 140(2), 107–113. (ISSN 0956-375X).
Hoang, H. S., & Baraille, R. (2011). Prediction error sampling procedure based on dominant Schur decomposition. Application to state estimation in high dimensional oceanic model. Applied Mathematics and Computation, 218(7), 3689–3709.
Hoang, H. S., & Baraille, R. (2017a). On the efficient low cost procedure for estimation of high-dimensional prediction error covariance matrices. Automatica, 83, 317–330.
Hoang, H. S., & Baraille, R. (2017b). A comparison study on performance of an adaptive filter with other estimation methods for state estimation in high-dimensional system, chapter 2. In T. Hokimoto (Ed.), Advances in statistical methodologies and their application to real problems, Chapter 2 (pp. 29–52). Chennai: Intech.
Hoang, H. S., Baraille, R., & Talagrand, O. (2001). On the design of a stable adaptive filter for state estimation in high dimensional system. Automatica, 37, 341–359.
Jazwinski, A. H. (1970). Stochastic processes and filtering theory. New York: Academic.
Kailath, T. (1991). From Kalman filtering to innovations. In A. C. Antoulas (Ed.), Martingales, scattering and other nice things, mathematical system theory (pp. 55–88). Heidelberg: Springer.
Kivman, G. A. (2003). Sequential parameter estimation for stochastic systems. Nonlinear Processes in Geophysics, 10, 253–259.
Ledoit, O., & Wolf, M. (2004). A well-conditioned estimator for large-dimensional covariance matrices. Journal of Multivariate Analysis, 88(2), 365–411.
Levina, E., Rothman, A. J., & Zhu, J. (2007). Sparse estimation of large covariance matrices via a nested Lasso penalty. Annals of Applied Statistics, 2, 245–263.
Lorenz, E. N. (1963). Deterministic non-periodic flow. Journal of the Atmospheric Sciences, 20(2), 130–141.
Muirhead, R. (2005). Aspects of multivariate statistical theory. London: Wiley.
Musoff, H., & Zarchan, P. (2005). Fundamentals of Kalman filtering: A practical approach. Reston: American Institute of Aeronautics and Astronautics.
Pannekoucke, O., Berre, L., & Desroziers, G. (2008). Background-error correlation length-scale estimates and their sampling statistics. Quarterly Journal of the Royal Meteorological Society, 134(631), 497508.
Ristic, B., Arulampalam, S., & Gordon, N. (2004). Beyond the Kalman Filter: Particle filters for tracking applications. Norwood: Artech House.
Salimpour, Y., & Soltanian-Zadeh, H. (2009). Particle filtering of point processes observation with application on the modeling of visual cortex neural spiking activity. In 4th International IEEE/EMBS conference on neural engineering, NER09 (pp. 718–721).
Sewell, G. (1988). The numerical solution of ordinary and partial differential equations. London: Academic.
Simon, D. (2001). Kalman filtering. Embedded systems programming, 16(6), 72–79.
Spall, J. C. (2003). Introduction to stochastic search and optimization. New York: Wiley.
Stewart, G. W., & Sun, J. G. (1990). Matrix perturbation theory. Boston: Academic.
Talagrand, O., & Courtier, P. (1987). Variational assimilation of meteorological observations with the adjoint vorticity equation. I: Theory. Quarterly Journal of the Royal Meteorological Society, 113, 1311–1328.
Xie, L., Liu, Y. J., & Yang, H. Z. (2016). Gradient based and least squares based iterative algorithms for matrix equations \(AXB + CX^TD = F\). Applied Mathematics and Computation, 217(5), 2191–2199.
Zhang, H. M., & Ding, F. (2016). Iterative algorithms for \(X+A^TX^{-1}A=I \) by using the hierarchical identification principle. Journal of the Franklin Institute, 353(5), 1132–1146.
Zhang, H. M., & Yin, C. H. (2017). New proof of the gradient-based iterative algorithm for a complex conjugate and transpose matrix equation. Journal of the Franklin Institute, 354(16), 7585–7603.
Acknowledgements
The authors would like to thank the anonymous reviewers for their valuable comments and suggestions to improve the quality of the paper.
Author information
Authors and Affiliations
Corresponding author
Appendix A
Appendix A
The following definitions are given in Chicone (2006).
Definition A1
Equilibria for the system (2) (s.t \(w_k = 0\)) is the point X such that \(\phi (X) = X\).
Let ||X|| denote the Euclidean norm.
Definition A2
Let X be a critical point of the system (2).
-
(i)
The critical point X is stable if, for any \(\epsilon > 0\), there is a \(\delta > 0\), such that if a solution \(x = \psi _k\) satisfies \(||\psi _0 - X|| < \delta \), then \(||\psi _k - X|| < \epsilon , \forall k\).
-
(ii)
The critical point X is unstable if it is not stable as defined above.
-
(iii)
The critical point X is asymptotically stable if there exists a \(\delta > 0\) such that if a solution \(X = \psi _k\) satisfies \(||\psi _0 - x|| < \delta \), then \(\text{ lim }_{k \rightarrow \infty } \psi _k = X\).
Lemma A
(Theorem 1.25 in Chicone (2006)). Assume \(\phi (x)\) is a continuously differentiable function, and X an equilibrium solution of \(x_{k+1} = \phi (x_k)\) (see (2)). If all eigenvalues of \(\varPhi = \partial {\phi (X)}/{\partial {x}}\) are stable and there exist \(c > 0\) such that \(||\mu _k (X)|| \le c ||X||\) (for definition of \(\mu _k\) see below) then the system \(x_{k+1} = \phi (x_k)\) is asymptotically stable.
Proof of Theorem 4.1
By the conditions, \(\phi (x)\) is continuous differentiable function.
Introduce \(e_{k} := \hat{x}_k - x_k\). Subtracting Eq. (2) from Eq. (23) yields
Using the Taylor expansion \(\delta \varphi = \varPhi e_k + O(||e_k||^2)\), \(\delta h = H{\varPhi } e_k + O(||e_k||^2)\), the Eq. (31) can be represented as
It is seen that \(e_k = 0\) is an equilibrium point for F(x).
Consider the nonlinear system (32). If we linearize the system (32) around \(e_k = 0\) we have \(L_k\) as its transition matrix.
From Lemma A it implies that the filter is a.s if the linear system \(e_{k+1}^l = L_k e_k^l\) is a.s.
Using the results in Hoang et al. (2001) for the linear filtering problem, it is established that under the conditions of the Theorem, all the eigenvalues of \(L_k\) are stable hencet the present, he works as a research engineer on applied mathematics at the DOPS/HOM/REC of the Service Hydrographique et Océanographique de la Marine, France. His research interests lie in numerical methods for hyperbolic partial differential equations, oceanographic modelling, and data assimilation.
The linear system \(e_{k+1}^l = L_k e_k^l\) is a.s. It implies in its turn, by Lemma A, that the nonlinear filter (23) (24) (25) is a.s. \(\square \)
Rights and permissions
About this article
Cite this article
Hoang, H.S., Baraille, R. A simple numerical method based simultaneous stochastic perturbation for estimation of high dimensional matrices. Multidim Syst Sign Process 30, 195–217 (2019). https://doi.org/10.1007/s11045-018-0551-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11045-018-0551-y