Some inverse problems on finite networks

PROGRAMA DE DOCTORADO EN MATEM ´ ATICAS TESIS DOCTORAL: SOME INVERSE PROBLEMS ON FINITE NETWORKS Presentada por ´ Alvaro Samperio Valdivieso para optar al grado de Doctor/a por la Universidad de Valladolid Dirigida por: Dr. Antonio Campillo L´opez Dr. Andr´es Marcos Encinas Bachiller Funding •Supported by a FPI grant of the Research Project PGC2018-096446-BC21 (with the help of the FEDER Program). •Partially supported by the project PID2022-138906NB-C21 funded by MICIU/AEI/ 10.13039/501100011033 and by ERDF/EU. •Partially supported by the Spanish Research Council (Ministerio de Ciencia e Innovaci´on) under project PID2021-122501NB-I00. Acknowledgments May the reader forgive me for writing the acknowledgments partially in Spanish. A mis directores de tesis, Antonio Campillo y Andr´es Marcos Encinas, cuyo apoyo ha sido esencial para el desarrollo de esta tesis. Ha sido una experiencia profundamente enriquecedora trabajar con dos matem´aticos tan excelentes. Estoy muy agradecido a Antonio por confiar en m´ı para desarrollar esta tesis y por lo mucho que he aprendido de ´el durante tantos a˜nos. Tambi´en estoy muy agradecido a Andr´es por su enorme dedicaci´on, y por su apuesta por este trabajo, que ha sido decisiva para que saliera adelante. A F´elix Delgado, que ha sido como un tercer director de esta tesis. Adem´as de su gran ayuda con los contenidos de la tesis, y haber aprendido mucho de ´el compartiendo docencia, ha sido la persona que m´as me ha influido estos a˜nos, un verdadero ejemplo a seguir que me ha hecho mejor matem´atico y mejor persona. I would like to thank the members of the jury for reading this work, and I would also like to thank the referees for their helpful comments and suggestions on a first version of this thesis. A mis compa˜neros del Departamento de ´ Algebra, Geometr´ıa, Topolog´ıa y An´alisis matem´atico de la Universidad de Valladolid, a mis compa˜neros de doctorado y a los miembros del grupo de investigaci´on SINGACOM. Ha sido un honor trabajar en la Universidad de Valladolid, y el ambiente de trabajo ha sido inmejorable. Me gustar´ıa agradecer especialmente su gran apoyo a mis compa˜neros de doctorado con los que he tenido la suerte de coincidir m´as tiempo: S¸eyma Bodur, Daniel Camaz´on, Ignacio de Miguel y Mar´ıa Mart´ın, que han sido como hermanos para m´ı. Los comienzos en investigaci´on son dif´ıciles y ha sido fundamental compartir el viaje desde el principio con este grupo, que ha sido como mi familia acad´emica. A los miembros del Departamento de Matem´aticas y del grupo de investigaci´on MAPTHE de la Universidad Polit´ecnica de Catalu˜na por ser mi segunda casa en este doctorado, incluyendo a Enric Mons´o, Margarida Mitjana y Leonardo Acho. Entre ellos, me gustar´ıa dedicar un agradecimiento especial a mis coautores ´ Angeles Carmona, Mar´ıa Jos´e Jim´enez, y al propio Andr´es, cuya influencia y ayuda en esta tesis me cuesta describir con palabras. Es un placer cuando se encuentra un grupo con el que uno est´a tan c´omodo dentro y fuera del trabajo, especialmente siendo un grupo del que he aprendido tanto. Cada visita a Barcelona, por peque˜na que sea, hace una gran diferencia. Al coordinador del programa de doctorado, Alfonso Gordaliza, por su cercan´ıa; por estar siempre preocupado y disponible para ayudar en todo lo posible en el desarrollo de la tesis iii y por su gran esfuerzo en el proceso burocr´atico. A todas las personas que me han invitado a dar conferencias a su universidad y tambi´en a todos los compa˜neros que he conocido en congresos, por lo mucho que he aprendido de ellos en tantas ponencias y tambi´en en conversaciones m´as informales. En especial me querr´ıa acordar de la Red ALAMA, a la que considero una de las comunidades cient´ıficas m´as activas y acogedoras de este pa´ıs, y particularmente me querr´ıa acordar de sus miembros Carlos Marijuan, Miriam Pisonero, Jos´e M´as, Alicia Roca, Julio Moro, Silvia Marcaida y Gorka Armentia. Thank you to the Algebraic Combinatorics group of the Eindhoven University of Technology and in particular to Aida Abiad, for inviting me for a research stay. During the time that I was there, I learned a lot from her and the experience was amazing both at a professional and a personal level. I am also grateful to the entire group for being so welcoming, especially my friend Ignacio Echave. A mis coautores Alberto Gonz´alez, Gilles Mordant y Bodhivastava Sen, con quienes estoy encantado de estar trabajando en una colaboraci´on muy estimulante. De los mejores momentos del doctorado han sido las visitas a Valladolid de Alberto, que es siempre una referencia para m´ı, tanto como matem´atico como eligiendo vino entre ratos de trabajo. Me gustar´ıa agradecer a CARTIF su apuesta decidida por la investigaci´on en matem´aticas, acordarme de mis compa˜neros de la Divisi´on de Energ´ıa de la que estoy encantado de formar parte, y especialmente dar las gracias a Ali Vasallo, Fernando Frechoso y Sergio Saludes por su confianza y flexibilidad que han sido muy importantes para poder hacer el doctorado. A mis profesores de la Universidad de Valladolid por brindarme una formaci´on excelente y a tantos compa˜neros de la carrera por compartir a˜nos muy felices. Menci´on especial merecen mis compa˜neros del Grado en Matem´aticas, ´ Alvaro Vielba, Diego Mart´ın, Alonso S´anchez, Juan Manuel Velasco, Alicia Nieto, Laura Carreras, Laura Esteban, Elena Sobrini y Elena de la Vega, junto a los que empez´o esta pasi´on por las matem´aticas entre San Bourbakis y tangos de la muerte. A mis amigos de siempre por su apoyo. Es muy importante para m´ı saber que siempre van a estar ah´ı en los momentos dif´ıciles aunque no nos podamos ver tan a menudo como me gustar´ıa. Querr´ıa destacar sobre todo a ´ Alvaro Delgado y a mis amigos de Valdunquillo Mario Valdivieso, David Fern´andez, Luis Pascual, Mus´afira Tami y Jorge Blanco. Me gustar´ıa finalizar con lo m´as importante, agradeciendo su apoyo incondicional a toda mi familia en los buenos y malos momentos. A mi hermana, mis t´ıos y mis primos por estar siempre para lo que haga falta. A mi madre Mar´ıa Jos´e Valdivieso por ense˜narme desde peque˜no la importancia de estudiar y por su calidez y cari˜no. A mi padre Jos´e Antonio Samperio tambi´en por ense˜narme la importancia de estudiar y trabajar duro para conseguir lo que me propongo. Espero que este a˜no veamos por fin al Racing volver a Primera. A mis abuelos Eloisa Rodr´ıguez, Mariano Valdivieso y Amelia L´opez, y a la memoria de mi abuelo Jos´e Samperio, por haber sido parte fundamental de mi vida. No hay cari˜no tan desinteresado y puro como el que he tenido la suerte de recibir de mis abuelos. Contents Funding i Acknowledgments ii Introduction 1 1 Discrete vector calculus on networks 7 1.1 Functionspaces.................................. 7 1.2 Topology and geometry of a graph . . . . . . . . . . . . . . . . . . . . . . . 12 1.2.1 Tangent bundle of a graph . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2.2 Difference operators on a graph . . . . . . . . . . . . . . . . . . . . . 15 1.2.3 Boundaryofaset............................. 17 1.3 Electricalnetworks ................................ 20 1.3.1 Difference operators on a network . . . . . . . . . . . . . . . . . . . . 21 1.4 Boundary value problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.5 The Dirichlet-to-Neumann map . . . . . . . . . . . . . . . . . . . . . . . . . 30 1.6 Monotonicity on DC networks . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.7 Effectiveadmittance ............................... 38 2 The inverse conductance problem 41 2.1 Background of the problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.2 Ill-posedness of the inverse conductance problem . . . . . . . . . . . . . . . . 45 2.3 Stable reformulation: the discrete piecewise constant conductance hypothesis 49 2.3.1 Polynomial optimization problem . . . . . . . . . . . . . . . . . . . . 50 Contents v 2.3.2 Problem resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.4 Stable recovery of piecewise constant conductances . . . . . . . . . . . . . . 54 2.5 Error Variation with respect to the penalty parameter . . . . . . . . . . . . . 60 2.6 Optimality guarantees of the recovered conductances . . . . . . . . . . . . . 65 3 Simultaneous recovery of the topology and admittance of a network 69 3.1 Ill-posedness of the problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.2 Reformulation of the problem: Recovery of a sparse electrical network . . . . 74 3.3 Spectral network sparsification . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.4 Sparsification of recovered electrical networks . . . . . . . . . . . . . . . . . 77 3.5 Algorithm for sparse network recovery . . . . . . . . . . . . . . . . . . . . . 82 3.6 Experimental results and discussion . . . . . . . . . . . . . . . . . . . . . . . 83 Conclusions 89 Bibliography 92 Introduction Inverse problems are a class of mathematical problems where the objective is to determine unknown causes from their known effects. Many inverse problems have garnered attention because their resolution allows to infer information that in some cases is not directly observable, and in other cases is directly observable, but observing it is more expensive and/or destructive than inferring it from its known effects. Inverse problems have applications in many different fields. For instance, they are common in deblurring images, signal recovery, and other areas of digital processing. Moreover, techniques like magnetic resonance imaging (MRI) and computed tomography (CT) scans rely on solving inverse problems to create images of the interior of the body. Inverse problems also help in interpreting seismic data for oil exploration or in analyzing astronomical data. Most inverse problems are ill-posed, meaning they do not meet for every data set the criteria of existence, uniqueness and stability of the solution. In an unstable problem, even if there is a unique solution for a data set, small changes in the data can lead to much greater changes in the solution. Regularization techniques are often used to handle this, [4, 21]. Regularization is a method to stabilize inverse problems by introducing additional information or constraints. Techniques like Tikhonov regularization or L1-regularization help in dealing with ill-posedness and improving the robustness of solutions, [1, 4, 89, 104]. In this work we focus on the study of inverse problems on finite electrical networks. We will consider Direct Current (DC) networks and balanced Alternating Current (AC) electrical networks in which all lines are inductive and “short”, (i.e., their length is shorter than 80km). An electrical network, (see Definition 1.3.1), is a pair Γ = (V, a) where Vis a finite nonempty set called vertex set, and ais a complex symmetric function on V×V with nonnegative real part and nonpositive imaginary part such that a(x, x) = 0 for any x∈V, called admittance. In the case of DC networks, ais a real function and it is called conductance. A network has an associated graph called its “network topology”, whose vertex set is Vand whose edges are the pairs {x, y}of distinct vertices such that a(x, y)= 0. The value a(x, y)= 0 is called the value of the admittance at the edge {x, y}. At a given time, there exist physical quantities, such as potential, current injected or power injected, which are defined at the vertices of the network. The value of each of these quantities at a set F⊆Vcan be represented by a complex function on Ffor AC networks and by a real function on Ffor DC networks. There are relations between these functions, which can be expressed in terms of difference operators that depend on the electrical network. Inverse problems on networks usually consist in determining information about the network 2Some Inverse Problems on Finite Networks such as its topology and/or the values of the admittance at its edges from certain measured functions of potential, current and/or power, and sometimes alongside additional known information. The objective of Chapter 1 is to establish a version of discrete vector calculus on networks, which gives us the framework to formulate the inverse problems that we study in this text, and also to introduce concepts and results that we use to solve those problems. Over time, many authors have proposed different approaches to define a discrete vector calculus on networks according to their needs and aims. On the one hand, in the area of numerical methods for solving boundary problems, the so-called Mimetic Methods describe how finite difference schemes on logically rectangular grids can be related to an operational calculus that follows the lines of differential operators, see for example [68, 69, 90]. In the field of finite or infinite networks or graphs, the vector calculus follows the guidelines of Algebraic Topology, see for instance [59, 74], especially when the graphs are part of simplicial complexes. The consideration of some boundary value problems on graphs and networks, and their variational treatment also led to the consideration of some operators as derivative, normal derivative, Laplacian, Green operator and Green functions, see for instance [44, 46, 67]. In the last decade, the need to deal with irregular graphs and abstract data with irregular interrelationships has revived the interest in vector calculus on graphs and networks, see [74, 84]. A good description of the interest of these methodologies can be found on the website [100], especially devoted to its use in image modeling. It is interesting to note that most of the above mentioned papers ignore developments made by other groups. For example, the theoretical description made on the web [100] is very similar to the one proposed in [47], although this paper is absent from the references. Furthermore, all the authors seem to be unaware of the systematic work that Japanese geometers and analysts have developed since the the last decades of the past century, see as example [70]. Another common feature of most vector calculus developed on graphs and networks is that the vector fields are identified with functions on the edge set and therefore limited to flows. This allows the formulation of Green’s identities, but not the Divergence Theorem, and also limits the study to the so-called purely resistive networks. In [18, 20, 35, 36], the authors introduced a discrete vector calculus for DC networks following the guidelines of differential geometry, whose central concept is the introduction of the tangent space at each vertex of the network. With this concept, the authors obtain discrete versions of several differential operators, vector fields, and boundary value problems that mimic the properties of its continuum analogues. The version proposed here extends that work to the case of AC networks, with some modifications. In Section 1.1 we start by introducing the general properties of the vector spaces and operators that we use throughout the document. Then, in Section 1.2 we study several topological and geometrical concepts associated to a graph without considering any weighting on the edge set. Those concepts include the tangent space at a vertex, difference operators such as the derivative and divergence, that are analogous in the discrete setting to the differential operators with the same name of the continuous calculus, and the boundary of a set of vertices. In Section 1.3 we set the fundamentals for the discrete calculus on networks. We consider the concepts introduced in the previous section, which only depend on the network topology, Introduction 3 and we introduce other difference operators depending on the topology and admittance which are analogous to the gradient, to the normal derivative, and to the Laplace-Beltrami operator. With those operators we can explain the physical laws relating the potential, current and power injected at the whole network, (see Remark 1.3.8). We prove that the operators introduced satisfy discrete versions of the Green Identities and Gauss’ Theorem. Then, in Section 1.4 we study the Dirichlet and Poisson problems on a subset F⊆V of the vertices of a network Γ, and their associated Green and Poisson operators. We extend the formulation of [35] to consider Dirichlet and Poisson problems on a subset that is not necessarily connected. The study of those problems allow us to introduce in Section 1.5 the Dirichlet-to-Neumann map of Γ and F. Under the condition that there is zero injected current at the vertices of Ffor any potential, this operator gives us the linear relationship between the potential and the respective injected current at Fc=V\F,i.e., at the complementary set of F. We extend the definition of [35] to consider also networks with edges between vertices of Fc. Section 1.6 is dedicated to survey previous results from [9] and [35] of monotonicity of real functions on DC networks in order to prove additional properties of the Dirichlet-toNeumann map of a DC network. In particular, we have that any Dirichlet-to-Neumann map is the Laplacian (the discrete analogous to the Laplace-Beltrami operator) of another network, the Kron reduction of Γwith respect to F. We show that for AC networks, the previous result is not always true, but it is true when Fc={x, y} ⊂ V. In Section 1.7 we introduce the effective admittance between two vertices xand yfrom the Dirichlet-toNeumann map of Γ and F=V\{x, y}, and therefore, by the previous result, we can relate it to a Kron reduction of Γ. Chapter 2 is dedicated to study the inverse conductance problem on a DC network, which is the discrete version of the continuous Calder´on problem. In 1980, A.P. Calder´on published the seminal paper “On an inverse boundary value problem” ([34]), which has motivated numerous developments in inverse problems. Calder´on’s problem establishes whether the electrical conductivity of a medium can be determined by making voltage and current measurements at the boundary. The problem at hand involves an unknown conductivity that needs to be determined and possibly reconstructed using boundary measurements of current and voltage. This intriguing challenge has garnered significant attention due to its wide range of applications in diverse fields, including noninvasive medical imaging, which stands as one of the most complex and compelling areas of interest (see [4, 42, 82, 91]). Calder´on’s problem is severely ill-posed, and significant efforts are being made to develop algorithms that can accurately solve it. This includes optimization algorithms, heuristic methods, and machine learning techniques, (see [24, 41]). The discrete inverse conductance problem consists in determining the conductance of a DC network from its Dirichlet-to-Neumann map. We study the problem for well-connected spider networks, which are a subfamily of critical circular planar networks and were first introduced in [54] because of their remarkable properties. In [51, 52, 53, 54, 55] it was established that for critical planar networks the problem has a unique solution. They also introduced an explicit method to solve the problem for well-connected spider networks from 10 Discrete vector calculus on networks defined after a labeling of V, but it is clearly independent of it. Moreover, the trace is also clearly independent of any labeling on V. Given x, y ∈V, we denote as K(x, y) the entry of the matrix Kcorresponding to vertices xand y, that is, the entry K(x, y) of the kernel K. More generally, given a pair of subsets F1, F2⊆V, we define the submatrix of K:K(F1;F2) = K(x, y)(x,y)∈F1×F2. We call operator to any linear application K:P−→ Qbetween two finite dimensional complex or real vector spaces with inner product Pand Q. Its null space is the subspace of Pdefined as ker(K) = {u∈Psuch that K(u)=0}. Its image is the subspace of Q defined as Img(K) = {K(u) such that u∈P}. When P=Q, we say that K:P−→ Pis an operator on P. The following results are extensions of results of operators from [17] to include the complex case. Given an operator K:P−→ Q, we denote by K∗:Q−→ Pits adjoint, which is the operator uniquely determined by the relation ⟨K(u), v⟩=⟨u, K∗(v)⟩, for all u∈Pand v∈Q. The following result is a consequence that follows almost immediately from the previous relation. Lemma 1.1.1 (Fredholm alternative).If Kis an operator on P, then we have that Img(K) = ker(K∗)⊥. Given an operator Kon P, we say that u∈Pis an eigenvector of Kif u= 0 and there exists λ∈Csuch that K(u) = λu. In that case, λis called the eigenvalue of Kassociated to the eigenvector u. The number of eigenvalues of Kis at most dim(P). We say that an operator Kon Pis self-adjoint if K∗=K. If Kis self-adjoint, then ⟨K(u), u⟩ ∈ Rfor every u∈P. Moreover, each eigenvalue of Kis real, and there is a basis u1, ..., udim(P)of Psuch that each ujis an eigenvector of K, and uj⊥ukwhenever j=k. We say that Kis positive semidefinite, respectively negative semidefinite, if ⟨K(u), u⟩ ≥ 0, respectively ⟨K(u), u⟩ ≤ 0, for every u∈C(V, C). If Kis positive semidefinite, respectively negative semidefinite, then each eigenvalue of Kis nonnegative, respectively nonpositive. Let K:P−→ Qbe an operator, and let m= min {dim(P),dim(Q)}. Then K∗◦K is a self-adjoint and positive semidefinite operator on P. We denote its eigenvalues by λ1≥... ≥λdim(P)≥0. The singular values of Kare the nonnegative numbers σj=pλj for each j= 1, ..., m. Then, we define the condition number of Kas κ(K) = σ1/σm. We have that κ(K) = ∞iff Kis singular, i.e., iff ker(K)={0}. We also define the spectral norm of Kas its largest singular value, ∥K∥2=σ1. Let Kbe a self-adjoint operator on C(V), respectively on C(V, Rm). Then, by the Courant-Fisher theorem [94], we have that the maximum of the eigenvalues of Kis equal to Function spaces 11 max ||u||=1 {⟨K(u), u⟩}. Also, for any u∈C(V), respectively u∈C(V, Rm), we have that ∥K(u)∥≤∥K∥2∥u∥. We denote by C:C(V, C)−→ C(V, C) the conjugation application, that is defined by C(u) = ¯ufor each u∈C(V, C). We say that K:C(V, C)−→ C(V, C) is a symmetric operator if K∗=C ◦ K◦ C [83], or equivalently iff K=C ◦ K∗◦ C. If we restrict the definition to operators in C(V), Cis the identity, so being symmetric and self-adjoint is equivalent. Given an operator Kon C(V) or on C(V, C), we define its real and complex parts as ℜ(K) = 1 2(K+K∗) and ℑ(K) = 1 2i(K−K∗), respectively. It is clear that they are self-adjoint operators and K=ℜ(K) + iℑ(K), (see [49]). Lemma 1.1.2. If Kis a symmetric operator on C(V)or on C(V, C), then ℜ(K)|C(V)and ℑ(K)|C(V)are operators on C(V). Proof. Let Kbe a symmetric operator and u∈C(V). Then, K∗=C ◦K◦C and u=u, so on one hand ℜ(K)(u) = C ◦ℜ(K)C(u)=1 2C ◦(K+K∗)◦C(u) =1 2C ◦K◦C +C ◦K∗◦C(u) = 1 2(K∗+K)(u) = ℜ(K)(u), and on the other hand ℑ(K)(u) = C ◦ℑ(K)C(u)=−1 2iC ◦(K−K∗)◦C(u) =1 2iC ◦K∗◦C −C ◦K◦C(u) = 1 2i(K−K∗)(u) = ℑ(K)(u). If Kis a real, respectively complex, kernel on F, we define the integral operator associated with Kas the endomorphism K:C(F)−→ C(F), respectively as the endomorphism K:C(F, C)−→ C(F, C), that assigns to each u∈C(F), respectively u∈C(F, C), the function K(u)(x) = ZF K(x, y)u(y)dy for all x∈V. The relationship between kernels, integral operators and endomorphisms of C(F) is given by the following result. Its first part can be seen as a discrete version of the Schwartz’s Kernel Theorem, because of the natural identification between C(F) and its dual space. Proposition 1.1.3 (Kernel Theorem [19, Prop. 5.1]).Each endomorphism Kof C(F), respectively C(F, C), is an integral operator associated with a real, respectively complex, kernel Kon Fwhich is uniquely determined by the relation K(x, y) = K(εy)(x)for each (x, y)∈F×F. Moreover, if Kis the integral operator on Fassociated to the kernel Kand Ais a non empty subset of F, then the following statements hold: (i) The adjoint of K,K∗, is the operator associated with the kernel K∗. Therefore, K is self-adjoint iff Kis self-adjoint. 12 Discrete vector calculus on networks (ii) The operator C◦K∗◦C is associated with the kernel K⊤. Therefore, Kis symmetric iff Kis symmetric. (iii) Img K⊆C(A)iff K∈C(A×F). (iv) C(F\A)⊆ker Kiff K∈C(F×A). In particular, each endomorphism of C(V), respectively C(V, C), is the integral operator associated to some kernel. Given K,Jendomorphisms of C(V), respectively of C(V, C), whose kernels are respectively Kand J, then the kernel of K◦Jis K◦J, defined for each x, y ∈Vas (K◦J)(x, y) = X z∈V K(x, z)J(z, y) = ZV Kx(z)Jy(z)dz =⟨Jy, Kx⟩. In addition, we can define the trace on the space of endomorphisms of C(V) or C(V, C) as tr(K) = tr(K), where Kis the kernel of K. From this definition, we can endow the space of endomorphisms of C(V) or of C(V, C), and as a consequence the space of kernels C(V×V) or C(V×V, C), with a natural inner product: if Kand Jare the kernels associated to the operators Kand Jrespectively, then ⟨K,J⟩= tr(K◦J∗) = ZV⟨Jx, Kx⟩dx = tr(K∗◦J). In particular, ⟨K,J⟩=⟨K∗,J∗⟩. The associated norm on the space of endomorphisms, or on the space of kernels, is named Frobenius norm and denoted as ||·||Fr . Therefore, ||K||Fr =||K||Fr = tr(K∗◦K)1 2. 1.2 Topology and geometry of a graph In this section we will present several topological and geometrical concepts associated to a graph. We start with the basic definitions, (see [19, 35] for a detailed discussion). Although almost all concepts we next introduce can be defined in infinite and locally finite graphs, every graph throughout this work will be finite, undirected and simple. A graph is a pair G= (V, E) where Vis a finite nonempty set called vertex set, and E⊆{x, y}such that x, y ∈Vand x=yis called edge set. A vertex is any x∈V. We say that x, y ∈Vare adjacent iff {x, y} ∈ Eand usually we denote it as x∼y. We will denote {x, y} ∈ Ealso by exy and so, exy =eyx. In Figure 1.1, we show the representation of some examples of graphs. We define the subspaces of kernels C(G) = {f∈C(V×V)|f(x, y) = 0 if exy /∈E}, C(G, C) = {f∈C(V×V, C)|f(x, y) = 0 if exy /∈E}and C+(G) = {f∈C+(V× V)|f(x, y) = 0 if exy /∈E}. The subspaces of symmetric kernels of C(G), C(G, C) and C+(G) can be identified with the function spaces on the edge set C(E), C(E, C) and C+(E), respectively. Topology and geometry of a graph 13 Figure 1.1: Examples of (locally finite) graphs We say that a subset F⊆Vis connected if for any x, y ∈Fthere exists a path contained in Ffrom xto y, that is, a (finite) sequence of vertices x0, . . . , xk∈Fsuch that x0=x, xk=yand exj−1,xj∈Efor all j= 1, . . . , k. We say that a graph is connected if Vis connected. We say that two distinct vertices x, y ∈Vare connected through Fif there exists a path from xto ysuch that every vertex of the path distinct from xor ybelongs to F. Given a graph G= (V, E), and a subset F⊆V, we denote by GFthe induced subgraph GF= (F, EF) with vertex set F, and only the set of edges of Gwhich are adjacent to two vertices of F,i.e.,EF={exy ∈Esuch that x, y ∈F}. There is a unique partition of V=V1⊔... ⊔Vs, with s≥1, such that E=EV1⊔... ⊔EVs and GViis connected for i= 1, ..., s. We call each GVi, or Vi, a connected component of G and write G=GV1⊔... ⊔GVs. Given x, y ∈V, we denote by d(x, y) the geodesic distance in the graph, that is defined as the minimum length of all paths from xto yif xand ybelong to the same connected component of Gand as d(x, y) = ∞otherwise. It is clear that dgives a structure of metric space to the set of vertices of each connected component of the graph and that d(x, y)=1 iff x∼y. Given x∈V, its combinatorial degree k(x) is the number of vertices adjacent to x, that is k(x) = |{y∈V:y∼x}|. 14 Discrete vector calculus on networks 1.2.1 Tangent bundle of a graph We follow the approach of [35, 36], in which the topological and geometrical concepts in a graph are based on the definition of a tangent space at each point of a graph. The main difference of our approach is that we consider the tangent space as a complex vector space with the standard inner product, instead of a real vector space. We define the tangent space Tx(G) of a vertex xas the complex vector space of formal linear combinations of the set of edges {exy ∈E:y∼x}. The dimension of Tx(G) is k(x), and the set of those edges is a basis of Tx(G), that we call its coordinate basis. In Figure 1.2 we show the coordinate basis at a vertex. Tx(G) x x Figure 1.2: Graph and tangent space at vertex x. Avector field on the graph is any function f:V−→ S x∈V Tx(G) with the property that for every x∈V,f(x)∈Tx(G). We denote the space of vector fields by X(G). The support of fis defined as supp(f) = {x∈V:f(x)=0}. A vector field f∈ X(G) is uniquely determined by its components in the coordinate basis, so we can define a kernel f∈C(G, C), which is called the component function of f, such that for any x∈V,f(x) = X y∼x f(x, y)exy.This association between fand fdefines an isomorphism between X(G) and C(G, C). Therefore, we can define the symmetric and antisymmetric components of f∈ X(G), fsand fa, as the vector fields associated with fs and fa, respectively. Note that f=fs+fa. We say that fis symmetric if f=fsand that f is antisymmetric, or a flow, if f=fa. Given u∈C(V, C) and f∈ X(G) with component function f, we denote by uf∈ X(G) the vector field whose component function is uf ∈C(G, C). We define the inner product of f,g∈ X(G) as ⟨f,g⟩=1 2ZV [f(x),g(x)] dx, where for any x∈Vwe denote by [f(x),g(x)] the inner product on Tx(G) determined by Topology and geometry of a graph 15 the orthonormality of its coordinate basis, i.e., for any y, z such that y∼xand z∼x, then [exy, exz] = εy(z). As a consequence, if fand gare the respective component functions of f and g, then [f(x),g(x)] = X y∼x f(x, y)g(x, y) = X y∈V f(x, y)g(x, y). We have included the factor 1 2in the definition of the inner product of X(G) because each edge is considered twice. In particular, including that factor we will avoid getting a factor 2 multiplying the sum in the result of Lemma 1.2.2. Lemma 1.2.1. If f∈ X(G)is symmetric and g∈ X(G)is a flow, then ⟨f,g⟩= 0. As a consequence, given any f,g∈ X(G), we have that ⟨f,g⟩=⟨fs,gs⟩+⟨fa,ga⟩. Proof. Let f∈ X(G) be symmetric and g∈ X(G) be a flow. Then, we have ⟨f,g⟩=1 2ZV×V f(x, y)g(x, y)dydx =−1 2ZV×V f(y, x)g(y, x)dxdy =−⟨f,g⟩. The second statement follows trivially from the properties of any inner product. The following result is straightforward. Lemma 1.2.2. Let both f,g∈ X(G)be either symmetric vector fields or flows, with component functions fand g. Then: ⟨f,g⟩=X exy∈E f(x, y)g(x, y). Note that the sum in Lemma 1.2.2 is well defined because if both fand gare symmetric or are flows, then f(x, y)g(x, y) = f(y, x)g(y, x) for every x, y ∈V. Remark 1.2.3. Due to the isomorphism between C(G, C) and X(G), the inner product on X(G) determines an inner product on C(G, C) defined for each f, g ∈C(G, C) as ⟨f,g⟩, where f,g∈ X(G) are the vector fields whose component functions are fand g, respectively. The norm associated with this inner product is ||f|| =⟨f,f⟩1 2. This inner product is different than the restriction to C(G, C) of the one in the space of kernels C(V×V, C) defined at the end of Section 1.1 from the inner product on the space of endomorphisms, whose associated norm is ||f||Fr . Throughout the whole text, whenever we consider the norm of a kernel f∈C(G, C) for a graph G, we will use that first norm ||f|| rather than the Frobenius one. If fis symmetric, by Lemma 1.2.2 we have that ||f||2=P exy∈E|f(x, y)|2. 1.2.2 Difference operators on a graph Now, we will define the derivative and divergence as discrete difference operators on a graph. They are analogous to the differential operators with the same name in the continuous vector calculus. 16 Discrete vector calculus on networks We define the derivative [35] as the linear map d:C(V, C)−→ X(G), which assigns to each u∈C(V, C) the flow du, such that for each x∈V,du(x) = P y∼x (u(y)−u(x))exy. Analogously to the continuous case, du= 0 iff u∈C(V, C) is constant within each connected component of G. We define the divergence as the linear map div =−d∗:X(G)−→ C(V, C). Namely, for any f∈ X(G), div(f)∈C(V, C) is the function determined by: ⟨div(f), u⟩=ZV div(f)u dx =−1 2ZV [f(x),du(x)] dx =−⟨f,du⟩(1.1) Let G=GV1⊔... ⊔GVsbe the decomposition of Gin its connected components. For any i= 1, ..., s, substituting u=χViin the previous expression, we have RVidiv(f)dx = 0 for any f∈ X(G). In particular, RVdiv(f)dx = 0 for any f∈ X(G). In [36], for any weighting ω∈C+(V) on the set of vertices, the authors define an inner product on C(V) associated to ω. Then, they define the divergence as div =−d∗with respect to that inner product. We do not consider any weighting on the vertices, although when we restrict the divergence to real vector fields, our definition of divergence agrees with the one in [36] when the weighting ωis equal to one. In [35], the divergence is introduced in a different manner because the authors consider an inner product on the tangent space at a vertex which is dependent on the electrical conductance on the edges. Nevertheless, that definition of divergence turns out to be independent of the conductance and it is also equivalent to our definition when we restrict it to real vector fields. As a consequence, our definition satisfies the following proposition from [35]. Proposition 1.2.4. If f∈ X(G)and f∈C(G, C)is its component function, then for any x∈V: div(f)(x) = X y∼x fa(x, y) = X y∈V fa(x, y). Proof. If for any x∈Vwe substitute u=εxin (1.1), then we get div(f)(x) = ⟨div(f), εx⟩=⟨f,−dεx⟩=⟨fa,−dεx⟩, where the last equality follows from Lemma 1.2.1. By definition, for any z∈V,−dεx(z) = P y∼z (εx(z)−εx(y))ezy. The component function of the flow −dεxis −dεx(z, y) = εx(z)−εx(y), which is nonzero only if y∼zand zor yare equal to x. Moreover, −dεx(x, y) = 1, so, by Lemma 1.2.2: div(f)(x) = −X exy∈E fa(x, y)dεx(x, y) = X y∼x fa(x, y). Topology and geometry of a graph 17 1.2.3 Boundary of a set A subset of vertices F⊆Vof a graph can be seen as the discrete analogue to a compact manifold. In [35, 36] there are discrete concepts analogous to topological concepts involving a compact manifold such as its interior, boundary, closure, exterior normal vector field and the Divergence Theorem, which we review below. The interior of Fis ◦ F={x∈F:y∈Fwhen y∼x}=x∈F:{y:d(x, y)≤1} ⊂ F. The boundary of Fis δ(F) = {x∈Fc| ∃y∈Fsuch that y∼x}={x∈V:d(x, F) = 1}. The interior boundary of Fis δ(Fc) = F\◦ F={x∈V:d(x, Fc) = 1}. The closure of Fis ¯ F=F∪δ(F) = {x∈V:d(x, F)≤1}. The Exterior of Fis Ext(F) = V\¯ F={x∈V:d(x, F)>1}. The Figure 1.3 shows a vertex set Fin light brown color and its boundary in ochre color. Vertices in ◦ F,δ(F), δ(Fc) or Ext(F) are depicted in different color. F δ(F) Figure 1.3: ◦ F(blue), δ(F) (orange), δ(Fc) (green) and Ext(F) (light grey). Observe that to define the above geometric notions, the (possible) edges between boundary vertices play no role. For this reason this kind of edges are depicted in light grey in Figure 1.3 The normal vector field to F is the flow nF=−dχF. Hence, its component function in C(G, C) is given by nF(x, y) =      1, y ∼xand (x, y)∈δ(Fc)×δ(F) −1, y ∼xand (x, y)∈δ(F)×δ(Fc), 0,otherwise As a consequence, nFc=−nFand supp(nF) = δ(Fc)∪δ(F). Therefore, given x∈F,nF(x) only takes into account the edges exy such that y∈Fand hence nFhas the meaning of exterior normal field. The concept of the normal field to a set Fappears for the first time in the literature in [20], although it had already been used previously by the authors. Without the vector 18 Discrete vector calculus on networks field formalism considered here, the notion of normal derivative was already present in many works related to Graph Analysis, see for example [22, 44, 47, 67] where the authors introduce the notions more or less independently of each other. In fact, these authors ignore the work of M. Yamasaki and collaborators, who introduced several years earlier a similar concept related to the interior normal derivative, see [70] and references therein. In Figure 1.4 we consider the same set Fas in Figure 1.3 and show that different vertices on the boundary could have different number of edges joining them with vertices in F. Figure 1.4: xhas two edges and zhas one edge joining them with vertices in F. The motivation to introduce the normal field was to express the normal derivative of a function as the inner product of its derivative with a field representing the exterior normal, thus mimicking differential calculus with the aim of proving the divergence theorem and Green’s identities. All the mentioned authors have their version for the Green Identities, see the next section, but none of them present something similar to the Divergence Theorem, due to the absence of the notion of normal field. As the proof of this result included in [20] is given in a more general setting that that considered in this work, we include here its proof. Proposition 1.2.5. (Divergence Theorem) For any f∈ X(G), it is verified that ZF div(f)dx =Zδ(F) [fa(x),nF(x)] dx. Proof. By the definition of divergence and normal vector field, and by Lemma 1.2.1, we have ZF div(f)dx =⟨div(f), χF⟩=−⟨f,dχF⟩=−⟨fa,dχF⟩=⟨fa,nF⟩. Denoting by fthe component function of f, from Lemma 1.2.2 we get ⟨fa,nF⟩=X (x,y)∈δ(Fc)×δ(F) fa(x, y) = Zδ(F) [fa(x),nF(x)] dx. Topology and geometry of a graph 19 Definition 1.2.6. We say that a graph G= (V, E) is a graph with boundary if there is a proper subset F⊂Vsuch that V=¯ Fand the boundary δ(F) is totally disconnected, i.e., Gδ(F)= (δ(F),∅). Well-connected spider graphs Now we will introduce different subsets of graphs with boundary, in order to illustrate the previous concepts and, in particular, to define the well-connected spider graphs. Such graphs were initially introduced in [54] due to their exceptional characteristics and will be the type of graphs with boundary on which we will formulate the inverse problem in Chapter 2. A circular planar graph [51] is a graph with boundary G= ( ¯ F, E) which can be planarly embedded (i.e., without crossing edges) in a disk D⊂R2, with the vertices within set Flocated in the interior of D(◦ D) and the boundary vertices of δ(F) located in the circumference of D(∂D). Now, let G= ( ¯ F, E) be a circular planar graph and we fix an embedding of it with the characteristics of the last paragraph. A circular pair is a pair (Ξ; Σ) = (ξ1, ..., ξs;σ1, ..., σs) of disjoint subsets of δ(F) such that the sequence (ξ1, ..., ξs, σ1, ..., σs) is in clockwise order. A circular pair (Ξ; Σ) is connected through Fif there are sdisjoint paths ϱ1, ..., ϱssuch that each ϱjstarts at ξj, ends at σjand, apart from these two, passes only through vertices of F [51]. We consider the process of contracting an edge exy ∈E, with x∈F, from a network with boundary G= ( ¯ F, E), which consists in creating the graph G′= (F′, E′) such that F′=F\{x}and E′=E\exz such that z∈F∪{eyz such that exz ∈Eand z=y}. Note that δ(F′) = δ(F). We also consider the process of removing the edge exy ∈E from G= ( ¯ F, E), which consists in creating the graph G′= (F′, E′), with F′=Fand E′=E\{exy}. We say that a circular planar graph Gis a critical circular planar graph if the operation of removing any edge or the operation of contracting any edge to a single vertex results in a graph G′such that there is at least one circular pair that is connected through Fin Gand it is not connected through F′in G′(see [51]). In [48], the author introduced the notion of well-connected graph, which is a circular planar graph in which every circular pair is connected through F. Awell-connected spider graph G= ( ¯ F, E) with ℓ≥0 circles and m= 4ℓ+ 3 radii is a particular example of a critical circular planar graph, which is the graph corresponding to the following planar embedding. We start by placing a vertex set in the center of a disk D and the mboundary vertices of δ(F) in ∂D. Next, we draw straight lines, referred to as radii, from the central vertex to each of the boundary vertices. Then, we draw ℓdistinct concentric circumferences contained within the interior of Dwhose center is the center of D. Now, we place a vertex for every intersection point of every circle and radius. The graph’s edges are determined by these radii and circles, as shown in Figure 1.5. 26 Discrete vector calculus on networks Remark 1.3.8. The physical laws governing the current transmission in electrical networks can be stated using the difference operators that we have defined. For AC networks, the potential in the network can be represented by a function u∈C(V, C). Then, by Ohms’ law, −∇urepresents the flow of electrical current. That is, each of the coefficients in the coordinate basis of −∇u(x) is equal to the current flowing from xto each of its neighbours. Also, by Kirchhoff’s Current Law, L(u) is the function assigning to each vertex the current injected at it when the potential at the network is u. Then, uL(u) is the function assigning to each vertex the apparent power injected at it when the potential at the network is u, and thus E(u, u) is equal to the total power dissipated at the network when the potential is u. For DC networks, the potential in the network can be represented by u∈C(V) and the rest of results are analogous, with the additional result that the dissipated power in the network is always nonnegative. 1.4 Boundary value problems The objective of this section is to review several results about the Dirichlet and Poisson problems on DC networks that can be found in [17, 35, 36], and to extend them to the case of AC networks. We study the following problem. Given an electrical network Γ,F⊆V,h∈C(F, C)and g∈C(Fc,C), find u∈C(V, C) such that L(u) = hon F, u =gon Fc.(1.4) When F=Vthis is called the Poisson problem and when F⊊Vthis is called the Dirichlet problem. We have that Fc=δ(F)⊔Ext(F), but because the values of the Laplacian of a function at Fonly depend on the values of the function at ¯ F, the set of solutions of (1.4) only depends on the values of gat δ(F), so it is called a boundary value problem on F. The associated homogeneous boundary value problem consists in finding u∈C(V, C)such that L(u) = 0 on F, u = 0 on Fc.(1.5) Lemma 1.4.1. Let Γ = ΓV1⊔... ⊔ΓVsbe the decomposition in connected components of Γ. Then, the set of solutions of the homogeneous boundary value problem (1.5) is the vector subspace Vof C(F, C)spanned by nχVisuch that Vi⊆Fo. Proof. Clearly, any function of Vis a solution of (1.5). Now, let u∈C(F, C) be a solution of (1.5). Then, E(u, u) = ZV uL(u)dx =ZF uL(u)dx +ZFc uL(u)dx = 0, so uis a linear combination of χV1, ..., χVs. As u= 0 in Fc,umust be equal to zero in each Visuch that Vi∩Fc=∅, so u∈ V. Boundary value problems 27 Proposition 1.4.2. Let Γ=(V, a)be an electrical network and let Γ=ΓV1⊔... ⊔ΓVsbe its decomposition in connected components. Then, (1.4) has a solution if and only if ZVi h dx = 0 for each isuch that Vi⊆F. Moreover, if the problem has a solution, then there is a unique solution vsuch that ZVi v dx = 0 for each isuch that Vi⊆F. Proof. In the case (1.4) has a solution, then, for any solution u, the set of all its solutions is u+V. Consider the problem (1.4) of finding u∈C(V, C)such that L(u) = h−L(g) on F, u = 0 on Fc.(1.6) Then uis a solution to (1.6) iff u+gis a solution to (1.4). We denote by M:C(F, C)−→ C(F, C) the linear operator M(u) = L(u) on Ffor each u∈C(F, C). Considering the inner product on C(F, C) induced by the standard one on C(V, C), we have that, for every u, v ∈C(F, C): ⟨M(u), v⟩=ZF M(u)vdx =ZVL(u)vdx =ZV uL(v)dx =ZF uM(v)dx =⟨u, M(v)⟩, so M∗=C ◦M◦C, and thus Mis a symmetric operator. Now, ker(M) = V. Moreover, u∈ker(M∗) iff M(u) = 0, that is, iff u∈ker(M). As u∈ V iff u∈ V, we have that ker(M) = ker(M∗), and, by the Fredholm alternative, Img(M) = V⊥. Then, (1.6) has a solution iff ⟨h− L(g), χVi⟩= 0 for each isuch that Vi⊆F. This is equivalent to saying RVih dx =RViL(g)dx = 0 for each isuch that Vi⊆F, and the last equality follows from Gauss’ Theorem. To prove the uniqueness, we see that there is a unique solution wto (1.6) such that w∈ V⊥. This is equivalent to that v=w+gis the only solution to (1.4) satisfying that ZVi v dx =ZVi w dx = 0 for each isuch that Vi⊆F. We say that a function uis harmonic on Fwhen L(u) = 0 on F. The particular case of (1.4) in which h= 0 consists in, given the values of a function at Fc, seeking for an extension of the function at Fthat is harmonic on F. In this case, any solution must be constant on each isuch that Vi⊆F, so we get the following result. Corollary 1.4.3. Given an electrical network Γ,F⊆Vand g∈C(Fc,C), the boundary value problem of finding u∈C(V, C)such that L(u) = 0 on F, u =gon Fc,(1.7) always has a solution. Moreover, it has a unique solution that is equal to zero on every connected component of the network that is contained in F, that we denote by ug. 28 Discrete vector calculus on networks Remark 1.4.4. Let vbe a solution of (1.7). Then ∂v ∂nF=∂ug ∂nF,L(v) = L(ug) and E(v, v) = E(ug, ug). In [30], a uniqueness result for a Dirichlet problem that is similar to (1.7) was obtained. The problem there is partially more general than (1.7) in the sense that they consider the possibility of adding a Schr¨odinger potential with some restrictions and the possibility of having negative susceptance, but it is also partially more restrictive than (1.7) in the sense that they only study the problem for connected networks. In the connected case, we obtain the same uniqueness result immediately from Corollary 1.4.3. Corollary 1.4.5. If Γis a connected network and h= 0, then any Dirichlet problem has a unique solution and the set of solutions to the Poisson problem is the set of constant functions on V. Let Γ = ΓV1⊔... ⊔ΓVsbe the decomposition in connected components of Γ, and F⊂V. We denote by F0the union of the Visuch that Vi⊆F, and F1=F\F0. Analogously to the operator Mdefined in the proof of Proposition 1.4.2, we denote by MF1:C(F1,C)−→ C(F1,C) the linear operator such that for each u∈C(F1,C), MF1(u) = L(u) on F1, which is an automorphism. Definition 1.4.6. We define the Green operator of Fas J=MF1 −1, which is an automorphism of C(F1,C). For any h∈C(F1,C), u=J(h) is the unique solution to the boundary problem L(u) = hon F1and u= 0 on Fc⊔F0. We define the Poisson operator of Fas the linear operatorK:C(Fc,C)−→ C(V\F0,C) such that, for each g∈C(Fc,C), K(g) = ug. That is, K(g) is the unique function satisfying L(K(g)) = 0 on F,K(g) = gon Fcand K(g) = 0 on F0. Lemma 1.4.7. The Green operator Jis symmetric with respect to the inner product on C(F1,C)induced by the standard one on C(V, C). Proof. Given g, h ∈C(F1,C), we denote u=J(g) and v=J(h). Then we have L(u) = g and L(v) = hon F1, and thus: ⟨J(g), h⟩=ZF1 J(g)hdx =ZV uL(v)dx =ZVL(u)vdx =ZF1 gJ(h)dx =⟨g, J(h)⟩, so J∗=C ◦J◦C. The kernel J∈C(F1×F1,C) associated with the Green operator Jon F, is called the Green kernel. By the previous lemma, it is symmetric. The matrix associated with MF1is L(F1;F1), so the matrix associated with Jis L(F1;F1)−1. We can extend the Poisson operator Kon Fto an endomorphism of C(V\F0,C) such that the image of any vector in C(F1,C) is equal to zero. By the Kernel Theorem, it has an associated kernel K∈C((V\F0)×Fc,C), which is called the Poisson kernel. The following result gives a characterization of the Green and Poisson kernels as solutions of boundary value problems, and a relation between them. The Dirichlet-to-Neumann map 29 Proposition 1.4.8. For every y∈F1, the function Jyis determined by L(Jy) = εyon F1. For every y∈Fc, the function Kyis determined by L(Ky) = 0 on F,Ky=εyon Fcand Ky= 0 on F0. Furthermore, K(x, y) = εy(x)−∂J ∂ny(x, y),for every x∈V\F0and y∈Fc. Moreover, ∂K ∂nx∈C(δ(F)×δ(F),C)and, for every x, y ∈δ(F), ∂K ∂nx(x, y) = εy(x)κF(x)−∂2J ∂nx∂ny(x, y). As a consequence, ∂K ∂nxis symmetric on C(δ(F)×δ(F),C). Proof. By the correspondence between kernels and operators, for every y∈F1,Jy=J(εy). As Jis an automorphism, this is equivalent to L(Jy) = 0 on F. Similarly, for every y∈Fc, Ky=K(εy) and thus u=Kyis the unique solution of the boundary problem L(u) = 0 on F,u=εyon Fcand u= 0 on F0. That problem is equivalent to seeking for v∈C(F1,C) such that L(v) = −L(εy) on F1, in the sense that Ky=εy−J(L(εy)|F1). Now, for every x∈F1,L(εy)(x) = RVa(x, z)(εy(x)−εy(z)) dz =−a(x, y), so we get: J(L(εy)|F1) = −ZF1 J(x, z)ay(z)dz ZF1 a(y, z) (J(x, y)−J(x, z)) dz =∂J ∂ny(x, y). Now, we define the kernel ε∈C(Fc×Fc,C) as ε(x, y) = εy(x) for every x, y ∈Fc. The expression of ∂K ∂nxfollows from the fact that, for every x∈δ(F): ∂ε ∂nx (x, y) = ∂εy ∂nF (x) = ZF a(x, z) (ε(x, y)−ε(x, z)) dz =εy(x)κF(x). Clearly, ∂ε ∂nx∈C(δ(F)×δ(F),C). Moreover, ∂J ∂ny∈C(F1×δ(F),C), so also ∂2J ∂nx∂ny∈ C(δ(F)×δ(F),C); and thus ∂K ∂nx∈C(δ(F)×δ(F),C). The symmetry of this kernel follows from Lemma 1.3.7. Remark 1.4.9. In the particular case of (1.4) in which Γ is a DC electrical network, h∈ C(F) and g∈C(Fc), we can restrict the problem to seek only for real solutions, i.e.,to seek for u∈C(V)such that L(u) = hon F, u =gon Fc.(1.8) Then, restricting to real function spaces, we can obtain for (1.8) results that are analogous to all the results in the section. As a consequence, in that case, the solution vin Proposition 1.4.2 and the solution ugin Corollary 1.4.3 are real. Because of that, we can consider the real restrictions of the Green and Poisson operators, that we also denote as J:C(F1)−→ C(F1) and K:C(Fc)−→ C(V\F0), respectively. Its associated Green and Poisson kernels are real and also satisfy Lemma 1.4.7 and Proposition 1.4.8, plus the fact that, in addition, ∂K ∂nx∈C(δ(F)×δ(F)). 30 Discrete vector calculus on networks 1.5 The Dirichlet-to-Neumann map Consider an electrical network Γ = (V, a) and F⊂V. Recall that for any function g∈ C(Fc,C), the Poisson operator gives a solution K(g) = ug∈C(V, C) to (1.7), that is, an extension of gto all Vthat is harmonic on F. This section is devoted to the study of the relationship between gand L(ug), which is given by the following linear operator. Definition 1.5.1. Given an AC (respectively DC) electrical network and F⊂V, the Dirichlet-to-Neumann map is the following endomorphism Λ: C(Fc,C)−→ C(Fc,C) (respectively Λ: C(Fc)−→ C(Fc)) defined for any g∈C(Fc,C) (respectively g∈C(Fc)) as: Λ(g) = ∂ug ∂nF +LFc(g) = L(ug) = (L◦K)(g). Note that, because of Remark 1.4.4, the definition of the Dirichlet-to-Neumann map is independent of the chosen solution of (1.7). In the literature, the Dirichlet-to-Neumann map is only defined for networks with boundary. For AC networks, it is defined as the function Υ: C(δ(F),C)−→ C(δ(F),C) such that, for any g∈C(δ(F),C), Υ(g) = ∂ug ∂nF .Similarly, for DC networks, it is defined as the function Υ: C(δ(F)) −→ C(δ(F)) such that, for any g∈C(δ(F)), Υ(g) = ∂ug ∂nF .Note that, for networks with boundary, our definition agrees with this one, i.e. Λ = Υ. This is because the subnetwork of Γ corresponding to Fcis ΓFc= (Fc,0), so E(ΓFc) = ∅and thus its Laplacian LFcis zero. For DC networks, the Dirichlet-to-Neumann map was considered in [52]. Later, in [10], it is proved that the Dirichlet-to-Robin map, which is a generalization of the Dirichlet-toNeumann map to the case of a Schr¨odinger potential, is self-adjoint and positive semidefinite. The characterization of possible Dirichlet-to-Neumann maps of networks with complex weights at the edges whose imaginary parts are not necessarily nonpositive was first derived in [78]. It was later rediscovered independently in [87]. A generalization of the Dirichlet-toRobin map to these networks with complex weights for certain complex Schr¨odinger potentials was defined in [30]. The extension of the map to general electrical networks will allow us to introduce in Section 1.7 the effective admittance from this map. This will allow us in Section 3.3 to give a novel physical interpretation to the product of the conductance of an edge by its effective resistance and, as a consequence, to the Algorithm 1 of spectral sparsification of networks. We can also give the following physical interpretation to the Dirichlet-to-Neumann map. Under the condition that there is zero injected current at the vertices of Ffor any potential, the values of a potential at Fcuniquely determine the values of that potential at the interior boundary of F, and thus, they also uniquely determine the values of injected current at Fc. Moreover, the relationship between potential at Fcand injected current at Fcis linear. In the electrical networks of the real world usually there is a subset of vertices Fthat The Dirichlet-to-Neumann map 31 are not associated to any generator or consumer in which there is never injected current, and thus the Dirichlet-to-Neumann map allows us to study the relationship between current and voltage in the rest of the vertices without having to calculate the voltage at F. Another practical application of this discrete operator is that, for networks with boundary, it is a mimetic discretization of the continuous Dirichlet-to-Neumann map, that is defined as follows in [6]. Let Ω ⊆Rnbe a bounded connected open set with n≥2 and a bounded measurable conductivity σwhich satisfies λ≥σ≥λ−1almost everywhere in Ω for some λ > 0. Given a potential g∈H1/2(∂Ω) in the trace space on the boundary ∂Ω, the induced potential ug on Ω solves the Dirichlet problem of finding u∈H1(Ω) such that ∇·(σ∇u) = 0 in Ω, u|∂Ω=g. The Dirichlet-to-Neumann map, (see [6]), is defined as the operator Λ: H1/2(∂Ω) −→ H1/2(∂Ω) such that Λσ(g) = σ∂ug ∂n∂Ω , for every g∈H1/2(∂Ω), where ndenotes the outer unit normal vector to ∂Ω. Roughly speaking, H1(Ω) is the subset of the Hilbert space of square-integrable functions L2(Ω) whose weak derivatives belong to L2(Ω), and therefore with weak gradient in L2(Ω). These functions can be extended to functions on ∂Ω. The set of these extensions is H1/2(∂Ω), which is a subspace of functions of L2(∂Ω) which have certain regularity. The consideration of these spaces allows the variational treatment of the problem and the proof that there is a solution (in H1(Ω)). The detailed definition and properties of these spaces can be found in [3, 31]. The knowledge of the properties of the discrete Dirichlet-to-Neumann operator will allow us to study the discrete problem analogous to Calder´on’s inverse conductivity problem, which will be the objective of Chapter 2. The bilinear form on C(Fc,C) associated to the Dirichlet-to-Neumann operator is given, for every g, h ∈C(Fc,C), by: ⟨h, Λ(g)⟩=ZV hΛ(g)dx =⟨uh,L(ug)⟩=E(uh, ug). By the First Green identity, and considering that L(ug) = 0 on F, we have that ⟨h, Λ(g)⟩=Zδ(F) uh ∂ug ∂nF dx +ZFc hLFc(g)dx =1 2ZV×V a(x, y)uh(x)−uh(y)ug(x)−ug(y)dxdy. Proposition 1.5.2. Let Γ = ΓV1⊔... ⊔ΓVsbe the decomposition in connected components of Γ, and F⊂V. The Dirichlet-to-Neumann map Λis symmetric, singular, its real part is 32 Discrete vector calculus on networks positive semidefinite and its imaginary part is negative semidefinite. Moreover, its null space is the set of functions that are constant on each Vi∩Fcthat is not empty. Furthermore, the symmetric kernel N∈C(Fc×Fc,C)of Λis: N=L|Fc×Fc−∂2J ∂nx∂ny . Proof. For every g, h ∈C(Fc,C), we have that ⟨Λ(g), h⟩−⟨g, Λ(h)⟩=ZV Λ(g)h−gΛ(h)dx =Zδ(F)∂ug ∂nF uh−ug ∂uh ∂nFdx +ZFcLFc(g)h−gLFc(h)dx = 0, where the integral in δ(F) is equal to zero by the Second Green Identity on F, and the integral in Fcis equal to zero by the Second Green Identity on the whole subnetwork ΓFc. As a consequence, Λ∗=C ◦Λ◦C, so Λ is symmetric. On the other hand, for any g∈C(Fc,C), it is satisfied that ⟨Λ(g), g⟩=E(ug, ug) = 1 2ZV×V a(x, y)ug(x)−ug(y) 2dxdy =1 2ZV×V c(x, y)ug(x)−ug(y) 2dxdy −i1 2ZV×V b(x, y)ug(x)−ug(y) 2dxdy. Considering that ⟨Λ∗(g), g⟩=⟨g, Λ∗(g)⟩=⟨Λ(g), g⟩; it is clear that ⟨ℜ(Λ)(g), g⟩ ≥ 0 and ⟨ℑ(Λ)(g), g⟩ ≤ 0. Now, as in the previous section, if we denote by F0the union of the Visuch that Vi⊆F, then F1=F\F0is the union of the Visuch that Vi∩Fc=∅. For any g∈C(Fc,C), Λ(g) = 0 iff L(ug) = 0 iff ugis constant at each Vi. If the last condition holds, it is clear that gis constant on each Vi∩Fcsuch that Vi⊆F1. Suppose now that g=Pi:Vi⊆F1kiχVi∩Fcwith each ki∈C. Next, we will prove that for this g,ugis piecewise constant on each Vi, which is enough to demonstrate the claim in the proposition about the null space of Λ. By definition, ugis the unique solution to the boundary problem of finding u∈C(V\ F0,C) such that L(u) = 0 on Fand u=gon Fc. We consider the equivalent problem of seeking for v∈C(F1,C) such that L(v) = −L(g) on F1. The unique solution to this last problem is v=Pi:Vi⊆F1kiχVi∩F, because L(X i:Vi⊆F1 kiχVi∩F) = X i:Vi⊆F1 kiL(χVi∩F) = X i:Vi⊆F1 kiL(χVi−χVi∩Fc) = −L(g). Then, ug=Pi:Vi⊆F1kiχVi∩F+g=Pi:Vi⊆F1kiχVi, so ugis piecewise constant on each Vi. Monotonicity on DC networks 33 On the other hand, denoting as LFcthe kernel of LFc, by the definition of Λ, we have that N=LFc+∂K ∂nx. As a consequence, from Proposition 1.4.8, we get that for every x, y ∈Fc: N(x, y) = LFc(x, y) + ∂K ∂nx(x, y) = LFc(x, y) + εy(x)κF(x)−∂2J ∂nx∂ny(x, y). For every x, y ∈Fc, we have that LFc(x, y) = LFc(εy)(x) = ZFc a(x, z)(εy(x)−εy(z)) dz, L(x, y) = L(εy)(x) = ZV a(x, z)(εy(x)−εy(z)) dz, so L(x, y) = LFc(x, y) except when x=y∈δ(F), for which L(x, x) = LFc(x, x) + κF(x). Therefore, we obtain the desired expression of the kernel N. Corollary 1.5.3. If Γis a DC network, then the Dirichlet-to-Neumann map Λis self-adjoint and positive semidefinite. Moreover, N∈C(Fc×Fc). Remark 1.5.4. After fixing a labeling {x1, ..., xn}on the vertex set Vof a network Γ = (V, a), we denote by N∈M|Fc|×|Fc|(C) the matrix corresponding to the Dirichlet-to-Neumann map, Λ, which is named the response matrix of Γ. It is a singular complex symmetric matrix. We can write a response matrix as N=ℜ(N) + iℑ(N), the sum of its real and imaginary parts, with the property that ℜ(N) is positive semidefinite and ℑ(N) is negative semidefinite. As a consequence, for every x∈Fc,N(x, x) = −Py=xN(x, y) has a nonnegative real part and a nonpositive imaginary part. For DC networks, the response matrix Nis real, positive semidefinite and its diagonal entries are nonnegative. Moreover, applying Lemma 1.3.7 to the kernel Jassociated to the Green operator (whose matrix is L(F1;F1)−1), we get that the matrix of ∂2J ∂nx∂nyis L(Fc;F1)L(F1;F1)−1L(Fc;F1)T, because Jis a kernel on F1, and thus the first three terms in the right side of the equation of that lemma are equal to zero. Therefore, N=L(Fc;Fc)−L(Fc;F1)L(F1;F1)−1L(Fc;F1)T. Thus Nis equal to the Schur complement of L(F1;F1) of L(V\F0); (V\F0), which is denoted as L(V\F0); (V\F0)L(F1;F1), (see [51]). 1.6 Monotonicity on DC networks In this section we will review some results of monotonicity of real functions on DC networks (Propositions 1.6.1, 1.6.2, 1.6.3 and 1.6.4), that can be found in [9] and [35]. This will allow 34 Discrete vector calculus on networks us to prove additional properties (see Proposition 1.6.5, Lemma 1.6.7 and Proposition 1.6.8) of the Dirichlet-to-Neumann map of a DC network. The results in this section rely on the order of Rand on the fact that the restriction of the Laplacian of a DC network to the space of real functions C(V) is an endomorphism of C(V), so they can not be generalized to AC networks. In fact, we show a counterexample to Proposition 1.6.5 in the AC case. Let Γ = (V, c) be a DC network and F⊆V. We say that a function u∈C(V) is superharmonic (respectively subharmonic) on Fwhen L(u)≥0 (respectively L(u)≤0) on F. Also, we say that a function u∈C(V) is strictly superharmonic (respectively strictly subharmonic) on Fwhen L(u)>0 (respectively L(u)<0) on F. Proposition 1.6.1 (Hopf’s minimum principle).Let Γ=(V, c)be a DC network, F⊆V a connected subset, and u∈C(V)superharmonic on F. If there is x∗∈Fsuch that u(x∗) = min y∈¯ Fu(y), then uis constant on ¯ Fand it is harmonic on F. Proof. As cis nonnegative, 0≤ L(u)(x∗) = Z¯ F c(x∗, y)(u(x∗)−u(y))dy ≤0. So u(y) = u(x∗) whenever c(x, y)>0, that is, for any y∼x. We can iterate this argument evaluating the Laplacian at any vertex y∈Ffor which we know that u(y) = u(x∗), until we get that u=u(x∗) on ¯ F. As a consequence, L(u) = 0 on F. The two following results are consequences of Hopf’s minimum principle. Proposition 1.6.2 (Monotonicity Principle).Let Γ=(V, c)be a DC network, F⊆Va connected subset, and u∈C(V)superharmonic on F. If δ(F) = ∅, then uis constant on ¯ F and it is harmonic on F. Moreover, if δ(F)=∅and u≥0on δ(F), then either u > 0on F or u= 0 on ¯ F. Proof. The result in the case that δ(F) = ∅is a straightforward consequence of Gauss’ Theorem. Now, in the case that δ(F)=∅and u≥0 on δ(F), if there exists a vertex x∗∈Fsuch that u(x∗) = 0, then u(x∗) = min y∈¯ Fu(y), so by Hopf’s minimum principle, u= 0 in ¯ F. Proposition 1.6.3 (Minimum Principle).Let Γ=(V, c)be a DC network, F⊂Va connected subset such that δ(F)=∅, and u∈C(V)superharmonic on F. Then: min y∈¯ Fu(y)= min y∈δ(F)u(y), and the equality holds if and only if uis constant on ¯ F. Monotonicity on DC networks 35 Proof. We define the function v=u−min y∈δ(F)u(y)χ¯ F∈C(V). As L(χ¯ F) = 0 on F,vis superharmonic on F. The function vis also nonnegative on δ(F), so we obtain the result applying Proposition 1.6.2 to v. In the next result we prove that a strictly superharmonic function on Fcan not have a local minimum in F, as in the continuous vector calculus. Proposition 1.6.4. Let Γ=(V, c)be a DC network, F⊂Vand u∈C(V)strictly superharmonic on F. Then, for any x∈F, there exists y∈¯ Fsuch that y∼xand u(y)< u(x). Proof. Let x∈Fand suppose that for every vertex y∈¯ Fadjacent to x, we have u(x)≤u(y). Then we arrive to the following contradiction: 0<L(u)(x) = Z¯ F c(x, y)(u(x)−u(y))dy ≤0. As a consequence of the Minimum Principle, we obtain the following property for the Dirichlet-to-Neumann map of any DC network. Proposition 1.6.5. Let Γ=(V, c)be a DC network, F⊂V, and let Λ: C(Fc)−→ C(Fc) be the Dirichlet-to-Neumann map of Γand F, whose kernel is N∈C(Fc×Fc). Then, for any x, y ∈Fcsuch that x=y, we have that N(x, y)≤0. Moreover, N(x, y)<0if and only if x∼yor xand yare connected through F. Proof. Given x, y ∈Fcsuch that x=y, we have that N(x, y) = Λ(εy)(x) = ∂uεy ∂nF (x) + LFc(εy)(x). On one hand, LFc(εy)(x)≤0 and LFc(εy)(x)<0 iff x∼y. On the other hand, as K(x, y) = εy(x) = 0, we get: ∂uεy ∂nF (x) = ∂K ∂nx (x, y) = X z∈F c(x, z)K(x, y)−K(z, y)=−X z∈F c(x, z)K(z, y). By Proposition 1.4.8, if x /∈δ(F) or y /∈δ(F), ∂uεy ∂nF(x) = 0. Now, for every z∈Fsuch that z∼x, we denote by Hz⊆Fthe connected component of Fthat contains the vertex z. For any z∈Fsuch that z∼x,x∈δ(Hz)=∅and uεy≥0 on δ(Hz), so we get that K(z, y) = uεy(z)≥0 applying the Monotonicity Principle to uεy, which is harmonic on F. As a consequence, N(x, y)≤0. Moreover, for any z∈Fsuch that z∼x, by the Minimum Principle, K(z, y)>0 iff y∈δ(Hz). Given that xand yare connected through Fiff there exists z∈Fwith z∼x such that y∈δ(Hz), we finish the proof. 42 The inverse conductance problem The discrete version of Calder´on’s problem, called the Inverse conductance problem is concerned with the recovery of the conductance of a given network from the response matrix. Of course, this (discrete) inverse problem is not limited to the realm of numerical reconstruction of conductivities, but makes sense in its own right and can be posed on arbitrary graphs and networks. It was proposed in the last decade of the past century mainly by the Seattle school, led by E.B. Curtis and J. Morrow. The explanation in terms of discrete vector calculus, mimicking the continuous formulation, is more recent, dating back to the last ten years and is based on the work of the MAPTHE group in Barcelona. In fact, if Γ is a network with boundary, i.e., Γ = ( ¯ F, c), the Dirichlet-to-Neumann map is a mimetic discretization of the continuous Dirichlet-to-Neumann map, (as stated in Section 1.5) and hence the resolution of the discrete problem can be interpreted as the reconstruction step of the continuous one. Therefore, with the notations introduced in Section 1.5, in this chapter, we study the following problem, (see [7, 8, 10, 54]). Problem 2.0.2 (Inverse conductance problem).Let Γ = (V, c)be a DC electrical network with unknown conductance c, but with a known topology, G(Γ) = (V, E(Γ)). Let F⊂Vand let Λbe the Dirichlet-to-Neumann map of Γand F. The problem consists in determining c from Λ. 2.1 Background of the problem The (continuous) inverse conductivity problem has received a lot of attention since its introduction in 1980. There are abundant papers dedicated to it, such as [5, 6, 23, 24, 26, 32, 34, 86, 97]. Two of the most studied aspects are the uniqueness of its solution, and in the cases where there is a unique solution, the construction of an algorithm to obtain it. In the case of dimension n= 2, the solution was proved to be unique in [13]. Moreover, an algorithm to recover the conductivity in this case was obtained in [12]. In the case of dimension n≥3, the question of uniqueness in general remains open to this date, although some authors have proved that the solution is unique if further regularity assumptions are added to the problem. For instance, in [40] the uniqueness of the problem was proved if the conductivity and the surface are Lipschitz continuous. Furthermore, an algorithm to recover the solution under this hypothesis was obtained in [39]. Even when the conductivity σcan be uniquely obtained from the Dirichlet-to-Neumann map Λσ, the solution σdoes not depend continuously on Λσin general, so the problem is ill-posed, (see [6, 15]). Because of that, several authors have investigated if knowing some a priori information about σmakes the problem stable. For example, in [14, 75] for the case of dimension n= 2 and in [5] for the case n≥3, the authors proved that if it is a priori known that σis bounded for a certain suitable norm, then σdepends continuously on Λσ, but with this a priori hypothesis we only have the so-called logarithmic stability. Therefore, the problem still exhibits a bad numerical behavior, which represents a severe obstruction for the reconstruction step. In that line of research, we highlight the paper [6] by Alessandrini and Vessella, where they proved that if it is a priori known that there is a known partition of the set Ω with a bounded Background of the problem 43 number of connected subsets satisfying some additional hypothesis such that the conductivity is piecewise constant on that partition, (that is, σis equal to an unknown constant value at each subset), then Calder´on’s problem becomes Lipschitz stable. Furthermore, the Lipschitz constant grows exponentially with the number of subsets in the partition, as demonstrated in [77, 85]. In order to improve the stability of the recovery process, there are authors that have used regularization methods, mainly of Tikhonov type, (see [61, 76, 86]). Other authors have used machine learning techniques, (see [41]). The (discrete) inverse conductance problem has gathered relatively less attention than its continuous counterpart, with papers such as [8, 10, 30, 45, 51, 65, 66]. Additionally, several authors have studied the problem with the goal of obtaining an approximate solution to Calder´on’s problem, (see [23, 24, 26, 27, 28, 62]). The situation in the research about this problem is analogous to the one in the continuous problem. On one hand, there are works that study the uniqueness of the problem, also known as the identification problem, which depends on the graph associated to the electrical network G(Γ). To the best of our knowledge, the statement of this problem for general networks appeared in [47], and was solved under some monotonicity hypothesis, see also [22]. In these works, the authors emphasize the need to formulate network problems using an operational calculus that allows following the developments of the continuum. In fact, the background of most of the authors comes from the field of PDEs. The used operators are the gradient, the normal derivative and the Laplacian, which are sufficient to describe the analogue of the Dirichlet-to-Neumann map and to use the variational approach. The most general framework including the consideration of general (discrete) elliptic operators and a complete vector calculus was presented in [20], where again under monotonicity hypothesis, similar results to the mentioned papers were obtained. The extension of Problem 2.0.2 to the case of recovering the admittance ain an AC network was raised in [30]. In this paper, the authors also consider cases in which the imaginary part of ais not nonpositive (which we do not consider in Definition 1.3.1), i.e. the authors extend the problem to the case in which each edge has a complex weight with positive real part. For this extension, they give a criterion to identify the graphs for which the problem has a unique solution for almost all networks with that topology. In previous works (see [52, 53, 54, 55]), Curtis and Morrow proved that the inverse conductance problem has a unique solution when the network topology is a critical planar graph, and thus, in particular, when it is a well-connected spider graph. They also introduced an explicit method to recover the conductance of a well-connected spider network from a finite number of elementary algebraic operations, which is called the layer peeling method. This method was generalized in [10] to include the case in which there is a Schr¨odinger potential at the vertices. There are other network topologies for which the the solution of the inverse conductance problem is also known to be unique and there is an explicit method similar to layer peeling to obtain the conductance, including the n×ngrids (see [11]), and any tree without vertices of combinatorial degree two, (see [66]). The method introduced in the last reference also allows to identify which tree is the network topology up to vertices of combinatorial degree two, although the method is only valid for trees, because it exploits the fact that the effective resistance between any two nodes coincides with the resistance distance between them. 44 The inverse conductance problem An alternative line of research in the construction of explicit algorithms for solving the inverse conductance problem for some topologies is related to the study of certain Grassmannians. In that line, in [71], an algorithm is proposed to solve the problem for a certain family of networks called standard networks. The values of the solution are obtained as a biratio of Pfaffians constructed from the response matrix. A related algorithm, which works for any well-connected electrical network can be found in [65], although the only example of network in which the conductances are computed is a well-connected spider network with m= 3 boundary nodes. Despite being finite-dimensional, the inverse conductance problem is also severely illposed in general, (see [54]). Among the explicit methods to recover the conductance mentioned so far, the ones in well-connected spider networks and in grids (in [10, 11, 52, 53, 54, 55]) are known to be ill-posed for networks of medium or large size; and for the rest of the methods (in [65, 66, 71]) the stability is not studied and the computational examples of recovery presented are only in networks with small size. Several authors, (see [45]), have developed numerical methods with regularization to recover an approximate solution of the inverse conductance problem with more stability than the mentioned explicit methods. In [45], the inverse problem is reformulated to obtain an equivalent problem in which the goal is to estimate a potential at the vertex set. Then, the problem is solved utilizing a discrete version of the inverse Born series with regularization. The method is tested in 12 ×12 grids. In the experiments, the method converges when the deviation from a constant potential is small; and the method diverges otherwise. Some of the works that solve the discrete inverse problem to approximate the continuous one have also contributed to the study of the stability of the discrete problem and the development of numerical methods to solve it. L. Borcea alongside several collaborators have written several papers in which they approximate the continuous problem using wellconnected spider networks, including [23, 24, 26, 27, 28]. In [27], the authors propose to formulate the discrete problem as an optimization problem which includes a Tikhonov-type regularization and to solve it with an optimization method. The regularization term penalizes the deviation from a reference conductance whose value has to be known and fixed a priori. The experimental results of the method are carried out in networks with moderate size (with 29 or less vertices in the boundary). In the rest of those works ([23, 24, 26, 28]), the conductance is recovered using the layer peeling algorithm ([55]). In order to have stability, the authors limit the size of the networks, choosing the topology with greatest number of boundary nodes such that the algorithm does not yield negative values for the conductance; which generally has fewer than 11 boundary nodes. In other works, the continuous problem is approximated solving the discrete one in grids. For example, in [24, 25], the discrete problem is solved using an algorithm that converges to the real network if and only if it is asymptotically close to a reference network that has to be known and fixed a priori. In [62], the authors solve the discrete problem using a discrete analogous to the complex geometric optics approach. They also use these solutions to obtain a stability estimate for the discrete problem, which is in |log(error)|α, for some α < 0, where error stands for the error in the Dirichlet-to-Neumann map, i.e., the problem is exponentially unstable. In the recent work [38], the authors explore whether knowing a priori the hypothesis Ill-posedness of the inverse conductance problem 45 that the conductance is piecewise constant on a partition with few subsets makes the discrete inverse conductance problem stable. This hypothesis, called the “piecewise constant conductance hypothesis”, mimics the hypothesis of piecewise constant conductivity considered in [6]. They propose to formulate the problem as a polynomial optimization problem, with a regularization term `a la Tikhonov that penalizes the deviation with respect to that hypothesis. The authors present numerous experimental examples in which it is possible to solve the inverse conductance problem with stability in well-connected spider networks satisfying that hypothesis with up to m= 47 boundary vertices, which are larger than the networks considered in the previous literature. Moreover, this work is extended by the same authors in the paper [37]. In that work, they show that the approach in [38] can be used to solve the inverse conductance problem with stability even in some cases in which the piecewise constant conductance hypothesis is not exactly satisfied by the real network. Moreover, they study the variation of the error in the recovered conductance with respect to the penalty parameter, and they use techniques of sum of squares of polynomials to seek for a guarantee that the obtained numerical solution of the polynomial optimization problem is a global minimum. The rest of the chapter is dedicated to review and extend the results of [37, 38] about the inverse conductance problem in well-connected spider networks. 2.2 Ill-posedness of the inverse conductance problem The aim of this section is to prove that the inverse conductance recovery problem is intrinsically severely ill-posed, in order to emphasize the importance of reformulating the problem and seeking for methods that allow us to recover the conductance with stability. This section is a review of [38, Section 2]. We conduct several tests in which we compute the Dirichlet-to-Neumann map of a wellconnected spider network, and then we apply the algorithm in [10] to solve the inverse conductance problem. We recover a conductance that, when the number of boundary vertices is high, widely differs from the one of the original network. This is due to the ill-posedness of the problem: despite the fact that the algorithm is based on explicit formulas, any error in the entries of the response matrix (which are stored with finite precision) could be amplified several orders of magnitude in the algorithm. For the sake of completeness we give here the highlights of the algorithm of [10] that are mainly based on finding solutions of a battery of overdetermined boundary value problems. Each step requires the information obtained in the last one. Let Γ = ( ¯ F, c) be a DC well-connected spider network and let A, B ⊂δ(F) nonempty subsets such that A∩B=∅. Moreover we denote by Rthe set R=δ(F)\(A⊔B), so δ(F) = A⊔B⊔Ris a partition of δ(F). We remark that Rcan be an empty set. For any f∈C(F), g∈C(A⊔R) and h∈C(A), the overdetermined partial Dirichlet–Neumann boundary value problem on Fwith data f, g, h consists in finding a function u∈C(¯ F) such 46 The inverse conductance problem that Lq(u) = fon F, ∂u ∂nF =hon Aand u=gon A⊔R. (2.1) In Figure 2.1 we show the representation of a general overdetermined boundary problem. We fix a labeling in the vertex set of Γ, and we denote by Lits Laplacian matrix, by Nits F B A R Figure 2.1: Boundary partition in an overdetermined boundary value problem. response matrix, and by f,gand hthe vectors associated with f,gand h, respectively. In [10] the authors proved the existence and uniqueness of a solution to this problem for any data f∈C(F), g∈C(A⊔R), h∈C(A) iff |A|=|B|and N(A;B) is invertible. Moreover, if u∈C(¯ F) is the unique solution of the overdetermined partial boundary value problem (2.1), then its associated vector usatisfies u(B) = −N(A;B)−1·L(A;F)·L(F;F)−1·f+N(A;A⊔R)·g−h, u(F) = L(F;F)−1·f−L(F;B)·u(B)−L(F;A⊔R)·g and, clearly, u(A⊔R) = g. We consider also the what we called boundary spike formula. If x∈Rhas a unique neighbour y∈F, then c(x, y) = N(x;x)−N(x;B)·N(A;B)−1·N(A;x). Once we get the value for the conductances on the boundary edges, and taking advantage of the null zone for the solution of Problem (2.1) when f= 0, h= 0 and g=εz, for each z∈A⊔R, we can recover the value of the solution on the set of vertices that are at distance 1 from the boundary. Then, the process follows alternating the knowledge of the conductance and the function value from the boundary to the interior vertex. The following example refers to the case of well-connected spider networks, as represented in Figure 2.2. Example 2.2.1 ([38]).For m= 7,11,15,19,23,27,31 and 35, we start from the wellconnected spider network with mradii and constant conductance c= 1. In all cases, we compute the response matrix Nof the network, and from it we recover the conductance c′ using the explicit formulas from [10]. The algorithm has been implemented in Matlab. Ill-posedness of the inverse conductance problem 47 A R B Figure 2.2: The boundary partition in a well-connected spider network. In Figure 2.3 we show the logarithm of the error in the recovered conductance in the Euclidean norm, log(||c′−c||), for all values of m, where log stands for the decimal logarithm, and the norm of c′−c∈C(Γ) = C(G(Γ)) is the one defined in Remark 1.2.3. Moreover, Table 2.1 displays the error on the conductances. We see that the error is almost zero for m= 7 and increases approximately exponentially with mfrom m= 7 to m= 23. The error keeps increasing with mfor m≥23. 5 10 15 20 25 30 35 -15 -10 -5 0 5 Figure 2.3: Logarithm of the error in the recovered conductance. We show the recovered conductance for m= 19 and for m= 23 in Figures 2.4 and 2.5, respectively. In both figures, the width of each edge is proportional to the absolute value of the recovered conductance c′. For the sake of clarity, the values displayed on each edge have been rounded to the nearest integer within the graphical illustrations. 48 The inverse conductance problem Table 2.1: Error in the recovered conductance. m7 11 15 19 23 27 31 35 ||c′−c|| 1·10−14 4·10−11 3·10−74·10−35·1022·1037·1039·103 Figure 2.4: Recovered network with m= 19 radii in Example 1. Figure 2.5: Recovered network with m= 23 radii in Example 1. Stable reformulation: the discrete piecewise constant conductance hypothesis 49 The error for m= 19 is approximately 3.5·10−3, and we see that the nearest integer to the value of the recovered conductance at every edge is equal to the true value c= 1. However, the error for the next bigger network, the one with m= 23, is approximately 5.2·10. We can see that the value of the recovered conductance is very far from 1 and in some cases even negative, especially in edges that are far from the boundary. For example there is an edge with conductance close to −31. As a conclusion of the performed tests, the recovery of the conductance of a wellconnected spider network is unstable except for small networks. Moreover, the big discrepancies appear on edges that are far away from the boundary. This situation is analogous to the one that appears in the continuous Calder´on inverse conductivity problem, which is severely ill-posed, and the instabilities increase as we move farther away from the boundary, (see [26]). 2.3 Stable reformulation: the discrete piecewise constant conductance hypothesis Calder´on’s problem is ill-posed, but in [6] it was shown that if the hypothesis that the conductivity is piecewise constant on a partition of the set Ω with a bounded number of connected subsets is a priori known, then the problem becomes Lipschitz stable. As in the previous section we have seen that its discrete counterpart is analogously ill-posed, we propose to translate this hypothesis to the discrete setting and to study the conductance recovery knowing a priori this hypothesis. This section is a review and extension of [38, Section 3]. In the discrete case, we say that a conductance is piecewise constant on a partition E=E1⊔···⊔Esif it is constant on each Ei. Of course, as the number of edges is finite, any conductance is inherently piecewise constant on some partition. In this work, we understand that a piecewise constant conductance hypothesis holds if and only if s, the number of subsets in the partition, satisfies s≪ |E|. Note that we do not require for any j= 1, ..., s that the subnetwork with edge set Ejand whose vertex set is the set of vertices of the network which are joined by edges of Ejis connected. Therefore this discrete hypothesis can be seen as a generalization of the strict discrete analogue of the hypothesis in [6] for the continuous problem in which the subsets of the partition must be connected. As demonstrated in the preceding section, even when considering the extreme scenario where the real conductance satisfies the hypothesis with s= 1, it has been observed that the explicit recovery methods that solve the general inverse conductance problem lead to instabilities. That is due to the fact that the methods do not use the information of the hypothesis of being piecewise constant on a particular partition: they do not enforce that the solution must satisfy the hypothesis, nor penalize the deviation with respect to the hypothesis in the recovery process. Consequently, it becomes imperative to develop alternative algorithms that ensure stability. Our proposal is to reformulate the inverse problem as a polynomial optimization problem that includes the deviation in the recovered conductance with respect to being piecewise con- 50 The inverse conductance problem stant on a given partition as a penalty. We formulate the problem for any possible partition E=E1⊔···⊔Esof the set of edges of the real network Γ = ( ¯ F, c), whether its conductance cis piecewise constant on this partition or not. In the case in which s≪ |E|, the penalty term penalizes the deviation with respect to a piecewise constant conductance hypothesis. 2.3.1 Polynomial optimization problem The polynomial optimization problem that we propose to solve the discrete inverse problem can be stated as follows. Problem 2.3.1. [[38]] Let Γ=(¯ F, c)be a well-connected spider DC network with known set of edges E(Γ) but unknown conductance c, let Nbe the kernel of the Dirichlet-to-Neumann map of Γand F, let E(Γ) = E1⊔ ··· ⊔ Esbe a partition and let µ≥0be a penalty parameter. We denote by Γ′= ( ¯ F, c′)the DC network that we want to recover, which must satisfy E(Γ′)⊆E(Γ). We define another unknown DC network Γω= ( ¯ F, ω)such that E(Γω)⊆E(Γ) and ωis piecewise constant on E1⊔···⊔Es. For each z∈δ(F), we define a function uz∈C(V)such that uz=εzon δ(F). The problem consists in determining values of the variables (i) c′(exy) (= c′(x, y) = c′(y, x)) for all exy ∈E(Γ); (ii) ω(Ej)for all j= 1, . . . , s; (iii) uz(x)for all x∈Fand z∈δ(F), which minimize the objective function p=Zδ(F)×δ(F)N(x, z)−ZV c′(x, y) (uz(x)−uz(y)) dy2 dxdz +µ s X j=1 X exy∈Ej (c′(x, y)−ω(Ej))2 (2.2) subject to the constraints gz x:= ZV c′(x, y) (uz(x)−uz(y)) dy = 0 (2.3) for all x∈Fand z∈δ(F); and c′(exy)≥0for all exy ∈E. Let c′be a fixed feasible value for the conductance in the problem, and we denote by L′, Λ′and N′the Laplacian, the Dirichlet-to-Neumann map and the kernel of the Dirichlet-toNeumann map of the recovered network Γ′= ( ¯ F, c′), respectively. Then, for any x∈Fand z∈δ(F) we have that gz x=L′(uz)(x). Because of that, the constraints (2.3) are equivalent to that, for each z∈δ(F), uz∈C(V) is a solution to the boundary value problem (1.7) for g=εz, that is, the boundary value problem of finding u∈C(V) such that L′(u) = 0 on F, u =εzon δ(F),(2.4) Stable reformulation: the discrete piecewise constant conductance hypothesis 51 Now, for each x, z ∈δ(F), the evaluation at xof the normal derivative of uzwith respect to Fin Γ′is equal to ∂uz ∂nF (x) = ZV c′(x, y) (uz(x)−uz(y)) dy =ZF c′(x, y) (uz(x)−uz(y)) dy, and as a consequence of Remark 1.4.4, we have that ∂uz ∂nF (x) = ∂uεz ∂nF (x)=Λ′(εz)(x) = N′(x, z). Then, the objective function (2.2) can be rewritten as p=||N′−N||2 Fr +µ||c′−ω||2,(2.5) so a solution of Problem 2.3.1 minimizes the squared Frobenius norm of the difference between the response matrix N′of the recovered network and Nplus a penalty term which is the squared norm (defined in Remark 1.2.3) of the difference between the recovered conductance and any piecewise constant conductance on E=E1⊔···⊔Esmultiplied by the penalty parameter µ. In the context of Tikhonov-like regularization methods the parameter µis often called regularization parameter (see [61, 76, 86]). Remark 2.3.2. In Problem 2.3.1, we allow the possibility that c′(x, y) = 0 for some exy ∈ E(Γ), and thus E(Γ′)⊊E(Γ). As we have discussed, this is not a problem for the objective function pto satisfy (2.5), even if some subset of vertices of Fis isolated in Γ′. Nevertheless, if we know a priori a value λ > 0 such that c(exy)≥λfor all exy ∈E(Γ), we can slightly modify the formulation of the problem, adding the restriction c′(exy)≥λfor all exy ∈Eif we want to ensure that the topology of Γ′and Γ are the same. In that case, Γ′is a network with boundary, so uz=uεzfor each z∈δ(F). Note that this a priori information is analogous to the known lower bound for the conductivity in the formulation of Calder´on’s problem. We define the function f: [0,∞]−→ [0,∞] which assigns to each µthe value of the minimum of pin a solution to Problem 2.3.1, i.e., f(µ) = min {c′,ω}||N′−N||2 Fr +µ||c′−ω||2. We also define has the minimum value of ||N′−N||2 Fr among the conductances c′that are piecewise constant on the partition E=E1⊔···⊔Es. Note that, for every µ, we have that f(µ)≤min {c′,ω:c′=ω}||N′−N||2 Fr +µ||c′−ω||2=h. By the last inequality, for every µ, the evaluation of the term µ||c′−ω||2in a solution to Problem 2.3.1 must be lower than or equal to h. Then, for any µ > 0, we have that f(µ) = min c′,ω:||c′−ω||≤qh µ||N′−N||2 Fr +µ||c′−ω||2. From that expression, we see that the limit case of µ→ ∞ corresponds with enforcing the hypothesis that the recovered conductance is piecewise constant on E=E1⊔ ···⊔ Es 58 The inverse conductance problem 0 10 20 30 40 50 60 0 1 2 3 4 5 6 7 8 9 N N Figure 2.7: Maximum log ||c′−c|| ||N′−N||Fr in recovered conductance of 100 networks with m= 11 and s= 1,...,55. (Example 2.4.2). between 1 and 13, the error in the recovered conductances is very low in all the networks. Besides, for values of sbetween 14 and 22, the error is greater in some cases, but smaller than the norm of the real conductances. Finally, for s > 23, there are networks in which the recovered conductances have a great error. We finish this work by considering again the test of Example 2.2.1 but with our approach. These results will show the robustness of our method, since as we will see all the cases are stable and even if we perturb the response matrix we can recover the conductance. Example 2.4.3. For m= 7,11,15,19,23,27,31,35,39,43 and 47,we start from the wellconnected spider network with mradii and constant conductance c= 1. In all cases, we compute the response matrix Nof the network, and from it we recover the conductance c′ obtaining an approximation to Problem 2.3.1 with s= 1. Additionally, for each mwe repeat 10 times the process of adding random perturbations to each entry of Nsampled from a uniform distribution in each of the intervals [−10−8,10−8],[−10−7,10−7]and [−10−1,10−1], and then recovering the conductance with the perturbed matrix. As in Example 2.4.1, we set µ= 1, we recover the conductance c′, we compute the error ||c′−c||, and we compute the quotient ||c′−c|| ||N′−N||Fr . In the first row of Table 2.4 we show the error in the recovered conductance in the unperturbed case. As we see the error is very small, especially in comparison with the results displayed in Table 2.1. We can initially see that for m= 7,11 the error is smaller in the explicit case, however for mbigger or equal than 15, when the explicit case becomes unstable, not only the error is smaller with our algorithm but also the recovered value accurately approximates the spider network with constant conductance 1, see Figure 2.8 for the case m= 23. In this last case, observe that the maximum error in the conductance values is 1.4·10−8. In the rest of the entries of Table 2.4 we show, for each network and each interval of Stable recovery of piecewise constant conductances 59 perturbation, the maximum error in the 10 recovered networks. Moreover, in Table 2.5, we display the maximum of the values of ||c′−c|| ||N′−N||Fr . As we can see the results are similar to the ones obtained by considering the unperturbed N,except for the case where the magnitude of the perturbation is 10−1. In this case, the error is much bigger but still comparable with the magnitude of the perturbation performed. Besides, the value for the conductance is close enough to 1, see Figure 2.9. This also shows the robustness of our algorithm. We can compare these results in Table 2.4 with the ones obtained in [55, Section 13], where a similar experiment was conducted only for m= 15. There, the authors perturbed the entries of Nrandomly by terms of magnitude 10−8obtaining the conductance values with an error of up to 0.5. Also, the authors perturbed the entries of Nrandomly by terms of magnitude 10−7obtaining several negative values in the conductance. In contrast, using our algorithm the maximum error in the conductance of an edge is 1.1·10−8for perturbations of order of magnitude 10−8; and the maximum error in the conductance is 8.7·10−8for perturbations of order of magnitude 10−7. We have continued this experiment with perturbations of order of magnitude 10−1, obtaining a conductance whose maximum error is 7.8·10−2. Figure 2.8: Recovered network with m= 23 radii in Example 2.4.3. Table 2.4: Maximum error in the recovered conductance with one significant digit. Interval \m7 11 15 19 23 27 31 35 39 43 47 Unperturbed 2 ·10−84·10−89·10−81·10−72·10−73·10−74·10−75·10−76·10−78·10−79·10−7 [−10−8,10−8] 4 ·10−86·10−81·10−72·10−73·10−74·10−74·10−76·10−77·10−78·10−71·10−6 [−10−7,10−7] 3 ·10−74·10−75·10−76·10−76·10−71·10−67·10−77·10−79·10−71·10−62·10−6 [−10−1,10−1] 3 ·10−14·10−14·10−14·10−13·10−18·10−19·10−19·10−16·10−18·10−18·10−1 60 The inverse conductance problem Figure 2.9: Recovered network with m= 35 radii in Example 2.4.3 and perturbations in the interval [−10−1,10−1]. (α= 0.96). Table 2.5: Maximum ||c′−c|| ||N′−N||Fr in the recovered conductance with two significant digits. Interval \m7 11 15 19 23 27 31 35 39 43 47 Unperturbed 2.8 3.9 4.7 5.4 6.0 6.6 7.1 7.6 8.0 8.5 8.9 [−10−8,10−8] 2.7 4.8 5.1 5.7 6.3 6.7 7.6 7.8 8.1 8.7 9.0 [−10−7,10−7] 2.5 3.4 3.9 4.6 4.9 5.5 5.8 6.2 6.8 7.3 7.8 [−10−1,10−1] 2.5 3.4 3.8 4.1 4.2 5.1 5.5 5.7 5.4 6.1 6.4 2.5 Error Variation with respect to the penalty parameter This section is a review of [37, Section 2]. The formulation of Problem 2.3.1 introduces the deviation with respect to the piecewise constant hypothesis as a penalty rather than imposing the hypothesis and minimizing the difference between N′and N. As µ→ ∞, the formulation of the problem corresponds with this last scenario. As discussed in the previous section, in the case that the real conductance cis piecewise constant on the partition E=E1⊔···⊔ Es, with s≪ |E|, the solution of the problem is almost equal for every µ > 0, recovering a conductance that is very close to c, except when µ→0, that is when the problem becomes unstable. Therefore, in that case, the penalty formulation for any value of µthat is big enough gives almost the same experimental results as the approach of imposing the hypothesis and minimizing the difference between N′and N. Nevertheless, the penalty formulation has the advantage of making possible to consider Error Variation with respect to the penalty parameter 61 intermediate values of µ∈(0,∞) that allow us to obtain a good approximation to the conductance avoiding the instabilities in cases in which the conductance is not piecewise constant on the partition E=E1⊔···⊔Es, as we can see in the following example. Example 2.5.1. We consider the DC spider network Γ = ( ¯ F, c)with m= 19 radii, see Figure 2.10, and we show how the error in recovering the conductance varies with µwhen a piecewise constant conductance hypothesis which does not hold in the network is used. Figure 2.10: Well-connected spider network Γ with m= 19. The conductance is piecewise constant on a partition E=E1⊔E2⊔E3⊔E4, with c(E1) = 1, c(E2) = 5, c(E3) = 2 and c(E4) = 4. We run our algorithm assuming that the conductance is piecewise constant on a different partition E=A1⊔A2⊔A3, with A1=E1,A2=E2and A3=E3⊔E4. We obtain a numerical approximation to a local minimum of Problem 2.3.1 with this false hypothesis for the following 498 values of µ:µ= 0, µ= 10−10j,µ= 10−8j,µ= 10−6j, µ= 10−4jand 10−2jfor j= 1,2, ..., 99, µ= 1 and µ= 105. The error in the recovered conductances ||c′−c|| is shown in Figure 2.11 for the values such that µ≤5·10−7with a linear interpolation. Additionally, the error ||c′−c|| is shown in Figure 2.12 in a logarithmic scale with a linear interpolation for all the positive values except µ= 105, for which the recovered conductance is almost equal to the one recovered with µ= 1. In all figures, the recovered values of the conductances have been rounded with one decimal digit for the sake of clarity. For µ= 0, we obtain the network in Figure 2.13. The error is 7.8519, which is much higher than for any of the other values of µ. Despite in this case we have the minimum difference with respect to the data ||N′−N||Fr = 5.9512 ·10−6, and thus also this is the solution at which the evaluation of pis minimum (equal to 3.5417 ·10−11), the recovered 62 The inverse conductance problem Figure 2.11: Error in the recovered conductance as a function of µ. Figure 2.12: Error in the recovered conductance as a function of log(µ). network differs a lot from the real one, being max |c−c′|= 2.9997, because the inverse conductance problem without regularization is ill-posed. When we recover the conductance for the problem with a positive value of µ, the error decreases drastically, and in µ= 4 ·10−10 the error is minimum, ||c′−c|| = 2.3567. In Figure 2.14, we show the recovered network for this value. Despite the error in the data, ||N′−N||Fr = 1.0791 ·10−5, is greater than for µ= 0, the recovered conductance is much closer to the real one, with max |c−c′|= 1.3334. The evaluation of pis equal to 2.6808·10−9. For µ > 4·10−10, the error monotonically increases with µ. From µ= 4.7·10−1onwards, the recovered conductance almost does not vary with µ, being almost piecewise constant on the partition E=A1⊔A2⊔A3, with c′(A1) = 0.9999, c′(A2) = 5.0145 and c′(A3) = 2.1943. The error is ||c′−c|| = 3.7250. The deviation with respect to the data is maximum, ||N′−N||Fr = 0.0078, the evaluation of pis equal to 6.0897 ·10−5, and max |c−c′|= 1.8057. Error Variation with respect to the penalty parameter 63 Figure 2.13: Recovered network with µ= 0. Figure 2.14: Recovered network with µ= 4 ·10−10. The recovered conductance for µ= 105can be seen in Figure 2.15, and in Table 2.6 there is a summary of the results for this value of µ, and also for µ= 0 and for the value of µwith minimum error. This example illustrates that if we consider a piecewise constant conductance hypothesis on a given partition that does not suit the real network, but the real conductance is not far from a piecewise constant conductance in this partition, the error in the recovered conductance is lower when introducing the penalization (µ > 0) than if we do not use it 64 The inverse conductance problem Figure 2.15: Recovered network with µ= 10000. Table 2.6: Error in the recovered conductance for different values of µ. µ||c−c′|| max{|c−c′|} ||N′−N||Fr 0 7.8519 2.9997 5.9512 ·10−6 4·10−10 2.3567 1.3334 1.0791 ·10−5 105(µ→ ∞) 3.7250 1.8057 7.8037 ·10−3 (µ= 0). These results support using a penalty term in our formulation of Problem 2.3.1 and will be useful in many applied inverse conductance problems. From an applied perspective, it is reasonable to work with a piecewise constant conductance hypothesis that may not be entirely accurate but closely approximates reality. This can be intentional, such as when using an approximate piecewise constant model, or unintentional, because we are recovering a network whose conductance should be piecewise constant on a partition under normal circumstances, but may exhibit perturbations in certain unknown edges. In the given example, we achieve the minimum error for an intermediate value of µ∈(0,∞) for which there is a compromise between deviating with respect to the data Nand with respect to the piecewise constant conductance hypothesis. In the solution with µ= 4 ·10−10, we see that the recovered conductance c′is close to being constant on A1and on A2, on which the real conductance is constant, while c′is far from being piecewise constant on A3, and the value of c′at any edge of E3is lower than the value of c′at any edge of E4. This suggests the idea of choosing a finer partition than the original one for the subsets on which the solution is far from being constant. Then, we would recover the conductance again Problem 2.3.1 by considering this refined partition seeking a solution with a lower error. 2.6. OPTIMALITY GUARANTEES OF THE RECOVERED CONDUCTANCES 65 2.6 Optimality guarantees of the recovered conductances This section is a review of [37, Section 3]. In the previous section we have shown an example in which obtaining an approximation to a local minimum t∗∈Aof Problem 2.3.1 with a value µ > 0 and a partition E=E1⊔ ···⊔ Eswith s≪ |E|such that cis not piecewise constant on it allow us to recover an approximation of cwith some stability. Recall that, in this case of a false piecewise constant conductance hypothesis, a solution ˆ t∈Ato Problem 2.3.1 must satisfy p(ˆ t)>0. In this case, we do not know a priori the value of p(ˆ t), so we can not tell whether t∗is an approximation of a global minimum or not just from the value of p(t∗), even if the recovery is stable. Nevertheless, we can apply techniques of Sum of Squares (SOS) decompositions of polynomials [81] to this problem to try to find a guarantee that t∗is an approximation to a global minimum, and as a consequence, an approximation to a solution to Problem 2.3.1. SOS decompositions are relaxations used in polynomial optimization to obtain a lower bound for a real polynomial in a real algebraic set. We say that a polynomial is SOS if it can be written as a sum of squares of real polynomials and we denote by I(V(J)) the ideal of polynomials vanishing on V(J). We denote by tthe vector containing all the variables of Problem 2.3.1, and we define the coordinate ring of the algebraic set V(J) as the quotient ring R[t]/I(V(J)). We formulate the following SOS problem, which is a particular case of the main problem studied in [56]. Problem 2.6.1. Given a bound d∈N, a quartic p, an algebraic set V(J), and a value z≥0, is there any polynomial q such that p(t)−z=q(t)in R[t]/I(V(J)); qis SOS, and deg(q)≤2d? Let z=p(t∗) for t∗∈Aand suppose that Problem 2.6.1 has an affirmative answer for p,V(J), zand some d, then p(t)≥zin V(J). Therefore, t∗is a global minimum of pin A and thus a solution to Problem 2.3.1. In Example 2.6.2, we will show a network in which we are able to guarantee that a minimum to Problem 2.3.1 is global by finding an affirmative answer to Problem 2.6.1. It could be possible that there is a global minimum t∗∈Ato Problem 2.3.1 such that Problem 2.6.1 has a negative answer for V(J), z=p(t∗) and any d, because for most algebraic varieties there exist nonnegative polynomials which are not SOS in the coordinate ring. Nevertheless, p−p(t∗) in V(J) can always be approximated by SOS polynomials, and the minimum degree of those polynomials depends on the closeness of the approximation [56], (see also [73] for more details). Given a Gr¨obner basis of I(V(J)), Problem 2.6.1 reduces to a semidefinite program (SDP) [56]. It is equivalent to find a symmetric positive semidefinite matrix Qsuch that the normal form of p−z−uTQu in the Gr¨obner basis is zero, where u is a vector whose entries are the standard monomials corresponding to the Gr¨obner basis, (that is, the monomials which are not divisible by any leading term of the polynomials in that basis) with degree at most d, see [81]. In general, it is computationally complex to determine a Gr¨obner basis of the real radical I(V(J)) of J. Alternatively, we can check if p−zis sum of squares in R[t]/J, which is a 66 The inverse conductance problem SDP problem that only requires a Gr¨obner basis of J, and obtaining an affirmative answer to this problem is a sufficient condition for obtaining an affirmative answer to Problem 2.6.1, because the evaluation of a polynomial which is equal to p−zin R[t]/J at any point of V(J) is equal to the evaluation of p−zat that point. Even with the relaxation of the above paragraph, the computation of a Gr¨obner basis of the ideal Jis computationally expensive when Jis the ideal of a spider network of a medium or large number of radii, because the number of variables of Problem 2.3.1 and the number of polynomials in (2.3) increase with the number of radii. Nevertheless, the ideal Jdepends only on the number of radii, and it does not depend on the Dirichlet-to-Neumann matrix nor on the partition used in Problem 2.3.1, so once a Gr¨obner basis of Jcorresponding to a number of radii is computed, it could be used to check if a local minimum of any case of Problem 2.3.1 in a spider network with this number of radii is a global minimum. Example 2.6.2. We consider the spider network Γ=(¯ F, c)with m= 3 radii in Figure 2.16, we recover its conductance using a piecewise constant conductance hypothesis which does not hold in the network, and we check if the obtained solution is a global minimum of Problem 2.3.1. Figure 2.16: Real network with m= 3. In the real network, we have c(x1, x4) = 1, c(x2, x4) = 2 and c(x3, x4) = 3. The Laplacian matrix of Γ is L=    100−1 020−2 003−3 −1−2−3 6     , and its Dirichlet-to-Neumann matrix is N=1 6  5−2−3 −2 8 −6 −3−6 9  . We set µ= 1 and we obtain a numerical approximation to a local minimum of Problem 2.3.1 under the hypothesis that the conductance is piecewise constant on E=E1⊔E2, with E1={ex2x4, ex1x4}and E2={ex3x4}; which is false in Γ. In Problem 2.3.1, we do not include Optimality guarantees of the recovered conductances 67 the variable ω(E2), nor the term (c′(x3, x4)−ω(E2))2in p, since as E2only has one edge, in the solution we will have ω(E2) = c′(x3, x4) trivially. The problem is to minimize p=c′(x1, x4)−c′(x1, x4)ux1(x4)−5 62+−c′(x2, x4)ux1(x4) + 1 32 +−c′(x3, x4)ux1(x4) + 1 22+−c′(x1, x4)ux2(x4) + 1 32 +c′(x2, x4)−c′(x2, x4)ux2(x4)−4 32+ (−c′(x3, x4)ux2(x4) + 1)2 +−c′(x1, x4)ux3(x4) + 1 22+ (−c′(x2, x4)ux3(x4) + 1)2 +c′(x3, x4)−c′(x3, x4)ux3(x4)−3 22+ (c′(x1, x4)−ω(E1))2+ (c′(x2, x4)−ω(E1))2. subject to      g1 4:= −c′(x1, x4)+(c′(x1, x4) + c′(x2, x4) + c′(x3, x4))ux1(x4)=0 g2 4:= −c′(x2, x4)+(c′(x1, x4) + c′(x2, x4) + c′(x3, x4))ux2(x4)=0 g3 4:= −c′(x3, x4)+(c′(x1, x4) + c′(x2, x4) + c′(x3, x4))ux3(x4)=0, and c(x, y)≥0 for all exy ∈E. Using an interior point method, we obtain a local minimum t∗such that p(t∗) = 0.1995, and the values of all the variables in t∗are c′(x1, x4) = 1.1486, c′(x2, x4)=1.5765, c′(x3, x4) = 3.4764, ω(E1)=1.3625, ux1(x4) = 0.1852, ux2(x4) = 0.2542 and ux3(x4) = 0.5606. We define the ideal J=⟨g1 4, g2 4, g3 4⟩. We choose the degree reverse lexicographic order with c′(x1, x4)> c′(x2, x4)> c′(x3, x4)> ux1(x4)> ux2(x4)> ux3(x4), and we compute the Gr¨obner basis J=⟨h1, h2, h3, h4, h5, h6⟩of Jwith respect to that monomial order using the gbasis function in Matlab. The polynomials of the basis are                          h1=c′(x2, x4)−c′(x1, x4) + c′(x3, x4) + c′(x1, x4)ux1(x4)−c′(x2, x4)ux2(x4) −2c′(x2, x4)ux3(x4)−c′(x3, x4)ux3(x4), h2=c′(x2, x4)ux1(x4)−c′(x2, x4) + c′(x2, x4)ux2(x4) + c′(x2, x4)ux3(x4), h3=c′(x3, x4)ux1(x4)−c′(x3, x4) + c′(x2, x4)ux3(x4) + c′(x3, x4)ux3(x4), h4=c′(x1, x4)ux2(x4)−c′(x2, x4) + c′(x2, x4)ux2(x4) + c′(x2, x4)ux3(x4), h5=c′(x3, x4)ux2(x4)−c′(x2, x4)ux3(x4), h6=c′(x1, x4)ux3(x4)−c′(x3, x4) + c′(x2, x4)ux3(x4) + c′(x3, x4)ux3(x4). Then, we solve Problem 2.6.1 for p,z=p(t∗) and d= 2, but with the relaxation that consists in substituting the coordinate ring R[t]/I(V(J)) by R[t]/J. That is, we check if there is a symmetric positive semidefinite matrix Qsuch that the normal form of p−0.1995−uTQu in ⟨h1, h2, h3, h4, h5, h6⟩is null, where uis a vector whose entries are the standard monomials with degree at most 2 corresponding to ⟨h1, h2, h3, h4, h5, h6⟩. Using the function findbound from SOOSTOOLS, a toolbox of Matlab for solving sum of squares programs [80], and the SDP solver SeDuMi [103], we obtain an affirmative answer to the raised question. 74 Simultaneous recovery of the topology and admittance of a network Any NNLS problem is a convex quadratic optimization problem, (see [92]), so every local minimum of it is a global minimum. We can obtain a solution Γ to Problem 3.1.2 calculating a minimum of its associated NNLS problem with an interior point method. The interior point methods are among the main numerical algorithms used to solve NNLS problems, (see [43]). We denote the numerical solution Γ with error rms ≡rms(Γ,u,s) obtained from Eand (u,s) as [Γ,rms] = network recovery(E, u,s). A sufficient condition that implies that Problem 3.1.2 has a unique solution is that m≥|E| |V|and κ(ME,u)<∞,i.e., the condition number of ME,uis finite, (see [92]). We will require in Section 3.6 that the data sets used to test the sparse network recovery algorithm satisfy m≥|E| |V|. Nevertheless, often the condition κ(ME,u)<∞is not satisfied, and thus there are multiple solutions to Problem 3.1.2; as seen in Example 3.1.1, in which there are multiple solutions with zero error. As we will see in Section 3.6, in cases in which the pair (u,s) contains voltage and power data corresponding to an electrical network with some error, the value of the condition number κ(ME,u) is finite but it is very high, so Problem 3.1.2 has a unique solution but it is severely ill-posed. 3.2 Reformulation of the problem: Recovery of a sparse electrical network This section is a review of the beginning of [88, Section 4]. As we have discussed in the previous section, given a data data pair (u,s) and a set of edges E, the Problem 3.1.2 of recovering a network Γ with minimum error such that E(Γ) ⊆Eis ill-posed. Because of that, even if there is a solution Γ∗to the exact Problem 3.0.2 whose topology is much more sparse than (V, E), i.e.,|E(Γ∗)|≪|E|, solving Problem 3.1.2 we usually get a solution whose topology is (V, E). If the number of edges in Eis high, a solution with that topology is not efficient for applications. We are interested in recovering a sparse network such that the fitting error to the data is below a fixed tolerance. Such a network would allow the efficient and accurate resolution of usual problems in electrical networks which require the admittance and topology. Those applications include failure identification, power flow optimization or generation scheduling [57]. We formulate the following problem of recovering a sparse network. Given a fixed tolerance, we seek to recover a network such that its rms is below this tolerance and none of the networks with the same set of vertices as our network and a subset of its edges has a rms below the tolerance. Problem 3.2.1 ([88]).Let Vbe a finite set of vertices, let Ebe a set of edges, let 0<|u|min ≤ |u|max be positive values, let m∈N∗, let u,s∈C(V, Cm), respectively u,s∈C(V, Rm), such that |u|min ≤ |uj| ≤ |u|max for all j= 1, . . . , m and let tol >0be a tolerance. Determine an AC network Γ = (V, a), respectively a DC network Γ = (V, c), with set of edges E(Γ) ⊆E such that rms(Γ,u,s)≤tol and Γis “minimal” in the following sense: Given any electrical network Γ′= (V, a′), respectively Γ′= (V, c′), with edge set E(Γ′), we have that 1. If E(Γ′) = E(Γ),then rms(Γ′,u,s)≥rms(Γ,u,s). 3.3. SPECTRAL NETWORK SPARSIFICATION 75 2. If E(Γ′)⊊E(Γ),then rms(Γ′,u,s)>tol. Remark 3.2.2. In particular, we have rms(Γ′,u,s)>tol ≥rms(Γ,u,s) if E(Γ′)⊊E(Γ). However, notice that there could be an electrical network E(Γ′) = (V, a′) such that rms(Γ′,u,s)<rms(Γ,u,s) and E(Γ′)⊂ E(Γ). A first naive idea to solve Problem 3.2.1 could be to recover a network Γ solving Problem 3.1.2 with the set of edges E,i.e., [Γ,rms] = network recovery(E, u,s), and then to remove from E(Γ) the edges whose admittance values are close to zero. However, this approach presents some problematic issues. First, let Γ∗be a solution to Problem 3.2.1, with set of edges E(Γ∗). As we will see in Section 3.6, if E(Γ∗) is much smaller than E, then usually the condition number of the operator associated with the network recovery Problem 3.1.2 using set E,κ(ME,u), is much bigger than the condition number of the operator associated with the network recovery Problem 3.1.2 using set E(Γ∗), κ(ME(Γ∗),u). Then, the values of the admittance of Γ at the edges of E\E(Γ∗) are usually far from zero. For instance, in Example 3.3.4, solving the Problem 3.1.2 with the edge set E(KV) = {exy, exz, eyz}, we can get solutions with zero error such that the values of the admittance at all edges of E(KV) are far from zero, despite the fact that there are solutions with zero error and less than three edges. Second, in Γ could exist edges with admittance close to zero whose removal would lead to a network which would not correctly fit the data (see Example 3.6.1). In order to avoid those problems, the algorithm that we propose in Section 3.5 algorithm uses techniques of spectral sparsification of networks in order to remove edges from networks. 3.3 Spectral network sparsification This section is a review of [88, Subsection 4.1]. Spielman and Teng introduced the notion of spectral sparsification of a real weighted graph, (that is, a DC network), in [95], (see also the subsequent papers [16, 93, 94] on this topic). Definition 3.3.1 ([93]).For ε > 0, we say that a DC network Γ′= (V, c′) with energy E′is an ε-approximation of a DC network Γ = (V, c) with energy Eif for all u∈C(V): 1 1 + εE(u, u)≤ E′(u, u)≤(1 + ε)E(u, u).(3.5) The energy of an AC network Γ = (V, a), with a=c−ib and c, b ∈C+(E(Γ)), is a complex bilinear form, so we can not apply Definition 3.3.1 to it. Nevertheless, we can apply this definition separately to its conductance and susceptance networks, Γc= (V, c) and Γb= (V, b). We introduce the following definition. Definition 3.3.2. For ε > 0, we say that an AC network Γ′is an ε-approximation of an AC network Γ if the conductance and susceptance networks of Γ′are ε-approximations of the conductance and susceptance networks of Γ, respectively. 76 Simultaneous recovery of the topology and admittance of a network Algorithm 1 Γ′=Sparsify(Γ, ε). Set t= 8|V|·log(|V|)/ε2,c′= 0, and E(Γ′) = ∅. for each edge exy ∈E(Γ) do Assign to edge exy a probability pxy proportional to c(x, y)re(x, y). end for Take tsamples independently with replacement from E(Γ), and each time the edge exy is sampled, increase the value of c′(x, y) and c′(y, x) by c(x, y)/tpxy, (and as a consequence, add the edge exy to E(Γ′) if it is the first time that exy is sampled). In [16] there is a procedure (Algorithm 1) that can be used to construct a sparse approximation Γ′= (V, c′) of a DC network Γ = (V, c) such that E(Γ′)⊆E(Γ). Algorithm 1 is not guaranteed to produce an ε-approximation of Γ, but in [16] there is a proof of the following theorem: Theorem 3.3.3 (Batson, Spielman, Srivastava, Teng).Let Γbe a DC network, let ε∈R, 0< ε ≤1and let Γ′=Sparsify(Γ, ε). Then Γ′is an ε-approximation of Γwith probability at least 1/2. Note that the edges that are removed in Algorithm 1 are the ones that are never sampled. The choice of the sampling probabilities in the algorithm has an interesting physical interpretation. By (1.13), for each edge exy ∈E, the probability of sampling it, pxy, is proportional to the dimensionless ratio c(x, y)re(x, y) = c(x, y) ce(x, y)=c(x, y) c(x, y) + ce \exy (x, y)∈(0,1], where ce \exy (x, y)≥0 is the effective conductance between xand yin the network Γ \exy obtained from Γ by removing the edge exy, which is equal to the contribution to the effective conductance ce(x, y) of the paths between xand ythrough the rest of vertices of the network Γ. The probability of choosing edge exy in each sample is high if the contribution of the value c(x, y) to the effective conductance between xand yin Γ, ce(x, y), is very important, that is, if c(x, y) is big compared to ce \exy (x, y). The limit case is that in which the removal of exy isolates xand y, in which ce \exy (x, y) = 0, so c(x, y)re(x, y) = 1; and thus the probability of keeping exy in Γ′is the highest possible. The probability pxy is low in the opposite case, that is, when c(x, y)≪ce \exy (x, y). In that case removal of edge exy does not significantly affect the effective conductance between xand y, because ce \exy (x, y)≈ce(x, y). In that case, the probability of keeping exy in Γ′is low. Example 3.3.4. We consider the DC network in Figure 3.2, with conductance cwhose values at each edge are given in Table 3.1. In the same table we indicate the sampling probabilities calculated for each edge in Algorithm 1. The values of the conductance at edges {x1, x2}and {x3, x4}are two orders of magnitude smaller than at the rest of edges, nevertheless, edge {x3, x4}is crucial because it is the only 3.4. SPARSIFICATION OF RECOVERED ELECTRICAL NETWORKS 77 Figure 3.2: Topology of the network in Example 3.3.4. Table 3.1: Conductances and sampling probabilities of the edges in the network. Edges {x1, x2} {x1, x3} {x2, x3} {x3, x4} {x4, x5} {x4, x6} Conductance 0.5797 75.980 75.980 0.4698 94.599 79.909 Conductance times effective resistance 0.0150 0.9925 0.9925 1 1 1 Sampling probability 0.0030 0.1985 0.1985 0.2 0.2 0.2 connection between vertices x3and x4, so it has a great probability of being sampled to form any sparse approximation of the network, while edge {x1, x2}is expendable, because its conductance c(x1, x2) is equal to only 1.5% of the effective conductance between nodes x1and x2. The current can flow from node x1to node x2with much greater ease by edges {x1, x3}and {x2, x3}, so the sampling probability of {x1, x2}is close to zero. In the case of an AC network Γ = (V, a), we will denote by Γ′=Sparsify(Γ, ε) an AC network constructed following the next procedure. First, we apply Algorithm 1 separately to the conductance and susceptance networks, Γcand Γb, of Γ; getting Γ′ c= (V, c′) and Γ′ b= (V, b′), respectively. Then, Γ′= (V, a′) = (V, c′−ib′). Note that E(Γ′) = E(Γ′ c)∪E(Γ′ b), so in the sparsification process of an AC network we remove the edges erased in the sparsification of both Γcand Γb. By definition, Γ′will be an ε-approximation of Γ iff Γ′ cis an ε-approximation of Γcand Γ′ b is an ε-approximation of Γb. By Theorem 3.3.3, if 0 < ε ≤1, then Γ′is an ε-approximation of Γ with probability at least 1 4. 3.4 Sparsification of recovered electrical networks This section is a review of [88, Subsection 4.2]. Once we have a procedure to sparsify any network, the key observation to develop our algorithm of sparse network recovery is that spectral sparsification is guaranteed to preserve the fitting properties of a network to some extent. We introduce some notation for the main result of the chapter in the case of DC networks. Let Γ = (V, c) be a DC network with Laplacian Land let u,s∈C(V, Rm), such that 0<|u|min ≤ |uj| ≤ |u|max for all j= 1, . . . , m. For each j= 1, ..., m, we denote as QΓ,uj the linear operator on C(V) defined for each v∈C(V) as QΓ,uj(v) = ujL(ujv). Clearly, QΓ,ujis a self-adjoint and positive semidefinite operator. Now, we denote as QΓ,uthe linear operator on C(V, Rm) defined for each (v1, ..., vm)∈C(V, Rm) as QΓ,u(v1, ..., vm) = 78 Simultaneous recovery of the topology and admittance of a network (QΓ,u1(v1), ..., QΓ,um(vm)). For any v= (v1, ..., vm),w= (w1, ..., wm)∈C(V, Rm), we have that ⟨QΓ,u(v),w⟩=Pm j=1 RVL(ujvj)ujwjdx =Pm j=1 RVujvjL(ujwj)dx =⟨v,QΓ,u(w)⟩, so the operator QΓ,uis self-adjoint. From the same expression, when v=w, we can see that QΓ,uis also positive semidefinite. We denote by 1m= (χV, ..., χV)∈C(V, Rm) the vector function whose value is equal to 1 at all vertices. Note that QΓ,u(1m) = ME(Γ),u(c). For each j= 1, ..., m, we denote as u−1 j∈C(V) the function defined for each x∈Vas u−1 j(x) = 1/uj(x). We also define the vector function ϕu=RVu−1 1dx ||u−1 1||2u−1 1, ..., RVu−1 mdx ||u−1 m||2u−1 m∈C(V, Rm). Our main original result consists in the following upper bound for the rms of any sparse approximation in a fixed data set. Theorem 3.4.1 (Main theorem).Given a DC network Γ = (V, c), positive values 0< |u|min ≤ |u|max,m∈N∗and u,s∈C(V, Rm)such that |u|min ≤ |uj| ≤ |u|max for all j= 1, . . . , m; if Γ′is an ε-approximation of Γ, then: rms(Γ′,u,s)≤rms(Γ,u,s) + ε∥QΓ,u∥2·∥1m−ϕu∥ pm|V|. Proof. Let Γ′= (V, c′) be an ε-approximation of Γ, with Laplacian L′. As QΓ′,u(1m) = ME(Γ′),u(c′), by (3.3) we get that rms(Γ′,u,s) = 1 pm|V|∥QΓ′,u(1m)−s∥ ≤1 pm|V|∥QΓ,u(1m)−s∥+1 pm|V|∥QΓ′,u(1m)−QΓ,u(1m)∥ =rms(Γ,u,s) + 1 pm|V|∥(QΓ′,u−QΓ,u) (1m)∥. The constant functions belong to the null space of any Laplacian, therefore ϕubelongs to the null space of QΓ′,u−QΓ,u, and thus ∥(QΓ′,u−QΓ,u) (1m)∥=∥(QΓ′,u−QΓ,u) (1m−ϕu)∥ ≤ ∥QΓ′,u−QΓ,u∥2·∥1m−ϕu∥.(3.6) In order to complete the proof, it is enough to show that ∥QΓ′,u−QΓ,u∥2≤ε∥QΓ,u∥2. Now, QΓ′,u−QΓ,uis a self-adjoint operator, so its spectral norm is equal to the maximum of the absolute value of its eigenvalues. It is straightforward to prove that its eigenvalues are those of the operators QΓ′,uj−QΓ,ujfor all 1 ≤j≤m. In particular, there is at least one index ksuch that ∥QΓ′,u−QΓ,u∥2=∥QΓ′,uk−QΓ,uk∥2. Sparsification of recovered electrical networks 79 Let u0∈C(V) be an eigenvector of QΓ′,uk−QΓ,ukcorresponding with its eigenvalue that has the largest absolute value such that ∥u0∥= 1. Then ∥QΓ′,u−QΓ,u∥2=|⟨u0,(QΓ′,uk−QΓ,uk) (u0)⟩|. Now, denoting as Eand E′the energy of Γ and Γ′, respectively, we have that ⟨u0,(QΓ′,uk−QΓ,uk) (u0)⟩=⟨u0, uk(L′−L)(uku0)⟩ =ZV u0uk(L′−L)(u0uk)dx =E′(u0uk, u0uk)−E(u0uk, u0uk). Evaluating (3.5) at u=u0uk∈C(V) we get 1 1 + εE(u0uk, u0uk)≤ E′(u0uk, u0uk)≤(1 + ε)E(u0uk, u0uk).(3.7) From the right inequality of (3.7), we have: E′(u0uk, u0uk)−E(u0uk, u0uk)≤εE(u0uk, u0uk), and from the left inequality in (3.7): −(E′(u0uk, u0uk)−E(u0uk, u0uk)) ≤ε 1 + εE(u0uk, u0uk)< εE(u0uk, u0uk). Joining the last two inequalities, we get ∥QΓ′,u−QΓ,u∥2≤εE(u0uk, u0uk). Moreover, E(u0uk, u0uk) = ZV u0ukL(u0uk)dx =⟨u0, ukL(uku0)⟩ =⟨u0,QΓ,uk(u0)⟩. By the Courant-Fisher theorem [94], the evaluation of the quadratic form associated with the operator QΓ,ukat any unit vector is less or equal than its maximum eigenvalue, which is equal to the norm of this operator because it is positive semidefinite, so: ∥QΓ′,u−QΓ,u∥2≤ε∥QΓ,uk∥2≤ε∥QΓ,u∥2,(3.8) where the last inequality holds because the eigenvalues of QΓ,uare those of the operators QΓ,ujfor all 1 ≤j≤m. Remark 3.4.2. In (3.6), it is possible to introduce any vector function equal to λ1u−1 1, ..., λmu−1 m∈C(V, Rm), for any choice of λ1, ..., λm∈R, because all of them belong to the null space of QΓ′,u−QΓ,u. Among them, we choose to introduce the term ϕubecause it is the choice that minimizes ρ(λ1, .., λm)≡ 1m−λ1u−1 1, ..., λmu−1 m  2= 80 Simultaneous recovery of the topology and admittance of a network Pm j=1 RVχV−λju−1 j2dx. Effectively, if we look for a minimum of ρ, its partial derivatives must be zero: ∂ρ(λ1, .., λm) ∂λk = 2 ZV−u−1 k+λku−1 k2dx = 0, so the only possible choice for the λkis: λk=RVu−1 kdx ||u−1 k||2, which is indeed the global minimum of ρbecause its Hessian is positive definite: if j=k, then ∂2ρ(λ1,..,λm) ∂λk∂λj= 0, and for each k= 1, ..., m, ∂2ρ(λ1, .., λm) ∂λ2 k = 2 ZVu−1 k2dx > 0. Remark 3.4.3. The term ∥QΓ,u∥2·∥1m−ϕu∥ √m|V|that appears in the upper bound given by the last theorem depends only on the electrical network Γ and the first element of the data pair (u,s), so if we want a sparse approximation of Γ such that the rms of the approximation does not increase (with respect to rms(Γ,u,s)) in the sparsification procedure above a fixed value, there is an ε > 0 such that any ε-approximation of Γ is guaranteed to meet this requirement. In the case of an AC electrical network Γ, we denote by Γc= (V, c) and Γb= (V, b) the conductance and susceptance networks of Γ, whose respective Laplacians are Lcand Lb. Additionally, we define the function ∆(Γ,u) = pm|V|(∥QΓc,ℜ(u)∥2+∥QΓc,ℑ(u)∥2) + ∥Lb∥2(∥ℜ(u)∥∞∥ℑ(u)∥2+∥ℑ(u)∥∞∥ℜ(u)∥2)2+ +pm|V|(∥QΓb,ℜ(u)∥2+∥QΓb,ℑ(u)∥2) + ∥Lc∥2(∥ℑ(u)∥∞∥ℜ(u)∥2+∥ℜ(u)∥∞∥ℑ(u)∥2)21/2 , and we have the following result, which is the AC analogous to Theorem 3.4.1: Theorem 3.4.4. Given an AC network Γ = (V, a),m∈N∗and u,s∈C(V, Cm), if Γ′is an ε-approximation of Γ, then: rms(Γ′,u,s)≤rms(Γ,u,s) + ε∆(Γ,u) p2m|V|, where ∆(Γ,u)is a function which depends only on Γand u. Proof. First, for every u∈C(V, C), we have that uL(u) = uL∗(u) = (ℜ(u) + iℑ(u))(Lc+iLb)((ℜ(u)−iℑ(u))), and therefore ℜ(uL(u)) = ℜ(u)Lc(ℜ(u)) + ℜ(u)Lb(ℑ(u)) + ℑ(u)Lb(ℜ(u)) + ℑ(u)Lc(ℑ(u)),(3.9) Sparsification of recovered electrical networks 81 and also ℑ(uL(u)) = ℑ(u)Lc(ℜ(u)) + ℑ(u)Lb(ℑ(u)) + ℜ(u)Lb(ℜ(u)) + ℜ(u)Lc(ℑ(u)).(3.10) Now, let Γ′= (V, a′) be an ε-approximation of Γ, with Laplacian L′. Let Γ′ c= (V, c′) and Γ′ b= (V, b′) be the conductance and susceptance networks of Γ′, whose respective Laplacians are L′ cand L′ b. By (3.3) we get that rms(Γ′,u,s) = 1 pm|V|∥ME(Γ′),u(c′, b′)−S(s)∥ ≤1 pm|V|∥ME(Γ),u(c, b)−S(s)∥+1 pm|V|∥ME(Γ′),u(c′, b′)−ME(Γ),u(c, b)∥ =rms(Γ,u,s) + 1 pm|V|∥ME(Γ′),u(c′, b′)−ME(Γ),u(c, b)∥. The square of the norm in the last equation is equal to ∥ME(Γ′),u(c′, b′)−ME(Γ),u(c, b)∥2=∥ℜ(u1(L′−L) (u1)), ..., ℜ(um(L′−L) (um))∥2 +∥ℑ(u1(L′−L) (u1)), ..., ℑ(um(L′−L) (um))∥2. (3.11) By equations (3.9), (3.10) and (3.11), we can write ∥ME(Γ′),u(c′, b′)−ME(Γ),u(c, b)∥2=∥β1+β2−β3+β4∥2+∥β5+β6+β7−β8∥2 ≤(∥β1∥+∥β2∥+∥β3∥+∥β4∥)2 + (∥β5∥+∥β6∥+∥β7∥+∥β8∥)2, (3.12) where: β1= (Pc′−Pc) (ℜ(u),ℜ(u)) , β2= (Pb′−Pb) (ℜ(u),ℑ(u)) , β3= (Pb′−Pb) (ℑ(u),ℜ(u)) , β4= (Pc′−Pc) (ℑ(u),ℑ(u)) , β5= (Pc′−Pc) (ℑ(u),ℜ(u)) , β6= (Pb′−Pb) (ℑ(u),ℑ(u)) , β7= (Pb′−Pb) (ℜ(u),ℜ(u)) , β8= (Pc′−Pc) (ℜ(u),ℑ(u)) . Then, on one hand, Pc(ℜ(u),ℜ(u)) = QΓc,ℜ(u)(1m) and Pc′(ℜ(u),ℜ(u)) = QΓ′ c,ℜ(u)(1m), so by (3.8), we get ∥β1∥≤∥QΓ′ c,ℜ(u)−QΓc,ℜ(u)∥2·∥1m∥=pm|V|∥QΓ′ c,ℜ(u)−QΓc,ℜ(u)∥2 ≤εpm|V|∥QΓc,ℜ(u)∥2. Reasoning analogously, we also obtain that ∥β4∥ ≤ εpm|V|∥QΓc,ℑ(u)∥2, ∥β6∥ ≤ εpm|V|∥QΓb,ℑ(u)∥2and ∥β7∥ ≤ εpm|V|∥QΓb,ℜ(u)∥2. On the other hand, Lc=QΓc,χV,L′ c=QΓ′ c,χV,Lb=QΓb,χVand L′ b=QΓ′ b,χV, so, by the proof of Theorem 3.4.1, we have that ∥L′ c−Lc∥2≤ε∥Lc∥2and ∥L′ b−Lb∥2≤ε∥Lb∥2. 82 Simultaneous recovery of the topology and admittance of a network As a consequence, for any (v,w) = ((v1, ..., vm),(w1, ..., wm)) ∈C(V, Rm)×C(V, Rm) it is satisfied that ∥(Pc′−Pc) (v,w)∥2= m X j=1 ZV v2 j(L′ c−Lc)(wj)2dx ≤ ∥v∥2 ∞ m X j=1 ZV (L′ c−Lc)(wj)2dx =∥v∥2 ∞ m X j=1 ∥(L′ c−Lc)(wj)∥2 2 ≤ ∥v∥2 ∞ m X j=1 ∥(L′ c−Lc)∥2 2·∥wj∥2 2=∥v∥2 ∞·∥(L′ c−Lc)∥2 2·∥w∥2 2 ≤ε2∥Lc∥2 2·∥v∥2 ∞·∥w∥2 2. And, analogously, it is satisfied that ∥(Pb′−Pb) (v,w)∥ ≤ ε∥Lb∥2·∥v∥∞·∥w∥2. Applying this result, we get the following bounds: ∥β2∥ ≤ ∥Lb∥2·∥ℜ(u)∥∞·∥ℑ(u)∥2, ∥β3∥ ≤ ∥Lb∥2·∥ℑ(u)∥∞·∥ℜ(u)∥2,∥β5∥ ≤ ∥Lc∥2·∥ℑ(u)∥∞·∥ℜ(u)∥2and ∥β8∥ ≤ ∥Lc∥2·∥ℜ(u)∥∞·∥ℑ(u)∥2. Considering in (3.12) all the upper bounds obtained for ∥β1∥, ..., ∥β8∥, we conclude the proof. 3.5 Algorithm for sparse network recovery This section is a review of [88, Subsection 4.3]. In this section we propose an algorithm to solve the Problem 3.2.1 of recovering simultaneously the topology and admittance of a sparse electrical network. If we have an electrical network Γ = (V, a), a data pair (u,s) and we choose an εsuch that the rms of any ε-approximation of Γ in the data pair (u,s) does not surpass a fixed tolerance tol >0 (by Theorems 3.4.1 and 3.4.4 such a εexists if rms(Γ,u,s)<tol), the only guarantee about the number of edges that any ε-approximation obtained by executing Sparsify(Γ, ε) will have is that this number of edges will be less or equal than the number of edges sampled in Algorithm 1, t= 8|V| · log(|V|)/ε2. If tol is small, the number of edges sampled will be large, so most ε-approximations of Γ will have the same number of edges as the original network, thus they will not be useful for our purposes. In the experimentation we have found that, if we choose an εsuch that Γ′=Sparsify(Γ, ε) satisfies that |E(Γ′)|<|E(Γ)|, and then we solve Problem 3.1.2 with the set E(Γ′); (that is, we execute [Γ′′,rms′′] = network recovery(E(Γ′),u,s), determining a network Γ′′ = (V, a′′) with set of edges E(Γ′′)⊆E(Γ′) such that the error rms′′ =rms(Γ′′,u,s) is minimum), then we have rms′′ ≤tol in many cases, even in cases in which rms(Γ′,u,s)>tol. Our approach to solve Problem 3.2.1 consists in the application of Algorithm 2. The algorithm starts by fitting a network Γ = network recovery(E, u,s) solving Problem 3.1.2 with the data pair (u,s) and the set of edges E. Then, our goal is to perform a sparsification of Γ, Γ′=Sparsify(Γ, ε), followed by a recovery of another network Γ′′ solving Problem 3.1.2 3.6. EXPERIMENTAL RESULTS AND DISCUSSION 83 with the set of edges of the sparse approximation, E(Γ′), as in the paragraph above, looking for a network with less edges than the current one, and with a rms below the input tolerance tol. We do not know which choices of εcan lead us to a network with these characteristics, so we use a procedure of exploration to let Algorithm 2 find suitable values of ε. We start the algorithm with an initial input value of ε, and we do an iterative procedure. Each iteration begins by checking if Γ′=Sparsify(Γ, ε) has less edges than the current network Γ. If this is not the case, there is a high probability, from Theorem 3.3.3, of Γ′being a sparse approximation so close to Γ that it has the same set of edges, so we increase the value of ε multiplying it by the input parameter ψ > 1, and we finish the iteration. In this way, in the next iteration the number of edges sampled in Sparsify will be lower than in the previous one, increasing the probability of getting sparse approximations with less edges than Γ. If, on the contrary, |E(Γ′)|<|E(Γ)|, we recover the network Γ′′ solving Problem 3.1.2 with set of edges E(Γ′), that is, we compute [Γ′′,rms′′] = network recovery(E(Γ′),u,s). Then, we check if rms′′ ≤tol. If this is the case, we replace the current network Γ by this new Γ′′ and we finish the iteration, using the new network as input for Sparsify in the next iteration, repeating the process, in order to look for networks with less edges than it. If, on the opposite case, rms′′ >tol, this means we have removed edges that are necessary for the network to correctly fit the data in the sparsification process, because there are no networks with set of edges contained in E(Γ′) whose rms is lower or equal than tol. We reject the network Γ′′, we decrease the value of εdividing it by ψand we finish the iteration because, from theorems 3.4.1 and 3.4.4, we know that decreasing the value of εassures that the rms on any subsequent ε-approximation of Γ will have a smaller upper bound. It is possible to define different stopping criteria for Algorithm 2, such as the total running time if we are interested on the best network that the algorithm can find in that period, or a maximum number of consecutive iterations in which the network has not changed. In the case of distribution networks, it is usual that the position of the switches is set so that the network topology is a tree, so in this case, reaching a tree topology can be another stopping criterion. A detailed discussion about the stopping criteria is left for future work. 3.6 Experimental results and discussion Lastly, we present some results of the application of Algorithm 2 to solve examples of Problem 3.2.1. This section is a review of [88, Section 5]. The algorithm has been written in MATLAB using Casadi [101], an open-source software tool that provides a symbolic framework suited for numerical optimization, and the interior-point solver IPOPT [102], an open-source software package for large-scale nonlinear optimization, for the network recovery process. The tolerance used in IPOPT is equal to 10−8. In all the examples, we use ψ= 1.5 as input of Algorithm 2. In each example, we have chosen a network Γ and we have sampled a data pair (u,s) consisting in m= 1000 pairs of voltage and power injected at Γ. Each pair (uj, sj) has been computed numerically solving the power flow equations of Γ, sj=ujL(uj), along with 90 Conclusions Chapter 2 was dedicated to studying of the inverse conductance problem on a DC network. This problem consists in recovering the conductance of a network from its Dirichletto-Neumann map, and it is ill-posed. In particular, we have reviewed and extended the results from [38] and [37]. In [38] the authors proposed Problem 2.3.1 as a reformulation of the inverse conductance problem. We have seen that Problem 2.3.1 is a polynomial optimization problem with a regularization term. This term penalizes deviations with respect to the conductance being piecewise constant on a partition of the edge set known a priori. We have presented numerous experimental examples that suggest that when the conductance is truly piecewise constant on the considered partition, the Lipschitz stability constant of the problem grows exponentially with the number of subsets in the partition. In particular, when the number of subsets is small relative to the total number of edges, we have been able to solve the inverse conductance problem with stability, for different partitions and sizes of the network. We have also discussed an example from [37] of resolution of the inverse conductance problem using the formulation of Problem 2.3.1 with a partition such that the actual conductance is not piecewise constant on it. In this example, the resolution of Problem 2.3.1 with a certain positive value of the penalty parameter yields better results than enforcing the recovered conductance to be piecewise constant on the partition or solving the problem without any regularization. This supports our penalty formulation of Problem 2.3.1 and the applicability of this approach to solve real-world problems, in which it is expected that the actual conductance is not exactly piecewise constant on the known partition. We have also explained how we can look for a guarantee that a minimum of this optimization problem obtained with a numerical method is a global minimum using techniques of Sum of Squares (SOS) decompositions of polynomials, (see [37]). We think that our approach of reformulation to solve the inverse conductance problem is promising, considering the results presented in this thesis. In particular, it would be interesting to solve the inverse conductance problem with this approach as part of a process to get a numerical solution of Calder´on’s problem. Currently, the use of spider networks in applications of Calder´on’s problem to noninvasive medical imaging is typically restricted to networks with fewer than 16 nodes on the boundary. As we have seen that our method remains stable when the size of the network increases, our method would enable the use of larger networks, thus improving the numerical results. We believe that it would also be interesting to solve Problem 2.3.1 for other network topologies for which we know that the inverse conductance problem has a unique solution, such as for critical planar graphs different from the spider graphs. Also, it would be interesting to carry out experiments with a supercomputer applying the mentioned SOS techniques for larger networks. If, in an experiment, a numerical method provides a minimum of Problem 2.3.1, but SOS techniques do not guarantee it is a global minimum, then we could look for another minimum of Problem 2.3.1 by using the numerical method with another initial guess, or by using a different numerical method. Chapter 3 has been devoted to extend and review the results from [88]. The aim of the chapter was to study the inverse problem of simultaneously recovering the admittance and topology of an AC or DC network from a set of measurements of voltage and its corresponding power injected at all vertices. Nevertheless, as we have discussed, this problem is Conclusions 91 ill-posed, and thus we usually get a solution with a large set of edges, which is not efficient for applications. Therefore, Problem 3.2.1 was proposed as a reformulation. The goal of this reformulated inverse problem is to recover a sparse network such that the fitting error to the data is below a fixed tolerance. A solution to this problem would be desirable from an applied point of view because it would allow the efficient and accurate resolution of usual problems in electrical networks. Motivated by our mentioned novel physical insights on Algorithm 1, we have studied its application to solve Problem 3.2.1. We have seen that given ε > 0 and a network Γ = (V, c), this algorithm generates a network Γ′= (V, c′) by removing edges from Γ, and there is a certain probability that Γ′is an ε-approximation of Γ, (see Definition 3.3.1). Then, we have proved original theoretical results (see Theorems 3.4.1 and 3.4.4) that give an upper bound on the fitting error of any ε-approximation a network. Later, we have proposed Algorithm 2 to obtain a solution to Problem 3.2.1, which is based on Theorems 3.4.1 and 3.4.4. This algorithm consists in an iterative procedure of solving a convex problem and applying Algorithm 1. We presented diverse experimental results, which suggest that Algorithm 2 is promising for efficiently solving the problem. In all experiments, after just a few iterations, we recovered a network that was either the real one, electrically equivalent to the real one under the conditions satisfied by the data set, or a sparse approximation of the real network. Therefore, we believe it would be interesting to further study Algorithm 2 in the future. One line of research currently in progress is the study of stopping criteria for it. Another promising direction for future research is exploring the application of alternative graph sparsification procedures to remove edges in the algorithm. To conclude, the discrete vector calculus on networks developed in this thesis has provided us the tools and definitions necessary to formulate and achieve significant advances in inverse problems on networks. In particular, we have proposed a stable reformulation of the inverse conductance problem and we have introduced an algorithm to solve Problem 3.2.1, based on original theoretical results. Bibliography [1] Abdulla, U.G., Bukshtynov, V., Seif, S., 2021. Cancer detection through electrical impedance tomography and optimal control theory: theoretical and computational analysis. Math. Biosci. Eng. 18, 4834–4859. [2] Abur, A., G´omez, A., 2004. Power System State Estimation: Theory and Implementation. Marcel Dekker, Inc. [3] Adams, R.A., Fournier, J., 2003. Sobolev spaces. volume 140 of Pure and Applied Mathematics (Amsterdam). Second ed., Elsevier/Academic Press, Amsterdam. [4] Adler, A., Holder, D., 2022. Electrical Impedance Tomography: Methods, History and Applications. Second ed., CRC Press. [5] Alessandrini, G., 1988. Stable determination of conductivity by boundary measurements. Appl. Anal. 27, 153–172. [6] Alessandrini, G., Vessella, S., 2005. Lipschitz stability for the inverse conductivity problem. Adv. Appl. Math. 35, 207–241. [7] Ara´uz, C., 2014. The inverse problem on finite networks. PhD Thesis, UPC. [8] Ara´uz, C., Carmona, ´ A., Encinas, A.M., 2015a. Dirichlet-to-Robin maps on finite networks. Appl. Anal. Discrete Math. 9, 85–102. [9] Ara´uz, C., Carmona, ´ A., Encinas, A.M., 2015b. Discrete Serrin’s problem. Linear Algebra Appl. 468, 107–121. [10] Ara´uz, C., Carmona, ´ A., Encinas, A.M., 2015c. Overdetermined partial boundary value problems on finite networks. J. Math. Anal. Appl. 423, 191–207. [11] Ara´uz, C., Carmona, ´ A., Encinas, A.M., Mitjana, M., 2016. Recovering the conductances on grids: a theoretical justification, in: A panorama of mathematics: pure and applied. Amer. Math. Soc., Providence, RI. volume 658 of Contemp. Math., pp. 149–166. [12] Astala, K., P¨aiv¨arinta, L., 2006a. A boundary integral equation for Calder´on’s inverse conductivity problem. Collect. Math. (2006) 57, 127–139. [13] Astala, K., P¨aiv¨arinta, L., 2006b. Calder´on’s inverse conductivity problem in the plane. Ann. Math. 163, 265–299. Bibliography 93 [14] Barcel´o, J.A., Barcel´o, T., Ruiz, A., 2001a. Stability of the inverse conductivity problem in the plane for less regular conductivities. J.Differential Equations 173, 231–270. [15] Barcel´o, J.A., Barcel´o, T., Ruiz, A., 2001b. Unicidad y estabilidad para el problema de conductividad inverso, in: Margarita Matem´atica en Memoria de Jos´e Javier Guadalupe Hen´andez, Servicio de Publicaciones de la Universidad de La Rioja, Logro˜no, Spain. pp. 401–413. [16] Batson, J., Spielman, D., Srivastava, N., Teng, S., 2013. Spectral Sparsification of Graphs: Theory and Algorithms. Commun. ACM 56, 87–94. [17] Bendito, E., Carmona, ´ A., Encinas, A.M., 2000. Solving boundary value problems on networks using equilibrium measures. J. Funct. Anal. 171, 155–176. [18] Bendito, E., Carmona, ´ A., Encinas, A.M., 2004. Difference schemes on uniform grids performed by general discrete operators. Appl. Num. Math. 50, 343–370. [19] Bendito, E., Carmona, ´ A., Encinas, A.M., 2005. Potential theory for Schr¨odinger operators on finite networks. Rev. Mat. Iberoamericana 21, 771–818. [20] Bendito, E., Carmona, ´ A., Encinas, A.M., 2008. Boundary value problems on weighted networks. Discrete Appl. Math. 156, 3443–3463. [21] Benning, M., Burger, M., 2018. Modern regularization methods for inverse problems. Acta Numer. 27, 1–111. [22] Bensoussan, A., Menaldi, J., 2005. Difference equations on weighted graphs,. J. Convex Anal. 12, 13–44. [23] Borcea, L., Druskin, V., Guevara, F., 2008. Electrical Impedance Tomography with resistor networks. Inverse Problems 24, 035013. [24] Borcea, L., Druskin, V., Guevara, F., Mamonov, A., 2011. Resistor network approaches to electrical impedance tomography, in: Inverse problems and applications: inside out. II (G. Uhlmann ed.). Cambridge Univ. Press, Cambridge. volume 60 of Math. Sci. Res. Inst. Publ., pp. 55–118. [25] Borcea, L., Druskin, V., Knizhnerman, L., 2005. On the continuum limit of a discrete inverse spectral problem on optimal finite difference grids. Comm. Pure Appl. Math. 58, 1231–1279. [26] Borcea, L., Druskin, V., Mamonov, A.V., 2010. Circular resistor networks for electrical impedance tomography with partial boundary measurements. Inverse Problems 26, 045010. [27] Borcea, L., Guevara, F., Mamonov, A.V., 2013. Study of noise effects in electrical impedance tomography with resistor networks. Inverse Probl. Imaging 7, 417–443. [28] Borcea, L., Guevara, F., Mamonov, A.V., 2017. A discrete Liouville identity for numerical reconstruction of Schr¨odinger potentials. Inverse Probl. Imaging 11, 623–641. 94 Bibliography [29] Bottura, R., Babazadeh, D., Zhu, K., Borghetti, A., Nordstr¨om, L., Nucci, C.A., 2013. Sitl and hla co-simulation platforms: Tools for analysis of the integrated ict and electric power system, in: Eurocon 2013, IEEE. pp. 918–925. [30] Boyer, J., Garzella, J.J., Guevara-Vasquez, F., 2016. On the solvability of the discrete conductivity and Schr¨odinger inverse problems. SIAM J. Appl. Math. 76, 1053–1075. [31] Brezis, H., 2011. Functional analysis, Sobolev spaces and partial differential equations. Universitext, Springer, New York. [32] Brown, R.M., Uhlmann, G.A., 1997. Uniqueness in the inverse conductivity problem for nonsmooth conductivities in two dimensions. Comm. Partial Differential Equations 22, 1009–1027. [33] Bunge, A., Botsch, M., 2023. A Survey on Discrete Laplacians for General Polygonal Meshes. Comput. Graph. Forum 42, 521–544. [34] Calder´on, A.P., 2006. On an inverse boundary value problem. Comput. Appl. Math. 25, 133–138. (Reprint of the original work in Seminar on Numerical Analysis and its Applications to Continuum Physics, Soc. Brasil. Mat. Rio de Janeiro 65-73, 1980.). [35] Carmona, ´ A., 2018. Boundary value problems on finite networks, in: Combinatorial Matrix Theory (Encinas A.M. and Mitjana, M. eds.). Birkh¨auser/Springer, Cham. Advanced Courses in Mathematics. CRM Barcelona, pp. 173–217. [36] Carmona, ´ A., Encinas, A.M., 2024. Discrete operators on graphs and networks, in: Inverse Problems, Regularization Methods and Related Topics. A Volume in Honour of Thamban Nair (Pereverzyev, S.V. and Radha, R. and S. Sampath, S. eds.). Springer. Industrial and Applied Mathematics, to appear. [37] Carmona, ´ A., Encinas, A.M., Jim´enez, M.J., Samperio, ´ A., 2024a. Stable and optimal conductance recovery on networks. Submitted . [38] Carmona, ´ A., Encinas, A.M., Jim´enez, M.J., Samperio, ´ A., 2024b. Stable recovery of piecewise constant conductance on spider networks. Int. J. Comput. Math. , 1–18. [39] Caro, P., Garc´ıa-Ferrero, M.´ A., Rogers, K.M., 2024. Reconstruction for the Calder´on problem with Lipschitz conductivities. ArXiv preprint: 2401.06120v1 . [40] Caro, P., Rogers, K.M., 2016. Global uniqueness for the Calder´on problem with Lipschitz conductivities. Forum Math., Pi 4, 20 pages. [41] Chan, M., Tae, J., Jeongchan, N., Hyeuknam, K., Kiwan, J., Kyounghun, L., 2023. Machine learning-based signal quality assessment for cardiac volume monitoring in electrical impedance tomography. Mach. Learn.: Sci. Technol. 4, 015034. [42] Cheney, M., Isaacson, D., Newell, J.C., 1999. Electrical impedance tomography. SIAM Rev. 41, 85–101. [43] Chou, H., Maly, J., Verdun, C., 2022. Non-negative Least Squares via Overparametrization. arXiv preprint: 2207.08437 . Bibliography 95 [44] Chung, F., 1997. Spectral Graph Theory. volume 92 of CBMS Regional Conf. Ser. in Math. American Mathematical Society, Providence, RI,. [45] Chung, F., Gilbert, A., Hoskins, J., Schotland, J., 2017. Optical tomography on graphs. Inverse Problems 33, 055016, 21. [46] Chung, F., Yau, S.T., 2000. Discrete Green’s Functions. J. Combin. Theory Ser. A 91, 191–214. [47] Chung, S., Berenstein, C., 2005. ω-harmonic functions and inverse conductivity problems on networks. SIAM J. Appl. Math. 65, 1200–1226. [48] Colin de Verdi`ere, Y., 1994. R´eseaux ´electrique planaires i. Commentarii Mathematici Helvetici 69, 351–374. [49] Conway, J.B., 2007. A Course in Functional Analysis. volume 96 of Graduate Texts in Mathematics. Springer New York, NY. [50] Crabtree, D.E., Haynsworth, E.V., 1969. An identity for the Schur complement of a matrix. Proc. Am. Math. Soc. 22, 364–366. [51] Curtis, E.B., Ingerman, D., Morrow, J.A., 1998. Circular planar graphs and resistor networks. Linear Algebra Appl. 283, 115–150. [52] Curtis, E.B., Morrow, J.A., 1990. Determining the resistors in a network. SIAM J. Appl. Math. 50, 918–930. [53] Curtis, E.B., Morrow, J.A., 1991. The Dirichlet to Neumann map for a resistor network. SIAM J. Appl. Math. 51, 1011–1029. [54] Curtis, E.B., Morrow, J.A., 2000. Inverse problems for electrical networks. volume 13. World Scientific. [55] Curtis, E.B., Morrow, J.A., Mooers, E., 1994. Finding the conductors in circular networks from boundary measurements, rairo model. RAIRO Mod´el. Math. Anal. Num´er. 28, 781–814. [56] D., C., Parrilo, P., 2017. Sampling algebraic varieties for sum of squares programs. SIAM J. Optimiz. 27, 2381–2404. [57] Deka, D., Backhaus, S., Chertkov, M., 2015. Structure Learning in Power Distribution Networks. IEEE Trans. Control Netw. Syst. 5, 1061–1074. [58] Devriendt, K., 2022. Effective resistance is more than distance: Laplacians, Simplices and the Schur complement. Linear Algebra Appl. 639, 24–49. [59] Dodziuk, J., 1986. Laplacian on manifolds and analogous difference operator for graphs, in: Complex differential geometry and nonlinear differential equations (Brunswick, Maine, 1984). Amer. Math. Soc., Providence, RI. volume 49 of Contemp. Math., pp. 45–49. [60] Dorfler, F., Bullo, F., 2013. Kron reduction of graphs with applications to electrical networks. IEEE Trans. Circuits Syst. I. Regul. Pap. 60, 150–163. 96 Bibliography [61] Engl, H., Hanke, M., Neubauer, A., 1996. Regularization of inverse problems. volume 375 of Mathematics and it Applications. Kluwer Academic Publishers Group, Dordrecht. [62] Ervedoza, S., de Gournay, F., 2011. Uniform stability estimates for the discrete Calder´on problems. Inverse problems 27, 125012. [63] Fraunhofer IEE and University of Kassel, a. Pandapower documentation. CIGRE networks. https://pandapower.readthedocs.io/en/v2.6.0/networks/cigre.html. Accessed: 22/07/2024. [64] Fraunhofer IEE and University of Kassel, b. Pandapower documentation. Kerber Networks. https://pandapower.readthedocs.io/en/v2.6.0/networks/kerber.html. Accessed: 22/07/2024. [65] George, T., 2024. The twist for electrical networks and the inverse problem. Int. Math. Res. Notices 8, 1073–7928. [66] Gernandt, H., Rohleder, J., 2022. A Calder´on type inverse problem for tree graphs. Linear Algebra Appl. 646, 29–42. [67] Grigor´yan, A., 2018. Introduction to analysis on graphs. volume 71 of University Lecture Series. American Mathematical Society, Providence, RI. [68] Hyman, J., Shashkov, M., 1997. Adjoint operators for the natural discretizations of the divergence, gradient and curl on logically rectangular grids. Appl. Numer. Math. 25, 413–442. [69] Hyman, J., Shashkov, M., Steinberg, S., 2001. The effect of inner products for discrete vector fields on the accuracy of mimetic finite difference methods. Comput. Math. Appl. 42, 1527–1547. [70] Kayano, T., Yamasaki, M., 1988/89. Discrete Dirichlet integral formula. Discrete Appl. Math. 22, 53–68. [71] Kenyon, R., Wilson, D., 2017. The space of circular planar electrical networks. SIAM J. Discrete Math. 31, 1–28. [72] Khan, A., Chakrabarti, S., Sharma, A., Alam, M., 2019. Parameter and Topology Estimation for Electrical Power Distribution System, in: 2019 8th International Conference on Power Systems (ICPS), pp. 1–5. [73] Lasserre, J., 2010. Moments, positive polynomials and their applications. volume 1 of Imperial College Press Optimization Series. Imperial College Press, London. [74] Lim, L.H., 2020. Hodge Laplacians on graphs. SIAM Rev. 62, 685–715. [75] Liu, L., 1997. Stability estimates for the two-dimensional inverse conductivity problem. PhD Thesis, University of Rochester, New York. [76] Lukaschewitsch, M., Maass, P., Pidcock, M., 2003. Tikhonov regularization for electrical impedance tomography on unbounded domains. Inverse Problems 19, 585–610. Bibliography 97 [77] Mandache, N., 2001. Exponential instability in an inverse problem for the Schr¨odinger equation. Inverse Problems 17, 1435–1444. [78] Milton, G.W., Seppecher, P., 2008. Realizable response matrices of multi-terminal electrical, acoustic and elastodynamic networks at a given frequency. Proc. R. Soc. A. 464, 967–986. [79] Montes, A., Castro, J., 1995. Solving the load flow problem using Gr¨obner basis. ACM SIGSAM Bulletin 29, 1–13. [80] Papachristodoulou, A., Anderson, J., Valmorbida, G., Prajna, S., Seiler, P., Parrilo, P., Peet, M., Jagt, D., 2021. SOSTOOLS Version 4.00 Sum of Squares Optimization Toolbox for MATLAB. ArXiv preprint: 1310.4716 . [81] Parrilo, P., 2005. Exploiting Algebraic Structure in Sum of Squares Programs. Springer, Berlin, Heidelberg. pp. 181–194. [82] Putensen, C., Hentze, B., Muenster, S., Muders, T., 2019. Electrical impedance tomography for cardio-pulmonary monitoring. J. Clin. Med. 8, 1176. [83] Ramon, S., Putinar, M., 2007. Complex symmetric operators and applications II. Trans. Amer. Math. Soc. 359, 3913–3931. [84] Ribando-Gros, E., Wang, R., Chen, J., Tong, Y., Wei, G.W., 2024. Combinatorial and Hodge Laplacians: Similarities and differences. SIAM Rev. 66, 575–601. [85] Rondi, L., 2006. A remark on a paper by Alessandrini and Vessella. Adv. Appl. Math. 36, 67–69. [86] Rondi, L., 2016. Discrete approximation and regularisation for the inverse conductivity problem. Rend. Istit. Mat. Univ. Trieste 48, 315–352. [87] Rote, G., 2020. Characterization of the response maps of alternating-current networks. Electron. J. Linear Algebra 36, 698–703. [88] Samperio, ´ A., 2023. Sparse recovery of an electrical network. ArXiv preprint: 2304.06676 . [89] Sarode, V., Patkar, S., Cheeran, A.N., 2013. Comparison of 2-d algorithms in eit based image reconstruction. Int. J. Comput. Appl. 69, 6–11. [90] Shashkov, M., 1996. Conservative finite-difference methods on general grids. Symbolic and Numeric Computation Series, CRC Press, Boca Raton, FL. [91] Shi, Y., Yang, Z., Xie, F., Ren, S., Xu, S., 2021. The research progress of electrical impedance tomography for lung monitoring. Front. Bioeng. Biotechnol. 9, 726652. [92] Slawski, M., Hein, M., 2013. Non-negative least squares for high-dimensional linear models: Consistency and sparse recovery without regularization. Electron. J. Statist. 7, 3004–3056. [93] Spielman, D., 2017. Graphs, Vectors and Matrices. Bull. Amer. Math. Soc. (N.S.) 54, 45–61. 98 Bibliography [94] Spielman, D., Srivastava, N., 2011. Graph Sparsification by Effective Resistances. SIAM J. Comput. 40, 1913–1926. [95] Spielman, D., Teng, S.H., 2011. Spectral Sparsification of Graphs. SIAM J. Comput. 40, 981–1025. [96] Stagg, G., El-Abiad, A., 1968. Computer Methods in Power System Analysis. McGrawHill series in electronic systems, McGraw-Hill. [97] Sylvester, J., Uhlmann, G., 1987. A global uniqueness theorem for an inverse boundary value problem. Ann. Math. , 153–169. [98] Uhlmann, G., 1998. Inverse boundary value problems for partial differential equations, in: Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998), pp. 77–86. [99] Wadhwa, C.L., 2012. Electrical Power Systems. New Academic Science Limited. [100] Webpage, 2019. Calculus on finite weighted graphs. URL: https://en.wikipedia. org/wiki/Calculus_on_finite_weighted_graphs. [101] Webpage, 2024a. Casadi. URL: https://web.casadi.org/. [102] Webpage, 2024b. Ipopt documentation. URL: https://coin-or.github.io/Ipopt/. [103] Webpage, 2024c. Sedumi. URL: https://sedumi.ie.lehigh.edu/. [104] Zhang, T., Jang, G.Y., Oh, T.I., Jeung, K.W., Wi, H., Woo, E.J., 2020. Source consistency electrical impedance tomography. SIAM J. Appl. Math. 80, 499–520.