

{"id":106,"date":"2016-09-30T23:12:21","date_gmt":"2016-09-30T21:12:21","guid":{"rendered":"https:\/\/project.inria.fr\/rarl2\/?page_id=106"},"modified":"2017-01-22T19:34:57","modified_gmt":"2017-01-22T18:34:57","slug":"algorithms","status":"publish","type":"page","link":"https:\/\/project.inria.fr\/rarl2\/algorithms\/","title":{"rendered":"Algorithms"},"content":{"rendered":"<h3>Rational H2 approximation<\/h3>\n<p> Given a matrix-valued function <span style=\"position: relative; top: 0.15em;\">\\(F(z)\\)<\/span> whose entries are \u00a0assumed to be in the <em>Hardy space<\/em> <sup>1<\/sup> \\(H^2\\) and a positive integer <em>n<\/em>, the problem is to find a <em>stable<\/em><sup>2<\/sup> rational matrix <span style=\"position: relative; top: 0.15em;\">\\(H(z)\\)<\/span> of <em>McMillan degree<\/em><sup>3<\/sup> at most  n  which minimizes the \\(L^2\\) norm<\/p>\n<p><center>\\( \\|F-H\\|_2^2=\\frac{1}{2\\pi} {\\rm Tr} \\int_0^{2\\pi}(F-H)(e^{it}) {(F-H)(e^{it})}^*dt.\\)<\/center>It is known [1] that a global minimum does exist and has exact degree <em>n<\/em> unless <span style=\"position: relative; top: 0.15em;\">\\(F(z)\\)<\/span> is of lower degree. Moreover, if <span style=\"position: relative; top: 0.15em;\">\\(F(z)\\)<\/span> has degree n, then the only critical point of the criterion is <span style=\"position: relative; top: 0.15em;\">\\(F(z)\\)<\/span> itself [2]. The approach used in RARL2 was first developped for scalar functions [3] and then in the matrix case [4].<\/p>\n<p> 1. <em> Hardy spaces<\/em>: the space \\( L^2 \\) of square integrable functions on the unit disk splits into two orthogonal subspaces: the space \\(H^2\\) of \\(L^2\\) functions having an analytic continuation in the unit disk (negative Fourier coefficients are zero) and the space \\(H_-^2\\) of \\(L^2\\) functions having an analytic continuation outside the unit disk and vanishing at infinity (non-negative Fourier coefficients are zero)<\/p>\n<p> 2.  <em> stable<\/em>: poles inside the unit disk<\/p>\n<p> 3.  <em>McMillan degree<\/em>: size of the A-matrix in a minimal realization\/ number of poles counting multiplicity<\/p>\n<h3>Reduction of the optimization space<\/h3>\n<p> We use a special matrix fraction description known has Douglas-Shapiro-Shields factorization, and write a rational matrix of degree n as<\/p>\n<p><center>\\(H= G C\\)<\/center>where <span style=\"position: relative; top: 0.15em;\">\\(G(z)\\)<\/span> is a <em>lossless matrix<\/em><sup>4<\/sup>, of same McMillan degree than <span style=\"position: relative; top: 0.15em;\">\\(H(z)\\)<\/span>, and <span style=\"position: relative; top: 0.15em;\">\\(C(z)\\)<\/span> is an anti-stable matrix.<\/p>\n<ul>\n<li><span style=\"position: relative; top: 0.15em;\">\\(H(z)\\)<\/span> and <span style=\"position: relative; top: 0.15em;\">\\(G(z)\\)<\/span>: same observable pair <span style=\"position: relative; top: 0.15em;\">\\((C,A)\\)<\/span><\/li>\n<li><span style=\"position: relative; top: 0.15em;\">\\(G(z)\\)<\/span> and <span style=\"position: relative; top: 0.15em;\">\\((C,A)\\)<\/span> bring the (left) pole structure<\/li>\n<li> unique up to a unitary matrix <\/li>\n<li>right generalization of an irreducible rational fraction<\/li>\n<\/ul>\n<p><!-- <span style=\"position:relative; top:0.15em;\">[latex size=1]G(z)[\/latex]<\/span> brings the information on the poles of <span style=\"position:relative; top:0.15em;\">[latex size=1]H(z)[\/latex]<\/span> (generalized denominator) while <span style=\"position:relative; top:0.15em;\">[latex size=1]C(z)[\/latex]<\/span> brings the information on its zeros. --><\/p>\n<p>By the <strong> Hilbert projection theorem <\/strong>, at a local minimum <span style=\"position: relative; top: 0.15em;\">\\(H(z)\\)<\/span> of the criterion, <span style=\"position: relative; top: 0.15em;\">\\(C(z)\\)<\/span> has to be the projection \\(P^+\\) of \\(G^{-1}F\\) onto \\(H^2\\). The approximation problem reduces to the minimization of a concentrated criterion [4,5]<\/p>\n<p><center>\\( G \\mapsto \\|F-G\\,P^+(G^{-1}F)\\|^2\\)<\/center><br \/>\nover the (quotient) set of <strong>lossless matrices of McMillan degree n <\/strong> up to a right unitary matrix.<\/p>\n<p> <strong>Advantage: minimization over a bounded set<\/strong><\/p>\n<p>4. lossless matrix: rationnal matrix analytic outside the unit disk which takes unitary values on the circle.<\/p>\n<h3> State-space formulas <\/h3>\n<p>In practice, the concentrated criterion is computed using balanced realizations<sup>5<\/sup> to represent lossless matrix functions. We have the nice following property<br \/>\n<center>  \\(\\left\\{\\begin{array}{cl}<br \/>\nD+C(zI-A)^{-1}B &#038;\\hbox{ lossless }\\\\<br \/>\n(A,B,C,D) &#038;\\hbox{ balanced }\\end{array}\\right. \\Leftrightarrow \\begin{bmatrix} D &#038; C \\\\<br \/>\nB &#038; A \\end{bmatrix} \\hbox{ unitary }\\) <\/center><\/p>\n<ul>\n<li> Write the state-space realization of <span style=\"position: relative; top: 0.2em;\">\\(F(z)\\)<\/span> and <span style=\"position: relative; top: 0.2em;\">\\(H(z)\\)<\/span>.<br \/>\n<center>\\(F(z)= {\\cal C} (zI- {\\cal A})^{-1} {\\cal B}~~~ H(z)={C}(zI-{ A})^{-1}{\\hat B}\\) <\/center><br \/>\nwhere the pair <span style=\"position: relative; top: 0.2em;\">\\((C,A)\\)<\/span> is assumed <strong> output normal <\/strong>: <span style=\"position: relative; top: 0.2em;\">\\(A^*A+C^*C=I\\)<\/span><\/li>\n<li> The Hilbert projection property translates into the classical necessary conditions for optimality<br \/>\n<center>\\({\\hat B}=-{\\cal Q}^*{\\cal B}~~~ \\hbox{ where }~~~ {\\cal A}^*  {\\cal Q} A +{\\cal C}^* C= {\\cal Q}. \\)<\/center><\/li>\n<li> The concentrated criterion becomes<br \/>\n<center>  \\(J(A,C)=\\|F\\|_2^2-\\hbox{Tr}({\\cal B}^* {\\cal Q}{\\cal Q}^* {\\cal B})\\)<\/center><br \/>\ndefined over the set of equivalence classes under similarity of <strong> balanced output pairs (BOP) <\/strong>.\n<\/li>\n<\/ul>\n<p><strong>Advantage: computation with unitary matrices <\/strong><\/p>\n<p>5. A <em> balanced realization<\/em> is such that both grammians are equal and diagonal<\/p>\n<h3>Parametrization of the optimization space<\/h3>\n<p>The optimization space has a manifold structure [6]. We use an atlas of charts, like for the earth, where each chart provides a local flat (Euclidien) representation which allows for the use of differential tools. In the actual version of RARL2, we use the atlas presented in [7], called <em> lossless mutual encoding <\/em><\/p>\n<ul>\n<li> A chart is indexed by a lossless matrix\/unitary realization <span style=\"position:relative; top:0.2em;\">\\( (W,X,Y,Z) \\)<\/span><\/li>\n<li> A BOP, given by a unitary realization <span style=\"position:relative; top:0.2em;\">\\((A,B,C,D)\\)<\/span> can be parametrized in this chart iff the solution <span style=\"position:relative; top:0.2em;\">\\( \\Sigma \\)<\/span> to<br \/>\n<center>\\(\\Sigma &#8211; A^* \\Sigma W = C^* Y \\) <\/center><br \/>\nis positive definite. <\/li>\n<li> The BOP is represented in the chart by the parameters matrix<br \/>\n<center>\\( V= D^*Y+B^*\\Sigma W \\)<\/center>\n<\/li>\n<\/ul>\n<p><strong> Advantage: use of differential tools safe <\/strong><\/p>\n<h3>Optimization over a manifold<\/h3>\n<p>In RARL2, the minimization process makes use of the Matlab solver <strong>fmincon<\/strong>.<br \/>\nThe optimization is carried over the manifold structure as illustrated below:<br \/>\n<center><a href=\"https:\/\/project.inria.fr\/rarl2\/files\/2016\/09\/manifold.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/project.inria.fr\/rarl2\/files\/2016\/09\/manifold.png\" alt=\"manifold\" width=\"357\" height=\"154\" \/><\/a><\/center><\/p>\n<ul>\n<li> Initialization: <span style=\"position: relative; top: 0.2em;\">\\(G_0(z)\\equiv (A_0,B_0,C_0,D_0)\\)<\/span> computed by balanced truncation [Kun, Lin, 1981]\n<\/li>\n<li> Optimization with respect to the local coordinates \\(V\\) using  fmincon\n<\/li>\n<li> Change of chart handled by a non-linear constraint:<br \/>\n<center>\\(\\mbox{min eig} ~\\Sigma \\leq \\epsilon  \\rightsquigarrow \\mbox{change chart}\\)<\/center>\n<\/li>\n<li> Changing chart is easy: adapted chart at <span style=\"position: relative; top: 0.2em;\">\\(G(z):~ V=0\\)<\/span><br \/>\n<h3> References <\/h3>\n<p>[1] L. Baratchart, Existence and generic properties for L2 approximants of linear systems <i> I.M.A. Journal of Math. Control and Identification<\/i> 3, 89-101 (1986)<\/p>\n<p>[2]L. Baratchart and M. Olivi <a href=\"http:\/\/www-sop.inria.fr\/members\/Martine.Olivi\/Papiers\/rapportcons.pdf\"> Critical points and error rank in matrix H2 rational approximation and the strong differential consistency of output error identification from white noise inputs<\/a><i>Constructive Approximation <\/i>14, pp. 273-300 (1998)<\/p>\n<p>[3] L. Baratchart, M. Cardelli, M. Olivi, Identification and rational L2 approximation: a gradient algorithm, <i> Automatica<\/i> 27(2) 413-418 (1991)<\/p>\n<p>[4] P. Fulcheri and M. Olivi <a href=\"http:\/\/www-sop.inria.fr\/members\/Martine.Olivi\/Papiers\/FO.pdf\"> Matrix rational H2 approximation: a gradient algorithm based on Schur analysis <\/a> <i>SIAM Journal on Control and Optimization<\/i> Vol. 36, No. 6, 2103-2127(1998)<\/p>\n<p>[5] M. Olivi, F. Seyfert, J.P. Marmorat, <a href=\" http:\/\/www-sop.inria.fr\/members\/Martine.Olivi\/Papiers\/AUTO_MOSfinal.pdf\"> Identication of microwave filters by analytic and rational H<sup>2<\/sup>approximation, <\/a><i>Automatica, <\/i> 49, 317-325(2013)<\/p>\n<p>[6] D. Alpay, L. Baratchart, A. Gombani, On the differential structure of matrix-valued rational inner functions, <i>Operator Theory: Advances and Applications, <\/i> 73, 30&#8211;66(1994)<\/p>\n<p>[7] J.P. Marmorat, M. Olivi, <a href=\" http:\/\/www-sop.inria.fr\/members\/Martine.Olivi\/Papiers\/Nudelman_r2.pdf\"> Nudelman Interpolation, Parametrization of Lossless Functions and balanced realizations, <\/a><i>Automatica, <\/i> 43 , 1329-1338(2007)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Rational H2 approximation Given a matrix-valued function whose entries are \u00a0assumed to be in the Hardy space 1 and a positive integer n, the problem is to find a stable2 rational matrix of McMillan degree3 at most n which minimizes the norm It is known [1] that a global minimum\u2026<\/p>\n<p> <a class=\"continue-reading-link\" href=\"https:\/\/project.inria.fr\/rarl2\/algorithms\/\"><span>Continue reading<\/span><i class=\"crycon-right-dir\"><\/i><\/a> <\/p>\n","protected":false},"author":40,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":"","_members_access_role":[],"_members_access_error":""},"class_list":["post-106","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/project.inria.fr\/rarl2\/wp-json\/wp\/v2\/pages\/106","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/project.inria.fr\/rarl2\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/project.inria.fr\/rarl2\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/project.inria.fr\/rarl2\/wp-json\/wp\/v2\/users\/40"}],"replies":[{"embeddable":true,"href":"https:\/\/project.inria.fr\/rarl2\/wp-json\/wp\/v2\/comments?post=106"}],"version-history":[{"count":153,"href":"https:\/\/project.inria.fr\/rarl2\/wp-json\/wp\/v2\/pages\/106\/revisions"}],"predecessor-version":[{"id":359,"href":"https:\/\/project.inria.fr\/rarl2\/wp-json\/wp\/v2\/pages\/106\/revisions\/359"}],"wp:attachment":[{"href":"https:\/\/project.inria.fr\/rarl2\/wp-json\/wp\/v2\/media?parent=106"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}