Embedding properties of network realizations of dissipative reduced order models
Jörn Zimmerling, Mikhail Zaslavsky,Rob Remis, Shasri Moskow, Alexander Mamonov, Murthy Guddati,
Vladimir Druskin, and Liliana Borcea
Mathematical Sciences Department, Worcester Polytechnic Institute
https://www.wpi.edu/people/vdruskin
Abstract
Realizations of reduced order models of passive SISO or MIMO LTI problems can be transformed to tridiagonal and
blocktridiagonal forms, respectively, via dierent modications of the Lanczos algorithm. Generally, such realizations
can be interpreted as ladder resistorcapacitorinductor (RCL) networks. They gave rise to network syntheses in the
rst half of the 20th century that was at the base of modern electronics design and consecutively to MOR that
tremendously impacted many areas of engineering (electrical, mechanical, aerospace, etc.) by enabling ecient
compression of the underlining dynamical systems. In his seminal 1950s works Krein realized that in addition to
their compressing properties, network realizations can be used to embed the data back into the state space of the
underlying continuum problems.
In more recent works of the authors Krein's ideas gave rise to socalled nitedierence Gaussian quadrature rules
(FDGQR), allowing to approximately map the ROM statespace representation to its full order continuum counterpart
on a judicially chosen grid. Thus, the state variables can be accessed directly from the transfer function without
solving the full problem and even explicit knowledge of the PDE coecients in the interior, i.e., the FDGQR directly
learns" the problem from its transfer function. This embedding property found applications in PDE solvers, inverse
problems and unsupervised machine learning.
Here we show a generalization of this approach to dissipative PDE problems, e.g., electromagnetic and acoustic
wave propagation in lossy dispersive media. Potential applications include solution of inverse scattering problems in
dispersive media, such as seismic exploration, radars and sonars.
To x the idea, we consider a passive irreducible SISO ROM
fn(s) = Xn
j=1
yi
s + σj
, (62)
assuming that all complex terms in (62) come in conjugate pairs.
We will seek ladder realization of (62) as
rjuj + vj − vj−1 = −shˆjuj ,
uj+1 − uj + ˆrj vj = −shj vj ,
(63)
for j = 0, . . . , n with boundary conditions
un+1 = 0, v1 = −1,
and 4n real parameters hi, hˆi, ri and rˆi, i = 1, . . . , n, that can be considered, respectively, as the equivalent discrete
inductances, capacitors and also primary and dual conductors. Alternatively, they can be viewed as respectively
masses, spring stiness, primary and dual dampers of a mechanical string. Reordering variables would bring (63)
into tridiagonal form, so from the spectral measure given by (62 ) the coecients of (63) can be obtained via a
nonsymmetric Lanczos algorithm written in Jsymmetric form and fn(s) can be equivalently computed as
fn(s) = u1.
The cases considered in the original FDGQR correspond to either (i) real y, θ or (ii) real y and imaginary θ. Both
cases are covered by the Stieltjes theorem, that yields in case (i) real positive h, hˆ and trivial r, rˆ, and in case (ii) real
positive h,r and trivial hˆ,rˆ. This result allowed us a simple interpretation of (62) as the staggered nitedierence
approximation of the underlying PDE problem [2]. For PDEs in more than one variables (including topologically rich
datamanifolds), a nitedierence interpretation is obtained via a MIMO extensions in block form, e.g., [4, 3].
The main diculty of extending this approach to general passive problems is that the Stieltjes theory is no longer
applicable. Moreover, the tridiagonal realization of a passive ROM transfer function (62) via the ladder network (63)
cannot always be obtained in portHamiltonian form, i.e., the equivalent primary and dual conductors may change
sign [1].
100
Embedding of the Stieltjes problems, e.g., the case (i) was done by mapping h and hˆ into values of acoustic (or
electromagnetic) impedance at grid cells, that required a special coordinate stretching (known as travel time coordinate transform) for continuous problems. Likewise, to circumvent possible nonpositivity of conductors for the
nonStieltjes case, we introduce an additional complex sdependent coordinate stretching, vanishing as s → ∞ [1].
This stretching applied in the discrete setting induces a diagonal factorization, removes oscillating coecients, and
leads to an accurate embedding for moderate variations of the coecients of the continuum problems, i.e., it maps
discrete coecients onto the values of their continuum counterparts.
Not only does this embedding yields an approximate linear algebraic algorithm for the solution of the inverse problems
for dissipative PDEs, it also leads to new insight into the properties of their ROM realizations. We will also discuss
another approach to embedding, based on KreinNudelman theory [5], that results in special datadriven adaptive
grids.
References
[1] Borcea, Liliana and Druskin, Vladimir and Zimmerling, Jörn, A reduced order model approach to
inverse scattering in lossy layered media, Journal of Scientic Computing, V. 89, N1, pp. 136,2021
[2] Druskin, Vladimir and Knizhnerman, Leonid, Gaussian spectral rules for the threepoint second dierences:
I. A twopoint positive denite problem in a semiinnite domain, SIAM Journal on Numerical Analysis, V. 37,
N 2, pp.403422, 1999
[3] Druskin, Vladimir and Mamonov, Alexander V and Zaslavsky, Mikhail, Distance preserving model
order reduction of graphLaplacians and cluster analysis, Druskin, Vladimir and Mamonov, Alexander V
and Zaslavsky, Mikhail, Journal of Scientic Computing, V. 90, N 1, pp 130, 2022
[4] Druskin, Vladimir and Moskow, Shari and Zaslavsky, Mikhail LippmannSchwingerLanczos algorithm
for inverse scattering problems, Inverse Problems, V. 37, N. 7, 2021,
[5] Mark Adolfovich Nudelman The Krein String and Characteristic Functions of Maximal Dissipative Operators, Journal of Mathematical Sciences, 2004, V 124, pp 49184934
Go back to Plenary Speakers Go back to Speakers Go back
more »
« less
Almost Optimal Scaling of ReedMuller Codes on BEC and BSC Channels
Consider a binary linear code of length N, minimum
distance dmin, transmission over the binary erasure channel
with parameter 0 < < 1 or the binary symmetric channel with
parameter 0 < < 1
2
, and blockMAP decoding. It was shown
by Tillich and Zemor that in this case the error probability of
the blockMAP decoder transitions “quickly” from δ to 1−δ for
any δ > 0 if the minimum distance is large. In particular the
width of the transition is of order O(1/
√
dmin). We strengthen this
result by showing that under suitable conditions on the weight
distribution of the code, the transition width can be as small as
Θ(1/N 1
2 −κ
), for any κ > 0, even if the minimum distance of the
code is not linear. This condition applies e.g., to ReedMueller
codes. Since Θ(1/N 1
2 ) is the smallest transition possible for any
code, we speak of “almost” optimal scaling. We emphasize that
the width of the transition says nothing about the location of
the transition. Therefore this result has no bearing on whether a
code is capacityachieving or not. As a second contribution, we
present a new estimate on the derivative of the EXIT function,
the proof of which is based on the BlowingUp Lemma.
more »
« less
 NSFPAR ID:
 10063530
 Date Published:
 Journal Name:
 2018 IEEE Int. Symp. Inf. Theory (ISIT)
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Braverman, Mark (Ed.)For an abelian group H acting on the set [𝓁], an (H,𝓁)lift of a graph G₀ is a graph obtained by replacing each vertex by 𝓁 copies, and each edge by a matching corresponding to the action of an element of H. Expanding graphs obtained via abelian lifts, form a key ingredient in the recent breakthrough constructions of quantum LDPC codes, (implicitly) in the fiber bundle codes by Hastings, Haah and O'Donnell [STOC 2021] achieving distance Ω̃(N^{3/5}), and in those by Panteleev and Kalachev [IEEE Trans. Inf. Theory 2021] of distance Ω(N/log(N)). However, both these constructions are nonexplicit. In particular, the latter relies on a randomized construction of expander graphs via abelian lifts by Agarwal et al. [SIAM J. Discrete Math 2019]. In this work, we show the following explicit constructions of expanders obtained via abelian lifts. For every (transitive) abelian group H ⩽ Sym(𝓁), constant degree d ≥ 3 and ε > 0, we construct explicit dregular expander graphs G obtained from an (H,𝓁)lift of a (suitable) base nvertex expander G₀ with the following parameters: ii) λ(G) ≤ 2√{d1} + ε, for any lift size 𝓁 ≤ 2^{n^{δ}} where δ = δ(d,ε), iii) λ(G) ≤ ε ⋅ d, for any lift size 𝓁 ≤ 2^{n^{δ₀}} for a fixed δ₀ > 0, when d ≥ d₀(ε), or iv) λ(G) ≤ Õ(√d), for lift size "exactly" 𝓁 = 2^{Θ(n)}. As corollaries, we obtain explicit quantum lifted product codes of Panteleev and Kalachev of almost linear distance (and also in a wide range of parameters) and explicit classical quasicyclic LDPC codes with wide range of circulant sizes. Items (i) and (ii) above are obtained by extending the techniques of Mohanty, O'Donnell and Paredes [STOC 2020] for 2lifts to much larger abelian lift sizes (as a byproduct simplifying their construction). This is done by providing a new encoding of special walks arising in the trace power method, carefully "compressing" depthfirst search traversals. Result (iii) is via a simpler proof of Agarwal et al. [SIAM J. Discrete Math 2019] at the expense of polylog factors in the expansion.more » « less

Braverman, Mark (Ed.)A longstanding open problem in coding theory is to determine the best (asymptotic) rate R₂(δ) of binary codes with minimum constant (relative) distance δ. An existential lower bound was given by Gilbert and Varshamov in the 1950s. On the impossibility side, in the 1970s McEliece, Rodemich, Rumsey and Welch (MRRW) proved an upper bound by analyzing Delsarte’s linear programs. To date these results remain the best known lower and upper bounds on R₂(δ) with no improvement even for the important class of linear codes. Asymptotically, these bounds differ by an exponential factor in the blocklength. In this work, we introduce a new hierarchy of linear programs (LPs) that converges to the true size A^{Lin}₂(n,d) of an optimum linear binary code (in fact, over any finite field) of a given blocklength n and distance d. This hierarchy has several notable features: 1) It is a natural generalization of the Delsarte LPs used in the first MRRW bound. 2) It is a hierarchy of linear programs rather than semidefinite programs potentially making it more amenable to theoretical analysis. 3) It is complete in the sense that the optimum code size can be retrieved from level O(n²). 4) It provides an answer in the form of a hierarchy (in larger dimensional spaces) to the question of how to cut Delsarte’s LP polytopes to approximate the true size of linear codes. We obtain our hierarchy by generalizing the Krawtchouk polynomials and MacWilliams inequalities to a suitable "higherorder" version taking into account interactions of 𝓁 words. Our method also generalizes to translation schemes under mild assumptions.more » « less


null (Ed.)The GilbertVarshamov bound (nonconstructively) establishes the existence of binary codes of distance 1/2ε and rate Ω(ε 2 ) (where an upper bound of O(ε 2 log(1/ε)) is known). TaShma [STOC 2017] gave an explicit construction of εbalanced binary codes, where any two distinct codewords are at a distance between 1/2ε/2 and 1/2+ε/2, achieving a near optimal rate of Ω(ε 2+β ), where β→ 0 as ε→ 0. We develop unique and list decoding algorithms for (a slight modification of) the family of codes constructed by TaShma, in the adversarial error model. We prove the following results for εbalanced codes with block length N and rate Ω(ε 2+β ) in this family: For all , there are explicit codes which can be uniquely decoded up to an error of half the minimum distance in time N Oε,β(1) . For any fixed constant β independent of ε, there is an explicit construction of codes which can be uniquely decoded up to an error of half the minimum distance in time (log(1/ε)) O(1) ·N Oβ(1) . For any , there are explicit εbalanced codes with rate Ω(ε 2+β ) which can be list decoded up to error 1/2ε ' in time N Oε,ε' ,β(1), where ε ' ,β→ 0 as ε→ 0. The starting point of our algorithms is the framework for list decoding directsum codes develop in Alev et al. [SODA 2020], which uses the SumofSquares SDP hierarchy. The rates obtained there were quasipolynomial in ε. Here, we show how to overcome the far from optimal rates of this framework obtaining unique decoding algorithms for explicit binary codes of near optimal rate. These codes are based on simple modifications of TaShma's construction.more » « less