{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:14:20Z","timestamp":1767237260146},"reference-count":42,"publisher":"Cambridge University Press (CUP)","issue":"9","license":[{"start":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T00:00:00Z","timestamp":1558915200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2019,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The present paper uses spectral theory of linear operators to construct approximatelyminimal realizations of weighted languages. Our new contributions are: (i) a new algorithm for the singular value decomposition (SVD) decomposition of finite-rank infinite Hankel matrices based on their representation in terms of weighted automata, (ii) a new canonical form for weighted automata arising from the SVD of its corresponding Hankelmatrix, and (iii) an algorithmto construct approximateminimizations of given weighted automata by truncating the canonical form.We give bounds on the quality of our approximation.<\/jats:p>","DOI":"10.1017\/s0960129519000094","type":"journal-article","created":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T10:43:07Z","timestamp":1558953787000},"page":"1444-1478","source":"Crossref","is-referenced-by-count":5,"title":["Singular value automata and approximate minimization"],"prefix":"10.1017","volume":"29","author":[{"given":"Borja","family":"Balle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prakash","family":"Panangaden","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Doina","family":"Precup","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2019,5,27]]},"reference":[{"key":"S0960129519000094_ref40","first-page":"741","volume-title":"Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics,","author":"Siddiqi","year":"2010"},{"key":"S0960129519000094_ref39","doi-asserted-by":"publisher","DOI":"10.1137\/1037083"},{"key":"S0960129519000094_ref38","first-page":"289","volume-title":"Joint European Conference on Machine Learning and Knowledge Discovery in Databases","author":"Recasens","year":"2013"},{"key":"S0960129519000094_ref37","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-1236(03)00078-8"},{"key":"S0960129519000094_ref42","unstructured":"Zhu, K. (1990). Operator Theory in Function Spaces, vol. 138. American Mathematical Society."},{"key":"S0960129519000094_ref36","volume-title":"Hankel Operators and Their Applications.","author":"Peller","year":"2012"},{"key":"S0960129519000094_ref34","volume-title":"Handbook on Speech Processingand Speech Communication.","author":"Mohri","year":"2008"},{"key":"S0960129519000094_ref32","article-title":"Low-rank spectral learning with weighted loss functions","author":"Kulesza","year":"2015","journal-title":"Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics."},{"key":"S0960129519000094_ref31","first-page":"522","article-title":"Low-rank spectral learning. In:","author":"Kulesza","year":"2014","journal-title":"Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics,"},{"key":"S0960129519000094_ref41","author":"Trefethen","year":"1997"},{"key":"S0960129519000094_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23780-5_20"},{"key":"S0960129519000094_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2014.11.026"},{"key":"S0960129519000094_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01492-5_13"},{"key":"S0960129519000094_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01492-5_14"},{"key":"S0960129519000094_ref5","first-page":"147","article-title":"Quadratic weighted automata: Spectral algorithm and likelihood maximization. In:","author":"Bailly","year":"2011","journal-title":"Asian Conference on Machine Learning,"},{"key":"S0960129519000094_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-013-5416-x"},{"key":"S0960129519000094_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04081-8_12"},{"key":"S0960129519000094_ref29","first-page":"268","volume-title":"Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP), part II, vol 8573, LNCS","author":"Kiefer","year":"2014"},{"key":"S0960129519000094_ref1","first-page":"34","article-title":"Analytic properties of Schmidt pairs for a Hankel operator and the generalized Schur-Takagi problem","volume":"128","author":"Adamyan","year":"1971","journal-title":"Matematicheskii Sbornik"},{"key":"S0960129519000094_ref11","first-page":"1386","article-title":"Methods of moments for learning stochastic languages: Unified presentation and empirical comparison","author":"Balle","year":"2014","journal-title":"International Conference on Machine Learning,"},{"key":"S0960129519000094_ref12","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.70"},{"key":"S0960129519000094_ref14","volume-title":"Noncommutative Rational Series with Applications.","author":"Berstel","year":"2011"},{"key":"S0960129519000094_ref18","article-title":"Closing the learning-planning loop with predictive state representations","author":"Boots","year":"2009","journal-title":"Proceedings of Robotics: Science and Systems VI."},{"key":"S0960129519000094_ref35","volume-title":"Treatise on the Shift Operator: Spectral Function Theory,","volume":"273","author":"Nikol\u2019Skii","year":"2012"},{"key":"S0960129519000094_ref7","first-page":"800","article-title":"Unsupervised spectral learning of finite state transducers. In:","author":"Bailly","year":"2013","journal-title":"Advances in Neural Information Processing Systems,"},{"key":"S0960129519000094_ref8","first-page":"2159","article-title":"Spectral learning of general weighted automata via constrained matrix completion. In:","author":"Balle","year":"2012","journal-title":"Advances in neural information processingsystems,"},{"key":"S0960129519000094_ref26","unstructured":"Fuhrmann, P. A. (2011). A Polynomial Approach to Linear Algebra. Springer Science & Business Media."},{"key":"S0960129519000094_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01492-5_11"},{"key":"S0960129519000094_ref3","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718713"},{"key":"S0960129519000094_ref20","first-page":"529","volume-title":"Proceedings of the Symposium on Mathematical Theory of Automata,","author":"Brzozowski","year":"1962"},{"key":"S0960129519000094_ref6","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1145\/1553374.1553379","article-title":"Grammatical inference as a principal component analysis problem. In:","author":"Bailly","year":"2009","journal-title":"Proceedings of the 26th Annual International Conference on Machine Learning,"},{"key":"S0960129519000094_ref13","first-page":"1","article-title":"Bisimulation metrics for weighted finite automata","volume":"103","author":"Balle","year":"2017","journal-title":"Proceedings of the 44th International Colloquium On Automata Languages and Programming Warsaw,"},{"key":"S0960129519000094_ref15","first-page":"191","volume-title":"Logic, Language, Information and Computation\u201419th International Workshop, WoLLIC 2012, Buenos Aires, Argentina, September 3\u20136, 2012","author":"Bezhanishvili","year":"2012"},{"key":"S0960129519000094_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2011.12.002"},{"key":"S0960129519000094_ref21","doi-asserted-by":"publisher","DOI":"10.1162\/coli_a_00006"},{"key":"S0960129519000094_ref22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.2517-6161.1977.tb01600.x","article-title":"Maximum likelihood from incomplete data via the EM algorithm","volume":"39","author":"Dempster","year":"1977","journal-title":"Journal of the Royal Statistical Society: Series B (Methodological)"},{"key":"S0960129519000094_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.12.025"},{"key":"S0960129519000094_ref23","first-page":"41","article-title":"On rational stochastic languages","volume":"86","author":"Denis","year":"2008","journal-title":"Fundamenta Informaticae"},{"key":"S0960129519000094_ref17","doi-asserted-by":"publisher","DOI":"10.1145\/2490818"},{"key":"S0960129519000094_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00051-8"},{"key":"S0960129519000094_ref25","first-page":"127","article-title":"Model reduction with balanced realizations: An error bound and a frequency weighted generalization","volume":"23","author":"Enns","year":"1984","journal-title":"The 23rd IEEE Conference on Decision and Control, 1984,"},{"key":"S0960129519000094_ref27","doi-asserted-by":"publisher","DOI":"10.1080\/00207178408933239"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129519000094","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,18]],"date-time":"2024-07-18T18:04:12Z","timestamp":1721325852000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129519000094\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,27]]},"references-count":42,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["S0960129519000094"],"URL":"https:\/\/doi.org\/10.1017\/s0960129519000094","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,27]]}}}