IDEAS home Printed from https://ideas.repec.org/a/taf/tsysxx/v46y2015i11p2029-2047.html
   My bibliography  Save this article

Optimal Kullback–Leibler approximation of Markov chains via nuclear norm regularisation

Author

Listed:
  • Kun Deng
  • Dayu Huang

Abstract

This paper is concerned with model reduction for Markov chain models. The goal is to obtain a low-rank approximation to the original Markov chain. The Kullback–Leibler divergence rate is used to measure the similarity between two Markov chains; the nuclear norm is used to approximate the rank function. A nuclear-norm regularised optimisation problem is formulated to approximately find the optimal low-rank approximation. The proposed regularised problem is analysed and performance bounds are obtained through the convex analysis. An iterative fixed point algorithm is developed based on the proximal splitting technique to compute the optimal solutions. The effectiveness of this approach is illustrated via numerical examples.

Suggested Citation

  • Kun Deng & Dayu Huang, 2015. "Optimal Kullback–Leibler approximation of Markov chains via nuclear norm regularisation," International Journal of Systems Science, Taylor & Francis Journals, vol. 46(11), pages 2029-2047, August.
    • Handle: RePEc:taf:tsysxx:v:46:y:2015:i:11:p:2029-2047
    DOI: 10.1080/00207721.2013.844284
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1080/00207721.2013.844284
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1080/00207721.2013.844284?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Z. Kowalczuk & M. Domżalski, 2012. "Optimal asynchronous estimation of 2D Gaussian–Markov processes," International Journal of Systems Science, Taylor & Francis Journals, vol. 43(8), pages 1431-1440.
    2. Patrick L. Combettes & Jean-Christophe Pesquet, 2011. "Proximal Splitting Methods in Signal Processing," Springer Optimization and Its Applications, in: Heinz H. Bauschke & Regina S. Burachik & Patrick L. Combettes & Veit Elser & D. Russell Luke & Henry (ed.), Fixed-Point Algorithms for Inverse Problems in Science and Engineering, chapter 0, pages 185-212, Springer.
    3. Alexander Brownlee & Olivier Regnier-Coudert & John McCall & Stewart Massie & Stefan Stulajter, 2013. "An application of a GA with Markov network surrogate to feature selection," International Journal of Systems Science, Taylor & Francis Journals, vol. 44(11), pages 2039-2056.
    4. Carl Eckart & Gale Young, 1936. "The approximation of one matrix by another of lower rank," Psychometrika, Springer;The Psychometric Society, vol. 1(3), pages 211-218, September.
    5. Guoying Miao & Shengyuan Xu & Yun Zou, 2013. "Necessary and sufficient conditions for mean square consensus under Markov switching topologies," International Journal of Systems Science, Taylor & Francis Journals, vol. 44(1), pages 178-186.
    6. Hua Han & Yongsheng Ding & Kuangrong Hao & Liangjian Hu, 2013. "Particle filter for state estimation of jump Markov nonlinear system with application to multi-targets tracking," International Journal of Systems Science, Taylor & Francis Journals, vol. 44(7), pages 1333-1343.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Sewell, Daniel K., 2018. "Visualizing data through curvilinear representations of matrices," Computational Statistics & Data Analysis, Elsevier, vol. 128(C), pages 255-270.
    2. Guillaume Sagnol & Edouard Pauwels, 2019. "An unexpected connection between Bayes A-optimal designs and the group lasso," Statistical Papers, Springer, vol. 60(2), pages 565-584, April.
    3. Kohei Adachi & Nickolay T. Trendafilov, 2016. "Sparse principal component analysis subject to prespecified cardinality of loadings," Computational Statistics, Springer, vol. 31(4), pages 1403-1427, December.
    4. Ernest K. Ryu & Yanli Liu & Wotao Yin, 2019. "Douglas–Rachford splitting and ADMM for pathological convex optimization," Computational Optimization and Applications, Springer, vol. 74(3), pages 747-778, December.
    5. Junhong Lin & Lorenzo Rosasco & Silvia Villa & Ding-Xuan Zhou, 2018. "Modified Fejér sequences and applications," Computational Optimization and Applications, Springer, vol. 71(1), pages 95-113, September.
    6. Weiyang Ding & Michael K. Ng & Wenxing Zhang, 2024. "A generalized alternating direction implicit method for consensus optimization: application to distributed sparse logistic regression," Journal of Global Optimization, Springer, vol. 90(3), pages 727-753, November.
    7. Norman Cliff, 1962. "Analytic rotation to a functional relationship," Psychometrika, Springer;The Psychometric Society, vol. 27(3), pages 283-295, September.
    8. Jushan Bai & Serena Ng, 2020. "Simpler Proofs for Approximate Factor Models of Large Dimensions," Papers 2008.00254, arXiv.org.
    9. Adele Ravagnani & Fabrizio Lillo & Paola Deriu & Piero Mazzarisi & Francesca Medda & Antonio Russo, 2024. "Dimensionality reduction techniques to support insider trading detection," Papers 2403.00707, arXiv.org, revised May 2024.
    10. Alfredo García-Hiernaux & José Casals & Miguel Jerez, 2012. "Estimating the system order by subspace methods," Computational Statistics, Springer, vol. 27(3), pages 411-425, September.
    11. Silvia Bonettini & Peter Ochs & Marco Prato & Simone Rebegoldi, 2023. "An abstract convergence framework with application to inertial inexact forward–backward methods," Computational Optimization and Applications, Springer, vol. 84(2), pages 319-362, March.
    12. Puya Latafat & Panagiotis Patrinos, 2017. "Asymmetric forward–backward–adjoint splitting for solving monotone inclusions involving three operators," Computational Optimization and Applications, Springer, vol. 68(1), pages 57-93, September.
    13. Sedi Bartz & Rubén Campoy & Hung M. Phan, 2022. "An Adaptive Alternating Direction Method of Multipliers," Journal of Optimization Theory and Applications, Springer, vol. 195(3), pages 1019-1055, December.
    14. Mitzi Cubilla‐Montilla & Ana‐Belén Nieto‐Librero & Ma Purificación Galindo‐Villardón & Ma Purificación Vicente Galindo & Isabel‐María Garcia‐Sanchez, 2019. "Are cultural values sufficient to improve stakeholder engagement human and labour rights issues?," Corporate Social Responsibility and Environmental Management, John Wiley & Sons, vol. 26(4), pages 938-955, July.
    15. Stegeman, Alwin, 2016. "A new method for simultaneous estimation of the factor model parameters, factor scores, and unique parts," Computational Statistics & Data Analysis, Elsevier, vol. 99(C), pages 189-203.
    16. Jos Berge & Henk Kiers, 1993. "An alternating least squares method for the weighted approximation of a symmetric matrix," Psychometrika, Springer;The Psychometric Society, vol. 58(1), pages 115-118, March.
    17. Shimeng Huang & Henry Wolkowicz, 2018. "Low-rank matrix completion using nuclear norm minimization and facial reduction," Journal of Global Optimization, Springer, vol. 72(1), pages 5-26, September.
    18. Antti J. Tanskanen & Jani Lukkarinen & Kari Vatanen, 2016. "Random selection of factors preserves the correlation structure in a linear factor model to a high degree," Papers 1604.05896, arXiv.org, revised Dec 2018.
    19. Ali Habibnia & Esfandiar Maasoumi, 2021. "Forecasting in Big Data Environments: An Adaptable and Automated Shrinkage Estimation of Neural Networks (AAShNet)," Journal of Quantitative Economics, Springer;The Indian Econometric Society (TIES), vol. 19(1), pages 363-381, December.
    20. Gui-Hua Lin & Zhen-Ping Yang & Hai-An Yin & Jin Zhang, 2023. "A dual-based stochastic inexact algorithm for a class of stochastic nonsmooth convex composite problems," Computational Optimization and Applications, Springer, vol. 86(2), pages 669-710, November.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:taf:tsysxx:v:46:y:2015:i:11:p:2029-2047. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Longhurst (email available below). General contact details of provider: http://www.tandfonline.com/TSYS20 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.