PROGRAMA DE DOCTORADO EN
MATEM ´
ATICAS
TESIS DOCTORAL:
SOME INVERSE PROBLEMS
ON FINITE NETWORKS
P esen ada po ´
Al a o Sampe io Valdi ieso pa a op a al
g ado de
Doc o /a po la Uni e sidad de Valladolid
Di igida po :
D . An onio Campillo L´opez
D . And ´es Ma cos Encinas Bachille
Funding
•Suppo ed by a FPI g an o he Resea ch P ojec PGC2018-096446-BC21 (wi h he
help o he FEDER P og am).
•Pa ially suppo ed by he p ojec PID2022-138906NB-C21 unded by
MICIU/AEI/ 10.13039/501100011033 and by ERDF/EU.
•Pa ially suppo ed by he Spanish Resea ch Council (Minis e io de Ciencia e Inno-
aci´on) unde p ojec PID2021-122501NB-I00.
Acknowledgmen s
May he eade o gi e me o w i ing he acknowledgmen s pa ially in Spanish.
A mis di ec o es de esis, An onio Campillo y And ´es Ma cos Encinas, cuyo apoyo ha
sido esencial pa a el desa ollo de es a esis. Ha sido una expe iencia p o undamen e en-
iquecedo a abaja con dos ma em´a icos an excelen es. Es oy muy ag adecido a An onio
po con ia en m´ı pa a desa olla es a esis y po lo mucho que he ap endido de ´el du an e
an os a˜nos. Tambi´en es oy muy ag adecido a And ´es po su eno me dedicaci´on, y po su
apues a po es e abajo, que ha sido decisi a pa a que salie a adelan e.
A F´elix Delgado, que ha sido como un e ce di ec o de es a esis. Adem´as de su g an
ayuda con los con enidos de la esis, y habe ap endido mucho de ´el compa iendo docencia,
ha sido la pe sona que m´as me ha in luido es os a˜nos, un e dade o ejemplo a segui que me
ha hecho mejo ma em´a ico y mejo pe sona.
I would like o hank he membe s o he ju y o eading his wo k, and I would also
like o hank he e e ees o hei help ul commen s and sugges ions on a i s e sion o his
hesis.
A mis compa˜ne os del Depa amen o de ´
Algeb a, Geome ´ıa, Topolog´ıa y An´alisis
ma em´a ico de la Uni e sidad de Valladolid, a mis compa˜ne os de doc o ado y a los miem-
b os del g upo de in es igaci´on SINGACOM. Ha sido un hono abaja en la Uni e sidad
de Valladolid, y el ambien e de abajo ha sido inmejo able. Me gus a ´ıa ag adece espe-
cialmen e su g an apoyo a mis compa˜ne os de doc o ado con los que he enido la sue e de
coincidi m´as iempo: S¸eyma Bodu , Daniel Camaz´on, Ignacio de Miguel y Ma ´ıa Ma ´ın,
que han sido como he manos pa a m´ı. Los comienzos en in es igaci´on son di ´ıciles y ha
sido undamen al compa i el iaje desde el p incipio con es e g upo, que ha sido como mi
amilia acad´emica.
A los miemb os del Depa amen o de Ma em´a icas y del g upo de in es igaci´on MAPTHE
de la Uni e sidad Poli ´ecnica de Ca alu˜na po se mi segunda casa en es e doc o ado, in-
cluyendo a En ic Mons´o, Ma ga ida Mi jana y Leona do Acho. En e ellos, me gus a ´ıa
dedica un ag adecimien o especial a mis coau o es ´
Angeles Ca mona, Ma ´ıa Jos´e Jim´enez,
y al p opio And ´es, cuya in luencia y ayuda en es a esis me cues a desc ibi con palab as. Es
un place cuando se encuen a un g upo con el que uno es ´a an c´omodo den o y ue a del
abajo, especialmen e siendo un g upo del que he ap endido an o. Cada isi a a Ba celona,
po peque˜na que sea, hace una g an di e encia.
Al coo dinado del p og ama de doc o ado, Al onso Go daliza, po su ce can´ıa; po es a
siemp e p eocupado y disponible pa a ayuda en odo lo posible en el desa ollo de la esis
iii
y po su g an es ue zo en el p oceso bu oc ´a ico.
A odas las pe sonas que me han in i ado a da con e encias a su uni e sidad y ambi´en a
odos los compa˜ne os que he conocido en cong esos, po lo mucho que he ap endido de ellos
en an as ponencias y ambi´en en con e saciones m´as in o males. En especial me que ´ıa
aco da de la Red ALAMA, a la que conside o una de las comunidades cien ´ı icas m´as
ac i as y acogedo as de es e pa´ıs, y pa icula men e me que ´ıa aco da de sus miemb os
Ca los Ma ijuan, Mi iam Pisone o, Jos´e M´as, Alicia Roca, Julio Mo o, Sil ia Ma caida y
Go ka A men ia.
Thank you o he Algeb aic Combina o ics g oup o he Eindho en Uni e si y o Tech-
nology and in pa icula o Aida Abiad, o in i ing me o a esea ch s ay. Du ing he ime
ha I was he e, I lea ned a lo om he and he expe ience was amazing bo h a a p o es-
sional and a pe sonal le el. I am also g a e ul o he en i e g oup o being so welcoming,
especially my iend Ignacio Echa e.
A mis coau o es Albe o Gonz´alez, Gilles Mo dan y Bodhi as a a Sen, con quienes
es oy encan ado de es a abajando en una colabo aci´on muy es imulan e. De los mejo es
momen os del doc o ado han sido las isi as a Valladolid de Albe o, que es siemp e una
e e encia pa a m´ı, an o como ma em´a ico como eligiendo ino en e a os de abajo.
Me gus a ´ıa ag adece a CARTIF su apues a decidida po la in es igaci´on en ma em´a icas,
aco da me de mis compa˜ne os de la Di isi´on de Ene g´ıa de la que es oy encan ado de o ma
pa e, y especialmen e da las g acias a Ali Vasallo, Fe nando F echoso y Se gio Saludes po
su con ianza y lexibilidad que han sido muy impo an es pa a pode hace el doc o ado.
A mis p o eso es de la Uni e sidad de Valladolid po b inda me una o maci´on excelen e y
a an os compa˜ne os de la ca e a po compa i a˜nos muy elices. Menci´on especial me ecen
mis compa˜ne os del G ado en Ma em´a icas, ´
Al a o Vielba, Diego Ma ´ın, Alonso S´anchez,
Juan Manuel Velasco, Alicia Nie o, Lau a Ca e as, Lau a Es eban, Elena Sob ini y Elena
de la Vega, jun o a los que empez´o es a pasi´on po las ma em´a icas en e San Bou bakis y
angos de la mue e.
A mis amigos de siemp e po su apoyo. Es muy impo an e pa a m´ı sabe que siemp e
an a es a ah´ı en los momen os di ´ıciles aunque no nos podamos e an a menudo como
me gus a ´ıa. Que ´ıa des aca sob e odo a ´
Al a o Delgado y a mis amigos de Valdunquillo
Ma io Valdi ieso, Da id Fe n´andez, Luis Pascual, Mus´a i a Tami y Jo ge Blanco.
Me gus a ´ıa inaliza con lo m´as impo an e, ag adeciendo su apoyo incondicional a oda
mi amilia en los buenos y malos momen os. A mi he mana, mis ´ıos y mis p imos po es a
siemp e pa a lo que haga al a. A mi mad e Ma ´ıa Jos´e Valdi ieso po ense˜na me desde
peque˜no la impo ancia de es udia y po su calidez y ca i˜no. A mi pad e Jos´e An onio
Sampe io ambi´en po ense˜na me la impo ancia de es udia y abaja du o pa a consegui
lo que me p opongo. Espe o que es e a˜no eamos po in al Racing ol e a P ime a. A
mis abuelos Eloisa Rod ´ıguez, Ma iano Valdi ieso y Amelia L´opez, y a la memo ia de mi
abuelo Jos´e Sampe io, po habe sido pa e undamen al de mi ida. No hay ca i˜no an
desin e esado y pu o como el que he enido la sue e de ecibi de mis abuelos.
Con en s
Funding i
Acknowledgmen s ii
In oduc ion 1
1 Disc e e ec o calculus on ne wo ks 7
1.1 Func ionspaces.................................. 7
1.2 Topology and geome y o a g aph . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.1 Tangen bundle o a g aph . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.2 Di e ence ope a o s on a g aph . . . . . . . . . . . . . . . . . . . . . 15
1.2.3 Bounda yo ase ............................. 17
1.3 Elec icalne wo ks ................................ 20
1.3.1 Di e ence ope a o s on a ne wo k . . . . . . . . . . . . . . . . . . . . 21
1.4 Bounda y alue p oblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.5 The Di ichle - o-Neumann map . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.6 Mono onici y on DC ne wo ks . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.7 E ec i eadmi ance ............................... 38
2 The in e se conduc ance p oblem 41
2.1 Backg ound o he p oblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.2 Ill-posedness o he in e se conduc ance p oblem . . . . . . . . . . . . . . . . 45
2.3 S able e o mula ion: he disc e e piecewise cons an conduc ance hypo hesis 49
2.3.1 Polynomial op imiza ion p oblem . . . . . . . . . . . . . . . . . . . . 50
Con en s
2.3.2 P oblem esolu ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.4 S able eco e y o piecewise cons an conduc ances . . . . . . . . . . . . . . 54
2.5 E o Va ia ion wi h espec o he penal y pa ame e . . . . . . . . . . . . . 60
2.6 Op imali y gua an ees o he eco e ed conduc ances . . . . . . . . . . . . . 65
3 Simul aneous eco e y o he opology and admi ance o a ne wo k 69
3.1 Ill-posedness o he p oblem . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.2 Re o mula ion o he p oblem: Reco e y o a spa se elec ical ne wo k . . . . 74
3.3 Spec al ne wo k spa si ica ion . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.4 Spa si ica ion o eco e ed elec ical ne wo ks . . . . . . . . . . . . . . . . . 77
3.5 Algo i hm o spa se ne wo k eco e y . . . . . . . . . . . . . . . . . . . . . 82
3.6 Expe imen al esul s and discussion . . . . . . . . . . . . . . . . . . . . . . . 83
Conclusions 89
Bibliog aphy 92
In oduc ion
In e se p oblems a e a class o ma hema ical p oblems whe e he objec i e is o de e mine
unknown causes om hei known e ec s. Many in e se p oblems ha e ga ne ed a en ion
because hei esolu ion allows o in e in o ma ion ha in some cases is no di ec ly ob-
se able, and in o he cases is di ec ly obse able, bu obse ing i is mo e expensi e and/o
des uc i e han in e ing i om i s known e ec s.
In e se p oblems ha e applica ions in many di e en ields. Fo ins ance, hey a e com-
mon in deblu ing images, signal eco e y, and o he a eas o digi al p ocessing. Mo eo e ,
echniques like magne ic esonance imaging (MRI) and compu ed omog aphy (CT) scans
ely on sol ing in e se p oblems o c ea e images o he in e io o he body. In e se p ob-
lems also help in in e p e ing seismic da a o oil explo a ion o in analyzing as onomical
da a.
Mos in e se p oblems a e ill-posed, meaning hey do no mee o e e y da a se he
c i e ia o exis ence, uniqueness and s abili y o he solu ion. In an uns able p oblem, e en
i he e is a unique solu ion o a da a se , small changes in he da a can lead o much
g ea e changes in he solu ion. Regula iza ion echniques a e o en used o handle his,
[4, 21]. Regula iza ion is a me hod o s abilize in e se p oblems by in oducing addi ional
in o ma ion o cons ain s. Techniques like Tikhono egula iza ion o L1- egula iza ion
help in dealing wi h ill-posedness and imp o ing he obus ness o solu ions, [1, 4, 89, 104].
In his wo k we ocus on he s udy o in e se p oblems on ini e elec ical ne wo ks.
We will conside Di ec Cu en (DC) ne wo ks and balanced Al e na ing Cu en (AC)
elec ical ne wo ks in which all lines a e induc i e and “sho ”, (i.e., hei leng h is sho e
han 80km). An elec ical ne wo k, (see De ini ion 1.3.1), is a pai Γ = (V, a) whe e Vis
a ini e nonemp y se called e ex se , and ais a complex symme ic unc ion on V×V
wi h nonnega i e eal pa and nonposi i e imagina y pa such ha a(x, x) = 0 o any
x∈V, called admi ance. In he case o DC ne wo ks, ais a eal unc ion and i is called
conduc ance. A ne wo k has an associa ed g aph called i s “ne wo k opology”, whose e ex
se is Vand whose edges a e he pai s {x, y}o dis inc e ices such ha a(x, y)= 0. The
alue a(x, y)= 0 is called he alue o he admi ance a he edge {x, y}.
A a gi en ime, he e exis physical quan i ies, such as po en ial, cu en injec ed o
powe injec ed, which a e de ined a he e ices o he ne wo k. The alue o each o hese
quan i ies a a se F⊆Vcan be ep esen ed by a complex unc ion on F o AC ne wo ks
and by a eal unc ion on F o DC ne wo ks. The e a e ela ions be ween hese unc ions,
which can be exp essed in e ms o di e ence ope a o s ha depend on he elec ical ne wo k.
In e se p oblems on ne wo ks usually consis in de e mining in o ma ion abou he ne wo k
2Some In e se P oblems on Fini e Ne wo ks
such as i s opology and/o he alues o he admi ance a i s edges om ce ain measu ed
unc ions o po en ial, cu en and/o powe , and some imes alongside addi ional known
in o ma ion.
The objec i e o Chap e 1 is o es ablish a e sion o disc e e ec o calculus on ne -
wo ks, which gi es us he amewo k o o mula e he in e se p oblems ha we s udy in his
ex , and also o in oduce concep s and esul s ha we use o sol e hose p oblems. O e
ime, many au ho s ha e p oposed di e en app oaches o de ine a disc e e ec o calculus
on ne wo ks acco ding o hei needs and aims. On he one hand, in he a ea o nume ical
me hods o sol ing bounda y p oblems, he so-called Mime ic Me hods desc ibe how ini e
di e ence schemes on logically ec angula g ids can be ela ed o an ope a ional calculus
ha ollows he lines o di e en ial ope a o s, see o example [68, 69, 90]. In he ield o
ini e o in ini e ne wo ks o g aphs, he ec o calculus ollows he guidelines o Algeb aic
Topology, see o ins ance [59, 74], especially when he g aphs a e pa o simplicial com-
plexes. The conside a ion o some bounda y alue p oblems on g aphs and ne wo ks, and
hei a ia ional ea men also led o he conside a ion o some ope a o s as de i a i e, no -
mal de i a i e, Laplacian, G een ope a o and G een unc ions, see o ins ance [44, 46, 67].
In he las decade, he need o deal wi h i egula g aphs and abs ac da a wi h i egula
in e ela ionships has e i ed he in e es in ec o calculus on g aphs and ne wo ks, see
[74, 84]. A good desc ip ion o he in e es o hese me hodologies can be ound on he
websi e [100], especially de o ed o i s use in image modeling.
I is in e es ing o no e ha mos o he abo e men ioned pape s igno e de elopmen s
made by o he g oups. Fo example, he heo e ical desc ip ion made on he web [100] is
e y simila o he one p oposed in [47], al hough his pape is absen om he e e ences.
Fu he mo e, all he au ho s seem o be unawa e o he sys ema ic wo k ha Japanese
geome e s and analys s ha e de eloped since he he las decades o he pas cen u y, see
as example [70]. Ano he common ea u e o mos ec o calculus de eloped on g aphs and
ne wo ks is ha he ec o ields a e iden i ied wi h unc ions on he edge se and he e o e
limi ed o lows. This allows he o mula ion o G een’s iden i ies, bu no he Di e gence
Theo em, and also limi s he s udy o he so-called pu ely esis i e ne wo ks.
In [18, 20, 35, 36], he au ho s in oduced a disc e e ec o calculus o DC ne wo ks
ollowing he guidelines o di e en ial geome y, whose cen al concep is he in oduc ion
o he angen space a each e ex o he ne wo k. Wi h his concep , he au ho s ob ain
disc e e e sions o se e al di e en ial ope a o s, ec o ields, and bounda y alue p oblems
ha mimic he p ope ies o i s con inuum analogues. The e sion p oposed he e ex ends
ha wo k o he case o AC ne wo ks, wi h some modi ica ions.
In Sec ion 1.1 we s a by in oducing he gene al p ope ies o he ec o spaces and
ope a o s ha we use h oughou he documen . Then, in Sec ion 1.2 we s udy se e al
opological and geome ical concep s associa ed o a g aph wi hou conside ing any weigh ing
on he edge se . Those concep s include he angen space a a e ex, di e ence ope a o s
such as he de i a i e and di e gence, ha a e analogous in he disc e e se ing o he
di e en ial ope a o s wi h he same name o he con inuous calculus, and he bounda y o a
se o e ices.
In Sec ion 1.3 we se he undamen als o he disc e e calculus on ne wo ks. We conside
he concep s in oduced in he p e ious sec ion, which only depend on he ne wo k opology,
In oduc ion 3
and we in oduce o he di e ence ope a o s depending on he opology and admi ance which
a e analogous o he g adien , o he no mal de i a i e, and o he Laplace-Bel ami ope a o .
Wi h hose ope a o s we can explain he physical laws ela ing he po en ial, cu en and
powe injec ed a he whole ne wo k, (see Rema k 1.3.8). We p o e ha he ope a o s
in oduced sa is y disc e e e sions o he G een Iden i ies and Gauss’ Theo em.
Then, in Sec ion 1.4 we s udy he Di ichle and Poisson p oblems on a subse F⊆V
o he e ices o a ne wo k Γ, and hei associa ed G een and Poisson ope a o s. We
ex end he o mula ion o [35] o conside Di ichle and Poisson p oblems on a subse ha
is no necessa ily connec ed. The s udy o hose p oblems allow us o in oduce in Sec ion
1.5 he Di ichle - o-Neumann map o Γ and F. Unde he condi ion ha he e is ze o
injec ed cu en a he e ices o F o any po en ial, his ope a o gi es us he linea
ela ionship be ween he po en ial and he espec i e injec ed cu en a Fc=V F,i.e.,
a he complemen a y se o F. We ex end he de ini ion o [35] o conside also ne wo ks
wi h edges be ween e ices o Fc.
Sec ion 1.6 is dedica ed o su ey p e ious esul s om [9] and [35] o mono onici y o
eal unc ions on DC ne wo ks in o de o p o e addi ional p ope ies o he Di ichle - o-
Neumann map o a DC ne wo k. In pa icula , we ha e ha any Di ichle - o-Neumann
map is he Laplacian ( he disc e e analogous o he Laplace-Bel ami ope a o ) o ano he
ne wo k, he K on educ ion o Γwi h espec o F. We show ha o AC ne wo ks, he
p e ious esul is no always ue, bu i is ue when Fc={x, y} ⊂ V. In Sec ion 1.7
we in oduce he e ec i e admi ance be ween wo e ices xand y om he Di ichle - o-
Neumann map o Γ and F=V {x, y}, and he e o e, by he p e ious esul , we can ela e
i o a K on educ ion o Γ.
Chap e 2 is dedica ed o s udy he in e se conduc ance p oblem on a DC ne wo k,
which is he disc e e e sion o he con inuous Calde ´on p oblem. In 1980, A.P. Calde ´on
published he seminal pape “On an in e se bounda y alue p oblem” ([34]), which has mo-
i a ed nume ous de elopmen s in in e se p oblems. Calde ´on’s p oblem es ablishes whe he
he elec ical conduc i i y o a medium can be de e mined by making ol age and cu en
measu emen s a he bounda y.
The p oblem a hand in ol es an unknown conduc i i y ha needs o be de e mined and
possibly econs uc ed using bounda y measu emen s o cu en and ol age. This in iguing
challenge has ga ne ed signi ican a en ion due o i s wide ange o applica ions in di e se
ields, including nonin asi e medical imaging, which s ands as one o he mos complex and
compelling a eas o in e es (see [4, 42, 82, 91]).
Calde ´on’s p oblem is se e ely ill-posed, and signi ican e o s a e being made o de elop
algo i hms ha can accu a ely sol e i . This includes op imiza ion algo i hms, heu is ic
me hods, and machine lea ning echniques, (see [24, 41]).
The disc e e in e se conduc ance p oblem consis s in de e mining he conduc ance o a
DC ne wo k om i s Di ichle - o-Neumann map. We s udy he p oblem o well-connec ed
spide ne wo ks, which a e a sub amily o c i ical ci cula plana ne wo ks and we e i s
in oduced in [54] because o hei ema kable p ope ies. In [51, 52, 53, 54, 55] i was
es ablished ha o c i ical plana ne wo ks he p oblem has a unique solu ion. They also
in oduced an explici me hod o sol e he p oblem o well-connec ed spide ne wo ks om
10 Disc e e ec o calculus on ne wo ks
de ined a e a labeling o V, bu i is clea ly independen o i . Mo eo e , he ace is also
clea ly independen o any labeling on V.
Gi en x, y ∈V, we deno e as K(x, y) he en y o he ma ix Kco esponding o e ices
xand y, ha is, he en y K(x, y) o he ke nel K. Mo e gene ally, gi en a pai o subse s
F1, F2⊆V, we de ine he subma ix o K:K(F1;F2) = K(x, y)(x,y)∈F1×F2.
We call ope a o o any linea applica ion K:P−→ Qbe ween wo ini e dimensional
complex o eal ec o spaces wi h inne p oduc Pand Q. I s null space is he subspace
o Pde ined as ke (K) = {u∈Psuch ha K(u)=0}. I s image is he subspace o Q
de ined as Img(K) = {K(u) such ha u∈P}. When P=Q, we say ha K:P−→ Pis
an ope a o on P. The ollowing esul s a e ex ensions o esul s o ope a o s om [17] o
include he complex case.
Gi en an ope a o K:P−→ Q, we deno e by K∗:Q−→ Pi s adjoin , which is he
ope a o uniquely de e mined by he ela ion
⟨K(u), ⟩=⟨u, K∗( )⟩,
o all u∈Pand ∈Q.
The ollowing esul is a consequence ha ollows almos immedia ely om he p e ious
ela ion.
Lemma 1.1.1 (F edholm al e na i e).I Kis an ope a o on P, hen we ha e ha
Img(K) = ke (K∗)⊥.
Gi en an ope a o Kon P, we say ha u∈Pis an eigen ec o o Ki u= 0 and he e
exis s λ∈Csuch ha K(u) = λu. In ha case, λis called he eigen alue o Kassocia ed
o he eigen ec o u. The numbe o eigen alues o Kis a mos dim(P).
We say ha an ope a o Kon Pis sel -adjoin i K∗=K. I Kis sel -adjoin , hen
⟨K(u), u⟩ ∈ R o e e y u∈P. Mo eo e , each eigen alue o Kis eal, and he e is a basis
u1, ..., udim(P)o Psuch ha each ujis an eigen ec o o K, and uj⊥ukwhene e j=k.
We say ha Kis posi i e semide ini e, espec i ely nega i e semide ini e, i ⟨K(u), u⟩ ≥
0, espec i ely ⟨K(u), u⟩ ≤ 0, o e e y u∈C(V, C). I Kis posi i e semide ini e, espec-
i ely nega i e semide ini e, hen each eigen alue o Kis nonnega i e, espec i ely nonpos-
i i e.
Le K:P−→ Qbe an ope a o , and le m= min {dim(P),dim(Q)}. Then K∗◦K
is a sel -adjoin and posi i e semide ini e ope a o on P. We deno e i s eigen alues by
λ1≥... ≥λdim(P)≥0. The singula alues o Ka e he nonnega i e numbe s σj=pλj
o each j= 1, ..., m. Then, we de ine he condi ion numbe o Kas κ(K) = σ1/σm. We
ha e ha κ(K) = ∞i Kis singula , i.e., i ke (K)={0}. We also de ine he spec al
no m o Kas i s la ges singula alue, ∥K∥2=σ1.
Le Kbe a sel -adjoin ope a o on C(V), espec i ely on C(V, Rm). Then, by he
Cou an -Fishe heo em [94], we ha e ha he maximum o he eigen alues o Kis equal
o
Func ion spaces 11
max
||u||=1 {⟨K(u), u⟩}. Also, o any u∈C(V), espec i ely u∈C(V, Rm), we ha e ha
∥K(u)∥≤∥K∥2∥u∥.
We deno e by C:C(V, C)−→ C(V, C) he conjuga ion applica ion, ha is de ined by
C(u) = ¯u o each u∈C(V, C). We say ha K:C(V, C)−→ C(V, C) is a symme ic
ope a o i K∗=C ◦ K◦ C [83], o equi alen ly i K=C ◦ K∗◦ C. I we es ic he
de ini ion o ope a o s in C(V), Cis he iden i y, so being symme ic and sel -adjoin is
equi alen .
Gi en an ope a o Kon C(V) o on C(V, C), we de ine i s eal and complex pa s as
ℜ(K) = 1
2(K+K∗) and ℑ(K) = 1
2i(K−K∗), espec i ely. I is clea ha hey a e
sel -adjoin ope a o s and K=ℜ(K) + iℑ(K), (see [49]).
Lemma 1.1.2. I Kis a symme ic ope a o on C(V)o on C(V, C), hen ℜ(K)|C(V)and
ℑ(K)|C(V)a e ope a o s on C(V).
P oo . Le Kbe a symme ic ope a o and u∈C(V). Then, K∗=C ◦K◦C and u=u,
so on one hand
ℜ(K)(u) = C ◦ℜ(K)C(u)=1
2C ◦(K+K∗)◦C(u)
=1
2C ◦K◦C +C ◦K∗◦C(u) = 1
2(K∗+K)(u) = ℜ(K)(u),
and on he o he hand
ℑ(K)(u) = C ◦ℑ(K)C(u)=−1
2iC ◦(K−K∗)◦C(u)
=1
2iC ◦K∗◦C −C ◦K◦C(u) = 1
2i(K−K∗)(u) = ℑ(K)(u).
I Kis a eal, espec i ely complex, ke nel on F, we de ine he in eg al ope a o associ-
a ed wi h Kas he endomo phism K:C(F)−→ C(F), espec i ely as he endomo phism
K:C(F, C)−→ C(F, C), ha assigns o each u∈C(F), espec i ely u∈C(F, C), he
unc ion K(u)(x) = ZF
K(x, y)u(y)dy o all x∈V.
The ela ionship be ween ke nels, in eg al ope a o s and endomo phisms o C(F) is gi en
by he ollowing esul . I s i s pa can be seen as a disc e e e sion o he Schwa z’s Ke nel
Theo em, because o he na u al iden i ica ion be ween C(F) and i s dual space.
P oposi ion 1.1.3 (Ke nel Theo em [19, P op. 5.1]).Each endomo phism Ko C(F),
espec i ely C(F, C), is an in eg al ope a o associa ed wi h a eal, espec i ely complex,
ke nel Kon Fwhich is uniquely de e mined by he ela ion K(x, y) = K(εy)(x) o each
(x, y)∈F×F.
Mo eo e , i Kis he in eg al ope a o on Fassocia ed o he ke nel Kand Ais a non
emp y subse o F, hen he ollowing s a emen s hold:
(i) The adjoin o K,K∗, is he ope a o associa ed wi h he ke nel K∗. The e o e, K
is sel -adjoin i Kis sel -adjoin .
12 Disc e e ec o calculus on ne wo ks
(ii) The ope a o C◦K∗◦C is associa ed wi h he ke nel K⊤. The e o e, Kis symme ic
i Kis symme ic.
(iii) Img K⊆C(A)i K∈C(A×F).
(i ) C(F A)⊆ke Ki K∈C(F×A).
In pa icula , each endomo phism o C(V), espec i ely C(V, C), is he in eg al ope a o
associa ed o some ke nel. Gi en K,Jendomo phisms o C(V), espec i ely o C(V, C),
whose ke nels a e espec i ely Kand J, hen he ke nel o K◦Jis K◦J, de ined o 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 addi ion, we can de ine he ace on he space o endomo phisms o C(V) o C(V, C)
as (K) = (K), whe e Kis he ke nel o K. F om his de ini ion, we can endow he
space o endomo phisms o C(V) o o C(V, C), and as a consequence he space o ke nels
C(V×V) o C(V×V, C), wi h a na u al inne p oduc : i Kand Ja e he ke nels associa ed
o he ope a o s Kand J espec i ely, hen
⟨K,J⟩= (K◦J∗) = ZV⟨Jx, Kx⟩dx = (K∗◦J).
In pa icula , ⟨K,J⟩=⟨K∗,J∗⟩. The associa ed no m on he space o endomo -
phisms, o on he space o ke nels, is named F obenius no m and deno ed as ||·||F . The e o e,
||K||F =||K||F = (K∗◦K)1
2.
1.2 Topology and geome y o a g aph
In his sec ion we will p esen se e al opological and geome ical concep s associa ed o a
g aph. We s a wi h he basic de ini ions, (see [19, 35] o a de ailed discussion). Al hough
almos all concep s we nex in oduce can be de ined in in ini e and locally ini e g aphs,
e e y g aph h oughou his wo k will be ini e, undi ec ed and simple.
A g aph is a pai G= (V, E) whe e Vis a ini e nonemp y se called e ex se , and
E⊆{x, y}such ha x, y ∈Vand x=yis called edge se .
A e ex is any x∈V. We say ha x, y ∈Va e adjacen i {x, y} ∈ Eand usually we
deno e i as x∼y. We will deno e {x, y} ∈ Ealso by exy and so, exy =eyx. In Figu e 1.1,
we show he ep esen a ion o some examples o g aphs.
We de ine he subspaces o ke nels C(G) = { ∈C(V×V)| (x, y) = 0 i exy /∈E},
C(G, C) = { ∈C(V×V, C)| (x, y) = 0 i exy /∈E}and C+(G) = { ∈C+(V×
V)| (x, y) = 0 i exy /∈E}. The subspaces o symme ic ke nels o C(G), C(G, C) and
C+(G) can be iden i ied wi h he unc ion spaces on he edge se C(E), C(E, C) and C+(E),
espec i ely.
Topology and geome y o a g aph 13
Figu e 1.1: Examples o (locally ini e) g aphs
We say ha a subse F⊆Vis connec ed i o any x, y ∈F he e exis s a pa h con ained
in F om x o y, ha is, a ( ini e) sequence o e ices x0, . . . , xk∈Fsuch ha x0=x,
xk=yand exj−1,xj∈E o all j= 1, . . . , k. We say ha a g aph is connec ed i Vis
connec ed. We say ha wo dis inc e ices x, y ∈Va e connec ed h ough Fi he e exis s
a pa h om x o ysuch ha e e y e ex o he pa h dis inc om xo ybelongs o F.
Gi en a g aph G= (V, E), and a subse F⊆V, we deno e by GF he induced subg aph
GF= (F, EF) wi h e ex se F, and only he se o edges o Gwhich a e adjacen o wo
e ices o F,i.e.,EF={exy ∈Esuch ha x, y ∈F}.
The e is a unique pa i ion o V=V1⊔... ⊔Vs, wi h s≥1, such ha E=EV1⊔... ⊔EVs
and GViis connec ed o i= 1, ..., s. We call each GVi, o Vi, a connec ed componen o G
and w i e G=GV1⊔... ⊔GVs.
Gi en x, y ∈V, we deno e by d(x, y) he geodesic dis ance in he g aph, ha is de ined
as he minimum leng h o all pa hs om x o yi xand ybelong o he same connec ed
componen o Gand as d(x, y) = ∞o he wise. I is clea ha dgi es a s uc u e o me ic
space o he se o e ices o each connec ed componen o he g aph and ha d(x, y)=1
i x∼y.
Gi en x∈V, i s combina o ial deg ee k(x) is he numbe o e ices adjacen o x, ha
is k(x) = |{y∈V:y∼x}|.
14 Disc e e ec o calculus on ne wo ks
1.2.1 Tangen bundle o a g aph
We ollow he app oach o [35, 36], in which he opological and geome ical concep s in a
g aph a e based on he de ini ion o a angen space a each poin o a g aph. The main
di e ence o ou app oach is ha we conside he angen space as a complex ec o space
wi h he s anda d inne p oduc , ins ead o a eal ec o space.
We de ine he angen space Tx(G) o a e ex xas he complex ec o space o o mal
linea combina ions o he se o edges {exy ∈E:y∼x}. The dimension o Tx(G) is k(x),
and he se o hose edges is a basis o Tx(G), ha we call i s coo dina e basis. In Figu e 1.2
we show he coo dina e basis a a e ex.
Tx(G)
x
x
Figu e 1.2: G aph and angen space a e ex x.
A ec o ield on he g aph is any unc ion :V−→ S
x∈V
Tx(G) wi h he p ope y ha
o e e y x∈V, (x)∈Tx(G). We deno e he space o ec o ields by X(G). The suppo
o is de ined as supp( ) = {x∈V: (x)=0}.
A ec o ield ∈ X(G) is uniquely de e mined by i s componen s in he coo dina e
basis, so we can de ine a ke nel ∈C(G, C), which is called he componen unc ion o ,
such ha o any x∈V, (x) = X
y∼x
(x, y)exy.This associa ion be ween and de ines
an isomo phism be ween X(G) and C(G, C). The e o e, we can de ine he symme ic and
an isymme ic componen s o ∈ X(G), sand a, as he ec o ields associa ed wi h s
and a, espec i ely. No e ha = s+ a. We say ha is symme ic i = sand ha
is an isymme ic, o a low, i = a.
Gi en u∈C(V, C) and ∈ X(G) wi h componen unc ion , we deno e by u ∈ X(G)
he ec o ield whose componen unc ion is u ∈C(G, C).
We de ine he inne p oduc o ,g∈ X(G) as
⟨ ,g⟩=1
2ZV
[ (x),g(x)] dx,
whe e o any x∈Vwe deno e by [ (x),g(x)] he inne p oduc on Tx(G) de e mined by
Topology and geome y o a g aph 15
he o hono mali y o i s coo dina e basis, i.e., o any y, z such ha y∼xand z∼x, hen
[exy, exz] = εy(z). As a consequence, i and ga e he espec i e componen unc ions o
and g, hen
[ (x),g(x)] = X
y∼x
(x, y)g(x, y) = X
y∈V
(x, y)g(x, y).
We ha e included he ac o 1
2in he de ini ion o he inne p oduc o X(G) because
each edge is conside ed wice. In pa icula , including ha ac o we will a oid ge ing a
ac o 2 mul iplying he sum in he esul o Lemma 1.2.2.
Lemma 1.2.1. I ∈ X(G)is symme ic and g∈ X(G)is a low, hen ⟨ ,g⟩= 0. As a
consequence, gi en any ,g∈ X(G), we ha e ha ⟨ ,g⟩=⟨ s,gs⟩+⟨ a,ga⟩.
P oo . Le ∈ X(G) be symme ic and g∈ X(G) be a low. Then, we ha e
⟨ ,g⟩=1
2ZV×V
(x, y)g(x, y)dydx =−1
2ZV×V
(y, x)g(y, x)dxdy =−⟨ ,g⟩.
The second s a emen ollows i ially om he p ope ies o any inne p oduc .
The ollowing esul is s aigh o wa d.
Lemma 1.2.2. Le bo h ,g∈ X(G)be ei he symme ic ec o ields o lows, wi h compo-
nen unc ions and g. Then:
⟨ ,g⟩=X
exy∈E
(x, y)g(x, y).
No e ha he sum in Lemma 1.2.2 is well de ined because i bo h and ga e symme ic
o a e lows, hen (x, y)g(x, y) = (y, x)g(y, x) o e e y x, y ∈V.
Rema k 1.2.3. Due o he isomo phism be ween C(G, C) and X(G), he inne p oduc
on X(G) de e mines an inne p oduc on C(G, C) de ined o each , g ∈C(G, C) as ⟨ ,g⟩,
whe e ,g∈ X(G) a e he ec o ields whose componen unc ions a e and g, espec i ely.
The no m associa ed wi h his inne p oduc is || || =⟨ , ⟩1
2. This inne p oduc is di e en
han he es ic ion o C(G, C) o he one in he space o ke nels C(V×V, C) de ined a he
end o Sec ion 1.1 om he inne p oduc on he space o endomo phisms, whose associa ed
no m is || ||F . Th oughou he whole ex , whene e we conside he no m o a ke nel
∈C(G, C) o a g aph G, we will use ha i s no m || || a he han he F obenius one.
I is symme ic, by Lemma 1.2.2 we ha e ha || ||2=P
exy∈E| (x, y)|2.
1.2.2 Di e ence ope a o s on a g aph
Now, we will de ine he de i a i e and di e gence as disc e e di e ence ope a o s on a g aph.
They a e analogous o he di e en ial ope a o s wi h he same name in he con inuous ec o
calculus.
16 Disc e e ec o calculus on ne wo ks
We de ine he de i a i e [35] as he linea map d:C(V, C)−→ X(G), which assigns o
each u∈C(V, C) he low du, such ha o each x∈V,du(x) = P
y∼x
(u(y)−u(x))exy.
Analogously o he con inuous case, du= 0 i u∈C(V, C) is cons an wi hin each
connec ed componen o G.
We de ine he di e gence as he linea map di =−d∗:X(G)−→ C(V, C). Namely, o
any ∈ X(G), di ( )∈C(V, C) is he unc ion de e mined by:
⟨di ( ), u⟩=ZV
di ( )u dx =−1
2ZV
[ (x),du(x)] dx =−⟨ ,du⟩(1.1)
Le G=GV1⊔... ⊔GVsbe he decomposi ion o Gin i s connec ed componen s. Fo any
i= 1, ..., s, subs i u ing u=χViin he p e ious exp ession, we ha e RVidi ( )dx = 0 o any
∈ X(G). In pa icula , RVdi ( )dx = 0 o any ∈ X(G).
In [36], o any weigh ing ω∈C+(V) on he se o e ices, he au ho s de ine an inne
p oduc on C(V) associa ed o ω. Then, hey de ine he di e gence as di =−d∗wi h
espec o ha inne p oduc . We do no conside any weigh ing on he e ices, al hough
when we es ic he di e gence o eal ec o ields, ou de ini ion o di e gence ag ees wi h
he one in [36] when he weigh ing ωis equal o one. In [35], he di e gence is in oduced
in a di e en manne because he au ho s conside an inne p oduc on he angen space
a a e ex which is dependen on he elec ical conduc ance on he edges. Ne e heless,
ha de ini ion o di e gence u ns ou o be independen o he conduc ance and i is also
equi alen o ou de ini ion when we es ic i o eal ec o ields. As a consequence, ou
de ini ion sa is ies he ollowing p oposi ion om [35].
P oposi ion 1.2.4. I ∈ X(G)and ∈C(G, C)is i s componen unc ion, hen o any
x∈V:
di ( )(x) = X
y∼x
a(x, y) = X
y∈V
a(x, y).
P oo . I o any x∈Vwe subs i u e u=εxin (1.1), hen we ge
di ( )(x) = ⟨di ( ), εx⟩=⟨ ,−dεx⟩=⟨ a,−dεx⟩,
whe e he las equali y ollows om Lemma 1.2.1. By de ini ion, o any z∈V,−dεx(z) =
P
y∼z
(εx(z)−εx(y))ezy. The componen unc ion o he low −dεxis −dεx(z, y) = εx(z)−εx(y),
which is nonze o only i y∼zand zo ya e equal o x. Mo eo e , −dεx(x, y) = 1, so, by
Lemma 1.2.2:
di ( )(x) = −X
exy∈E
a(x, y)dεx(x, y) = X
y∼x
a(x, y).
Topology and geome y o a g aph 17
1.2.3 Bounda y o a se
A subse o e ices F⊆Vo a g aph can be seen as he disc e e analogue o a compac
mani old. In [35, 36] he e a e disc e e concep s analogous o opological concep s in ol ing
a compac mani old such as i s in e io , bounda y, closu e, ex e io no mal ec o ield and
he Di e gence Theo em, which we e iew below.
The in e io o Fis ◦
F={x∈F:y∈Fwhen y∼x}=x∈F:{y:d(x, y)≤1} ⊂ F.
The bounda y o Fis δ(F) = {x∈Fc| ∃y∈Fsuch ha y∼x}={x∈V:d(x, F) = 1}.
The in e io bounda y o Fis δ(Fc) = F ◦
F={x∈V:d(x, Fc) = 1}.
The closu e o Fis ¯
F=F∪δ(F) = {x∈V:d(x, F)≤1}.
The Ex e io o Fis Ex (F) = V ¯
F={x∈V:d(x, F)>1}.
The Figu e 1.3 shows a e ex se Fin ligh b own colo and i s bounda y in och e colo .
Ve ices in ◦
F,δ(F), δ(Fc) o Ex (F) a e depic ed in di e en colo .
F
δ(F)
Figu e 1.3: ◦
F(blue), δ(F) (o ange), δ(Fc) (g een) and Ex (F) (ligh g ey).
Obse e ha o de ine he abo e geome ic no ions, he (possible) edges be ween bound-
a y e ices play no ole. Fo his eason his kind o edges a e depic ed in ligh g ey in
Figu e 1.3
The no mal ec o ield o F is he low nF=−dχF. Hence, i s componen unc ion in
C(G, C) is gi en by
nF(x, y) =
1, y ∼xand (x, y)∈δ(Fc)×δ(F)
−1, y ∼xand (x, y)∈δ(F)×δ(Fc),
0,o he wise
As a consequence, nFc=−nFand supp(nF) = δ(Fc)∪δ(F). The e o e, gi en x∈F,nF(x)
only akes in o accoun he edges exy such ha y∈Fand hence nFhas he meaning o
ex e io no mal ield.
The concep o he no mal ield o a se Fappea s o he i s ime in he li e a u e
in [20], al hough i had al eady been used p e iously by he au ho s. Wi hou he ec o
18 Disc e e ec o calculus on ne wo ks
ield o malism conside ed he e, he no ion o no mal de i a i e was al eady p esen in many
wo ks ela ed o G aph Analysis, see o example [22, 44, 47, 67] whe e he au ho s in oduce
he no ions mo e o less independen ly o each o he . In ac , hese au ho s igno e he wo k
o M. Yamasaki and collabo a o s, who in oduced se e al yea s ea lie a simila concep
ela ed o he in e io no mal de i a i e, see [70] and e e ences he ein.
In Figu e 1.4 we conside he same se Fas in Figu e 1.3 and show ha di e en e ices
on he bounda y could ha e di e en numbe o edges joining hem wi h e ices in F.
Figu e 1.4: xhas wo edges and zhas one edge joining hem wi h e ices in F.
The mo i a ion o in oduce he no mal ield was o exp ess he no mal de i a i e o a
unc ion as he inne p oduc o i s de i a i e wi h a ield ep esen ing he ex e io no mal,
hus mimicking di e en ial calculus wi h he aim o p o ing he di e gence heo em and
G een’s iden i ies. All he men ioned au ho s ha e hei e sion o he G een Iden i ies, see
he nex sec ion, bu none o hem p esen some hing simila o he Di e gence Theo em,
due o he absence o he no ion o no mal ield. As he p oo o his esul included in [20] is
gi en in a mo e gene al se ing ha ha conside ed in his wo k, we include he e i s p oo .
P oposi ion 1.2.5. (Di e gence Theo em) Fo any ∈ X(G), i is e i ied ha
ZF
di ( )dx =Zδ(F)
[ a(x),nF(x)] dx.
P oo . By he de ini ion o di e gence and no mal ec o ield, and by Lemma 1.2.1, we ha e
ZF
di ( )dx =⟨di ( ), χF⟩=−⟨ ,dχF⟩=−⟨ a,dχF⟩=⟨ a,nF⟩.
Deno ing by he componen unc ion o , om Lemma 1.2.2 we ge
⟨ a,nF⟩=X
(x,y)∈δ(Fc)×δ(F)
a(x, y) = Zδ(F)
[ a(x),nF(x)] dx.
Topology and geome y o a g aph 19
De ini ion 1.2.6. We say ha a g aph G= (V, E) is a g aph wi h bounda y i he e is a
p ope subse F⊂Vsuch ha V=¯
Fand he bounda y δ(F) is o ally disconnec ed, i.e.,
Gδ(F)= (δ(F),∅).
Well-connec ed spide g aphs
Now we will in oduce di e en subse s o g aphs wi h bounda y, in o de o illus a e he
p e ious concep s and, in pa icula , o de ine he well-connec ed spide g aphs. Such g aphs
we e ini ially in oduced in [54] due o hei excep ional cha ac e is ics and will be he ype
o g aphs wi h bounda y on which we will o mula e he in e se p oblem in Chap e 2.
A ci cula plana g aph [51] is a g aph wi h bounda y G= ( ¯
F, E) which can be plana ly
embedded (i.e., wi hou c ossing edges) in a disk D⊂R2, wi h he e ices wi hin se Flo-
ca ed in he in e io o D(◦
D) and he bounda y e ices o δ(F) loca ed in he ci cum e ence
o D(∂D).
Now, le G= ( ¯
F, E) be a ci cula plana g aph and we ix an embedding o i wi h he
cha ac e is ics o he las pa ag aph. A ci cula pai is a pai (Ξ; Σ) = (ξ1, ..., ξs;σ1, ..., σs)
o disjoin subse s o δ(F) such ha he sequence (ξ1, ..., ξs, σ1, ..., σs) is in clockwise o de .
A ci cula pai (Ξ; Σ) is connec ed h ough Fi he e a e sdisjoin pa hs ϱ1, ..., ϱssuch ha
each ϱjs a s a ξj, ends a σjand, apa om hese wo, passes only h ough e ices o F
[51].
We conside he p ocess o con ac ing an edge exy ∈E, wi h x∈F, om a ne wo k
wi h bounda y G= ( ¯
F, E), which consis s in c ea ing he g aph G′= (F′, E′) such ha
F′=F {x}and E′=E exz such ha z∈F∪{eyz such ha exz ∈Eand z=y}.
No e ha δ(F′) = δ(F). We also conside he p ocess o emo ing he edge exy ∈E
om G= ( ¯
F, E), which consis s in c ea ing he g aph G′= (F′, E′), wi h F′=Fand
E′=E {exy}.
We say ha a ci cula plana g aph Gis a c i ical ci cula plana g aph i he ope a ion
o emo ing any edge o he ope a ion o con ac ing any edge o a single e ex esul s in a
g aph G′such ha he e is a leas one ci cula pai ha is connec ed h ough Fin Gand
i is no connec ed h ough F′in G′(see [51]).
In [48], he au ho in oduced he no ion o well-connec ed g aph, which is a ci cula
plana g aph in which e e y ci cula pai is connec ed h ough F.
Awell-connec ed spide g aph G= ( ¯
F, E) wi h ℓ≥0 ci cles and m= 4ℓ+ 3 adii is a
pa icula example o a c i ical ci cula plana g aph, which is he g aph co esponding o
he ollowing plana embedding. We s a by placing a e ex se in he cen e o a disk D
and he mbounda y e ices o δ(F) in ∂D. Nex , we d aw s aigh lines, e e ed o as
adii, om he cen al e ex o each o he bounda y e ices. Then, we d aw ℓdis inc
concen ic ci cum e ences con ained wi hin he in e io o Dwhose cen e is he cen e o D.
Now, we place a e ex o e e y in e sec ion poin o e e y ci cle and adius. The g aph’s
edges a e de e mined by hese adii and ci cles, as shown in Figu e 1.5.
26 Disc e e ec o calculus on ne wo ks
Rema k 1.3.8. The physical laws go e ning he cu en ansmission in elec ical ne wo ks
can be s a ed using he di e ence ope a o s ha we ha e de ined. Fo AC ne wo ks, he
po en ial in he ne wo k can be ep esen ed by a unc ion u∈C(V, C). Then, by Ohms’
law, −∇u ep esen s he low o elec ical cu en . Tha is, each o he coe icien s in he
coo dina e basis o −∇u(x) is equal o he cu en lowing om x o each o i s neighbou s.
Also, by Ki chho ’s Cu en Law, L(u) is he unc ion assigning o each e ex he cu en
injec ed a i when he po en ial a he ne wo k is u. Then, uL(u) is he unc ion assigning
o each e ex he appa en powe injec ed a i when he po en ial a he ne wo k is u, and
hus E(u, u) is equal o he o al powe dissipa ed a he ne wo k when he po en ial is u.
Fo DC ne wo ks, he po en ial in he ne wo k can be ep esen ed by u∈C(V) and he es
o esul s a e analogous, wi h he addi ional esul ha he dissipa ed powe in he ne wo k
is always nonnega i e.
1.4 Bounda y alue p oblems
The objec i e o his sec ion is o e iew se e al esul s abou he Di ichle and Poisson
p oblems on DC ne wo ks ha can be ound in [17, 35, 36], and o ex end hem o he case
o AC ne wo ks. We s udy he ollowing p oblem.
Gi en an elec ical ne wo k Γ,F⊆V,h∈C(F, C)and g∈C(Fc,C), ind u∈C(V, C)
such ha
L(u) = hon F, u =gon Fc.(1.4)
When F=V his is called he Poisson p oblem and when F⊊V his is called he
Di ichle p oblem. We ha e ha Fc=δ(F)⊔Ex (F), bu because he alues o he Laplacian
o a unc ion a Fonly depend on he alues o he unc ion a ¯
F, he se o solu ions o
(1.4) only depends on he alues o ga δ(F), so i is called a bounda y alue p oblem on F.
The associa ed homogeneous bounda y alue p oblem consis s in inding u∈C(V, C)such
ha
L(u) = 0 on F, u = 0 on Fc.(1.5)
Lemma 1.4.1. Le Γ = ΓV1⊔... ⊔ΓVsbe he decomposi ion in connec ed componen s o Γ.
Then, he se o solu ions o he homogeneous bounda y alue p oblem (1.5) is he ec o
subspace Vo C(F, C)spanned by nχVisuch ha Vi⊆Fo.
P oo . Clea ly, any unc ion o Vis a solu ion o (1.5). Now, le u∈C(F, C) be a solu ion
o (1.5). Then,
E(u, u) = ZV
uL(u)dx =ZF
uL(u)dx +ZFc
uL(u)dx = 0,
so uis a linea combina ion o χV1, ..., χVs. As u= 0 in Fc,umus be equal o ze o in
each Visuch ha Vi∩Fc=∅, so u∈ V.
Bounda y alue p oblems 27
P oposi ion 1.4.2. Le Γ=(V, a)be an elec ical ne wo k and le Γ=ΓV1⊔... ⊔ΓVsbe i s
decomposi ion in connec ed componen s. Then, (1.4) has a solu ion i and only i ZVi
h dx = 0
o each isuch ha Vi⊆F. Mo eo e , i he p oblem has a solu ion, hen he e is a unique
solu ion such ha ZVi
dx = 0 o each isuch ha Vi⊆F.
P oo . In he case (1.4) has a solu ion, hen, o any solu ion u, he se o all i s solu ions is
u+V.
Conside he p oblem (1.4) o inding u∈C(V, C)such ha
L(u) = h−L(g) on F, u = 0 on Fc.(1.6)
Then uis a solu ion o (1.6) i u+gis a solu ion o (1.4).
We deno e by M:C(F, C)−→ C(F, C) he linea ope a o M(u) = L(u) on F o each
u∈C(F, C). Conside ing he inne p oduc on C(F, C) induced by he s anda d one on
C(V, C), we ha e ha , o e e y u, ∈C(F, C):
⟨M(u), ⟩=ZF
M(u) dx =ZVL(u) dx =ZV
uL( )dx =ZF
uM( )dx =⟨u, M( )⟩,
so M∗=C ◦M◦C, and hus Mis a symme ic ope a o . Now, ke (M) = V. Mo eo e ,
u∈ke (M∗) i M(u) = 0, ha is, i u∈ke (M). As u∈ V i u∈ V, we ha e ha
ke (M) = ke (M∗), and, by he F edholm al e na i e, Img(M) = V⊥.
Then, (1.6) has a solu ion i ⟨h− L(g), χVi⟩= 0 o each isuch ha Vi⊆F. This is
equi alen o saying RVih dx =RViL(g)dx = 0 o each isuch ha Vi⊆F, and he las
equali y ollows om Gauss’ Theo em.
To p o e he uniqueness, we see ha he e is a unique solu ion w o (1.6) such ha
w∈ V⊥. This is equi alen o ha =w+gis he only solu ion o (1.4) sa is ying ha
ZVi
dx =ZVi
w dx = 0
o each isuch ha Vi⊆F.
We say ha a unc ion uis ha monic on Fwhen L(u) = 0 on F. The pa icula case o
(1.4) in which h= 0 consis s in, gi en he alues o a unc ion a Fc, seeking o an ex ension
o he unc ion a F ha is ha monic on F. In his case, any solu ion mus be cons an on
each isuch ha Vi⊆F, so we ge he ollowing esul .
Co olla y 1.4.3. Gi en an elec ical ne wo k Γ,F⊆Vand g∈C(Fc,C), he bounda y
alue p oblem o inding u∈C(V, C)such ha
L(u) = 0 on F, u =gon Fc,(1.7)
always has a solu ion. Mo eo e , i has a unique solu ion ha is equal o ze o on e e y
connec ed componen o he ne wo k ha is con ained in F, ha we deno e by ug.
28 Disc e e ec o calculus on ne wo ks
Rema k 1.4.4. Le be a solu ion o (1.7). Then ∂
∂nF=∂ug
∂nF,L( ) = L(ug) and E( , ) =
E(ug, ug).
In [30], a uniqueness esul o a Di ichle p oblem ha is simila o (1.7) was ob ained.
The p oblem he e is pa ially mo e gene al han (1.7) in he sense ha hey conside he
possibili y o adding a Sch ¨odinge po en ial wi h some es ic ions and he possibili y o
ha ing nega i e suscep ance, bu i is also pa ially mo e es ic i e han (1.7) in he sense
ha hey only s udy he p oblem o connec ed ne wo ks. In he connec ed case, we ob ain
he same uniqueness esul immedia ely om Co olla y 1.4.3.
Co olla y 1.4.5. I Γis a connec ed ne wo k and h= 0, hen any Di ichle p oblem has a
unique solu ion and he se o solu ions o he Poisson p oblem is he se o cons an unc ions
on V.
Le Γ = ΓV1⊔... ⊔ΓVsbe he decomposi ion in connec ed componen s o Γ, and F⊂V.
We deno e by F0 he union o he Visuch ha Vi⊆F, and F1=F F0. Analogously o
he ope a o Mde ined in he p oo o P oposi ion 1.4.2, we deno e by MF1:C(F1,C)−→
C(F1,C) he linea ope a o such ha o each u∈C(F1,C), MF1(u) = L(u) on F1, which
is an au omo phism.
De ini ion 1.4.6. We de ine he G een ope a o o Fas J=MF1
−1, which is an au omo -
phism o C(F1,C). Fo any h∈C(F1,C), u=J(h) is he unique solu ion o he bounda y
p oblem L(u) = hon F1and u= 0 on Fc⊔F0.
We de ine he Poisson ope a o o Fas he linea ope a o K:C(Fc,C)−→ C(V F0,C)
such ha , o each g∈C(Fc,C), K(g) = ug. Tha is, K(g) is he unique unc ion sa is ying
L(K(g)) = 0 on F,K(g) = gon Fcand K(g) = 0 on F0.
Lemma 1.4.7. The G een ope a o Jis symme ic wi h espec o he inne p oduc on
C(F1,C)induced by he s anda d one on C(V, C).
P oo . Gi en g, h ∈C(F1,C), we deno e u=J(g) and =J(h). Then we ha e L(u) = g
and L( ) = hon F1, and hus:
⟨J(g), h⟩=ZF1
J(g)hdx =ZV
uL( )dx =ZVL(u) dx =ZF1
gJ(h)dx =⟨g, J(h)⟩,
so J∗=C ◦J◦C.
The ke nel J∈C(F1×F1,C) associa ed wi h he G een ope a o Jon F, is called he
G een ke nel. By he p e ious lemma, i is symme ic. The ma ix associa ed wi h MF1is
L(F1;F1), so he ma ix associa ed wi h Jis L(F1;F1)−1.
We can ex end he Poisson ope a o Kon F o an endomo phism o C(V F0,C) such
ha he image o any ec o in C(F1,C) is equal o ze o. By he Ke nel Theo em, i has an
associa ed ke nel K∈C((V F0)×Fc,C), which is called he Poisson ke nel.
The ollowing esul gi es a cha ac e iza ion o he G een and Poisson ke nels as solu ions
o bounda y alue p oblems, and a ela ion be ween hem.
The Di ichle - o-Neumann map 29
P oposi ion 1.4.8. Fo e e y y∈F1, he unc ion Jyis de e mined by L(Jy) = εyon F1.
Fo e e y y∈Fc, he unc ion Kyis de e mined by L(Ky) = 0 on F,Ky=εyon Fcand
Ky= 0 on F0. Fu he mo e,
K(x, y) = εy(x)−∂J
∂ny(x, y), o e e y x∈V F0and y∈Fc.
Mo eo e , ∂K
∂nx∈C(δ(F)×δ(F),C)and, o e e y x, y ∈δ(F),
∂K
∂nx(x, y) = εy(x)κF(x)−∂2J
∂nx∂ny(x, y).
As a consequence, ∂K
∂nxis symme ic on C(δ(F)×δ(F),C).
P oo . By he co espondence be ween ke nels and ope a o s, o e e y y∈F1,Jy=J(εy).
As Jis an au omo phism, his is equi alen o L(Jy) = 0 on F. Simila ly, o e e y y∈Fc,
Ky=K(εy) and hus u=Kyis he unique solu ion o he bounda y p oblem L(u) = 0 on
F,u=εyon Fcand u= 0 on F0. Tha p oblem is equi alen o seeking o ∈C(F1,C)
such ha L( ) = −L(εy) on F1, in he sense ha Ky=εy−J(L(εy)|F1).
Now, o e e y x∈F1,L(εy)(x) = RVa(x, z)(εy(x)−εy(z)) dz =−a(x, y), so we ge :
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 de ine he ke nel ε∈C(Fc×Fc,C) as ε(x, y) = εy(x) o e e y x, y ∈Fc. The
exp ession o ∂K
∂nx ollows om he ac ha , o e e y x∈δ(F):
∂ε
∂nx
(x, y) = ∂εy
∂nF
(x) = ZF
a(x, z) (ε(x, y)−ε(x, z)) dz =εy(x)κF(x).
Clea ly, ∂ε
∂nx∈C(δ(F)×δ(F),C). Mo eo e , ∂J
∂ny∈C(F1×δ(F),C), so also ∂2J
∂nx∂ny∈
C(δ(F)×δ(F),C); and hus ∂K
∂nx∈C(δ(F)×δ(F),C). The symme y o his ke nel ollows
om Lemma 1.3.7.
Rema k 1.4.9. In he pa icula case o (1.4) in which Γ is a DC elec ical ne wo k, h∈
C(F) and g∈C(Fc), we can es ic he p oblem o seek only o eal solu ions, i.e., o seek
o u∈C(V)such ha
L(u) = hon F, u =gon Fc.(1.8)
Then, es ic ing o eal unc ion spaces, we can ob ain o (1.8) esul s ha a e analogous
o all he esul s in he sec ion. As a consequence, in ha case, he solu ion in P oposi ion
1.4.2 and he solu ion ugin Co olla y 1.4.3 a e eal. Because o ha , we can conside he eal
es ic ions o he G een and Poisson ope a o s, ha we also deno e as J:C(F1)−→ C(F1)
and K:C(Fc)−→ C(V F0), espec i ely. I s associa ed G een and Poisson ke nels a e
eal and also sa is y Lemma 1.4.7 and P oposi ion 1.4.8, plus he ac ha , in addi ion,
∂K
∂nx∈C(δ(F)×δ(F)).
30 Disc e e ec o calculus on ne wo ks
1.5 The Di ichle - o-Neumann map
Conside an elec ical ne wo k Γ = (V, a) and F⊂V. Recall ha o any unc ion g∈
C(Fc,C), he Poisson ope a o gi es a solu ion K(g) = ug∈C(V, C) o (1.7), ha is, an
ex ension o g o all V ha is ha monic on F. This sec ion is de o ed o he s udy o he
ela ionship be ween gand L(ug), which is gi en by he ollowing linea ope a o .
De ini ion 1.5.1. Gi en an AC ( espec i ely DC) elec ical ne wo k and F⊂V, he
Di ichle - o-Neumann map is he ollowing endomo phism Λ: C(Fc,C)−→ C(Fc,C) ( e-
spec i ely Λ: C(Fc)−→ C(Fc)) de ined o any g∈C(Fc,C) ( espec i ely g∈C(Fc))
as:
Λ(g) = ∂ug
∂nF
+LFc(g) = L(ug) = (L◦K)(g).
No e ha , because o Rema k 1.4.4, he de ini ion o he Di ichle - o-Neumann map is
independen o he chosen solu ion o (1.7).
In he li e a u e, he Di ichle - o-Neumann map is only de ined o ne wo ks wi h bound-
a y. Fo AC ne wo ks, i is de ined as he unc ion Υ: C(δ(F),C)−→ C(δ(F),C) such ha ,
o any g∈C(δ(F),C), Υ(g) = ∂ug
∂nF
.Simila ly, o DC ne wo ks, i is de ined as he unc-
ion Υ: C(δ(F)) −→ C(δ(F)) such ha , o any g∈C(δ(F)), Υ(g) = ∂ug
∂nF
.No e ha , o
ne wo ks wi h bounda y, ou de ini ion ag ees wi h his one, i.e. Λ = Υ. This is because he
subne wo k o Γ co esponding o Fcis ΓFc= (Fc,0), so E(ΓFc) = ∅and hus i s Laplacian
LFcis ze o.
Fo DC ne wo ks, he Di ichle - o-Neumann map was conside ed in [52]. La e , in [10],
i is p o ed ha he Di ichle - o-Robin map, which is a gene aliza ion o he Di ichle - o-
Neumann map o he case o a Sch ¨odinge po en ial, is sel -adjoin and posi i e semide i-
ni e. The cha ac e iza ion o possible Di ichle - o-Neumann maps o ne wo ks wi h complex
weigh s a he edges whose imagina y pa s a e no necessa ily nonposi i e was i s de i ed
in [78]. I was la e edisco e ed independen ly in [87]. A gene aliza ion o he Di ichle - o-
Robin map o hese ne wo ks wi h complex weigh s o ce ain complex Sch ¨odinge po en-
ials was de ined in [30].
The ex ension o he map o gene al elec ical ne wo ks will allow us o in oduce in
Sec ion 1.7 he e ec i e admi ance om his map. This will allow us in Sec ion 3.3 o gi e
a no el physical in e p e a ion o he p oduc o he conduc ance o an edge by i s e ec i e
esis ance and, as a consequence, o he Algo i hm 1 o spec al spa si ica ion o ne wo ks.
We can also gi e he ollowing physical in e p e a ion o he Di ichle - o-Neumann map.
Unde he condi ion ha he e is ze o injec ed cu en a he e ices o F o any po en ial,
he alues o a po en ial a Fcuniquely de e mine he alues o ha po en ial a he in e io
bounda y o F, and hus, hey also uniquely de e mine he alues o injec ed cu en a Fc.
Mo eo e , he ela ionship be ween po en ial a Fcand injec ed cu en a Fcis linea .
In he elec ical ne wo ks o he eal wo ld usually he e is a subse o e ices F ha
The Di ichle - o-Neumann map 31
a e no associa ed o any gene a o o consume in which he e is ne e injec ed cu en ,
and hus he Di ichle - o-Neumann map allows us o s udy he ela ionship be ween cu en
and ol age in he es o he e ices wi hou ha ing o calcula e he ol age a F. Ano he
p ac ical applica ion o his disc e e ope a o is ha , o ne wo ks wi h bounda y, i is
a mime ic disc e iza ion o he con inuous Di ichle - o-Neumann map, ha is de ined as
ollows in [6].
Le Ω ⊆Rnbe a bounded connec ed open se wi h n≥2 and a bounded measu able
conduc i i y σwhich sa is ies λ≥σ≥λ−1almos e e ywhe e in Ω o some λ > 0. Gi en
a po en ial g∈H1/2(∂Ω) in he ace space on he bounda y ∂Ω, he induced po en ial ug
on Ω sol es he Di ichle p oblem o inding u∈H1(Ω) such ha
∇·(σ∇u) = 0 in Ω, u|∂Ω=g.
The Di ichle - o-Neumann map, (see [6]), is de ined as he ope a o
Λ: H1/2(∂Ω) −→ H1/2(∂Ω) such ha
Λσ(g) = σ∂ug
∂n∂Ω
,
o e e y g∈H1/2(∂Ω), whe e ndeno es he ou e uni no mal ec o o ∂Ω.
Roughly speaking, H1(Ω) is he subse o he Hilbe space o squa e-in eg able unc ions
L2(Ω) whose weak de i a i es belong o L2(Ω), and he e o e wi h weak g adien in L2(Ω).
These unc ions can be ex ended o unc ions on ∂Ω. The se o hese ex ensions is H1/2(∂Ω),
which is a subspace o unc ions o L2(∂Ω) which ha e ce ain egula i y. The conside a ion
o hese spaces allows he a ia ional ea men o he p oblem and he p oo ha he e is a
solu ion (in H1(Ω)). The de ailed de ini ion and p ope ies o hese spaces can be ound in
[3, 31].
The knowledge o he p ope ies o he disc e e Di ichle - o-Neumann ope a o will allow
us o s udy he disc e e p oblem analogous o Calde ´on’s in e se conduc i i y p oblem, which
will be he objec i e o Chap e 2.
The bilinea o m on C(Fc,C) associa ed o he Di ichle - o-Neumann ope a o is gi en,
o e e y g, h ∈C(Fc,C), by:
⟨h, Λ(g)⟩=ZV
hΛ(g)dx =⟨uh,L(ug)⟩=E(uh, ug).
By he Fi s G een iden i y, and conside ing ha L(ug) = 0 on F, we ha e ha
⟨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.
P oposi ion 1.5.2. Le Γ = ΓV1⊔... ⊔ΓVsbe he decomposi ion in connec ed componen s
o Γ, and F⊂V. The Di ichle - o-Neumann map Λis symme ic, singula , i s eal pa is
32 Disc e e ec o calculus on ne wo ks
posi i e semide ini e and i s imagina y pa is nega i e semide ini e. Mo eo e , i s null space
is he se o unc ions ha a e cons an on each Vi∩Fc ha is no emp y. Fu he mo e, he
symme ic ke nel N∈C(Fc×Fc,C)o Λis:
N=L|Fc×Fc−∂2J
∂nx∂ny
.
P oo . Fo e e y g, h ∈C(Fc,C), we ha e ha
⟨Λ(g), h⟩−⟨g, Λ(h)⟩=ZV
Λ(g)h−gΛ(h)dx
=Zδ(F)∂ug
∂nF
uh−ug
∂uh
∂nFdx +ZFcLFc(g)h−gLFc(h)dx = 0,
whe e he in eg al in δ(F) is equal o ze o by he Second G een Iden i y on F, and he
in eg al in Fcis equal o ze o by he Second G een Iden i y on he whole subne wo k ΓFc.
As a consequence, Λ∗=C ◦Λ◦C, so Λ is symme ic.
On he o he hand, o any g∈C(Fc,C), i is sa is ied ha
⟨Λ(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.
Conside ing ha ⟨Λ∗(g), g⟩=⟨g, Λ∗(g)⟩=⟨Λ(g), g⟩; i is clea ha
⟨ℜ(Λ)(g), g⟩ ≥ 0 and ⟨ℑ(Λ)(g), g⟩ ≤ 0.
Now, as in he p e ious sec ion, i we deno e by F0 he union o he Visuch ha Vi⊆F,
hen F1=F F0is he union o he Visuch ha Vi∩Fc=∅. Fo any g∈C(Fc,C), Λ(g) = 0
i L(ug) = 0 i ugis cons an a each Vi. I he las condi ion holds, i is clea ha gis
cons an on each Vi∩Fcsuch ha Vi⊆F1. Suppose now ha g=Pi:Vi⊆F1kiχVi∩Fcwi h
each ki∈C. Nex , we will p o e ha o his g,ugis piecewise cons an on each Vi, which
is enough o demons a e he claim in he p oposi ion abou he null space o Λ.
By de ini ion, ugis he unique solu ion o he bounda y p oblem o inding u∈C(V
F0,C) such ha L(u) = 0 on Fand u=gon Fc. We conside he equi alen p oblem o
seeking o ∈C(F1,C) such ha L( ) = −L(g) on F1.
The unique solu ion o his las p oblem is =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 cons an on each Vi.
Mono onici y on DC ne wo ks 33
On he o he hand, deno ing as LFc he ke nel o LFc, by he de ini ion o Λ, we ha e ha
N=LFc+∂K
∂nx. As a consequence, om P oposi ion 1.4.8, we ge ha o e e y 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).
Fo e e y x, y ∈Fc, we ha e ha
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) excep when x=y∈δ(F), o which L(x, x) = LFc(x, x) + κF(x).
The e o e, we ob ain he desi ed exp ession o he ke nel N.
Co olla y 1.5.3. I Γis a DC ne wo k, hen he Di ichle - o-Neumann map Λis sel -adjoin
and posi i e semide ini e. Mo eo e , N∈C(Fc×Fc).
Rema k 1.5.4. A e ixing a labeling {x1, ..., xn}on he e ex se Vo a ne wo k Γ =
(V, a), we deno e by N∈M|Fc|×|Fc|(C) he ma ix co esponding o he Di ichle - o-Neumann
map, Λ, which is named he esponse ma ix o Γ. I is a singula complex symme ic ma ix.
We can w i e a esponse ma ix as N=ℜ(N) + iℑ(N), he sum o i s eal and imagina y
pa s, wi h he p ope y ha ℜ(N) is posi i e semide ini e and ℑ(N) is nega i e semide ini e.
As a consequence, o e e y x∈Fc,N(x, x) = −Py=xN(x, y) has a nonnega i e eal
pa and a nonposi i e imagina y pa .
Fo DC ne wo ks, he esponse ma ix Nis eal, posi i e semide ini e and i s diagonal
en ies a e nonnega i e.
Mo eo e , applying Lemma 1.3.7 o he ke nel Jassocia ed o he G een ope a o (whose
ma ix is L(F1;F1)−1), we ge ha he ma ix o ∂2J
∂nx∂nyis L(Fc;F1)L(F1;F1)−1L(Fc;F1)T,
because Jis a ke nel on F1, and hus he i s h ee e ms in he igh side o he equa ion
o ha lemma a e equal o ze o.
The e o e,
N=L(Fc;Fc)−L(Fc;F1)L(F1;F1)−1L(Fc;F1)T.
Thus Nis equal o he Schu complemen o L(F1;F1) o L(V F0); (V F0), which is
deno ed as L(V F0); (V F0)L(F1;F1), (see [51]).
1.6 Mono onici y on DC ne wo ks
In his sec ion we will e iew some esul s o mono onici y o eal unc ions on DC ne wo ks
(P oposi ions 1.6.1, 1.6.2, 1.6.3 and 1.6.4), ha can be ound in [9] and [35]. This will allow
34 Disc e e ec o calculus on ne wo ks
us o p o e addi ional p ope ies (see P oposi ion 1.6.5, Lemma 1.6.7 and P oposi ion 1.6.8)
o he Di ichle - o-Neumann map o a DC ne wo k.
The esul s in his sec ion ely on he o de o Rand on he ac ha he es ic ion o
he Laplacian o a DC ne wo k o he space o eal unc ions C(V) is an endomo phism o
C(V), so hey can no be gene alized o AC ne wo ks. In ac , we show a coun e example
o P oposi ion 1.6.5 in he AC case.
Le Γ = (V, c) be a DC ne wo k and F⊆V. We say ha a unc ion u∈C(V) is
supe ha monic ( espec i ely subha monic) on Fwhen L(u)≥0 ( espec i ely L(u)≤0) on
F. Also, we say ha a unc ion u∈C(V) is s ic ly supe ha monic ( espec i ely s ic ly
subha monic) on Fwhen L(u)>0 ( espec i ely L(u)<0) on F.
P oposi ion 1.6.1 (Hop ’s minimum p inciple).Le Γ=(V, c)be a DC ne wo k, F⊆V
a connec ed subse , and u∈C(V)supe ha monic on F. I he e is x∗∈Fsuch ha
u(x∗) = min
y∈¯
Fu(y), hen uis cons an on ¯
Fand i is ha monic on F.
P oo . As cis nonnega i e,
0≤ L(u)(x∗) = Z¯
F
c(x∗, y)(u(x∗)−u(y))dy ≤0.
So u(y) = u(x∗) whene e c(x, y)>0, ha is, o any y∼x. We can i e a e his a gumen
e alua ing he Laplacian a any e ex y∈F o which we know ha u(y) = u(x∗), un il we
ge ha u=u(x∗) on ¯
F. As a consequence, L(u) = 0 on F.
The wo ollowing esul s a e consequences o Hop ’s minimum p inciple.
P oposi ion 1.6.2 (Mono onici y P inciple).Le Γ=(V, c)be a DC ne wo k, F⊆Va
connec ed subse , and u∈C(V)supe ha monic on F. I δ(F) = ∅, hen uis cons an on ¯
F
and i is ha monic on F. Mo eo e , i δ(F)=∅and u≥0on δ(F), hen ei he u > 0on F
o u= 0 on ¯
F.
P oo . The esul in he case ha δ(F) = ∅is a s aigh o wa d consequence o Gauss’
Theo em.
Now, in he case ha δ(F)=∅and u≥0 on δ(F), i he e exis s a e ex x∗∈Fsuch
ha u(x∗) = 0, hen u(x∗) = min
y∈¯
Fu(y), so by Hop ’s minimum p inciple, u= 0 in ¯
F.
P oposi ion 1.6.3 (Minimum P inciple).Le Γ=(V, c)be a DC ne wo k, F⊂Va
connec ed subse such ha δ(F)=∅, and u∈C(V)supe ha monic on F. Then:
min
y∈¯
Fu(y)= min
y∈δ(F)u(y),
and he equali y holds i and only i uis cons an on ¯
F.
Mono onici y on DC ne wo ks 35
P oo . We de ine he unc ion =u−min
y∈δ(F)u(y)χ¯
F∈C(V). As L(χ¯
F) = 0 on F, is
supe ha monic on F. The unc ion is also nonnega i e on δ(F), so we ob ain he esul
applying P oposi ion 1.6.2 o .
In he nex esul we p o e ha a s ic ly supe ha monic unc ion on Fcan no ha e a
local minimum in F, as in he con inuous ec o calculus.
P oposi ion 1.6.4. Le Γ=(V, c)be a DC ne wo k, F⊂Vand u∈C(V)s ic ly supe -
ha monic on F. Then, o any x∈F, he e exis s y∈¯
Fsuch ha y∼xand u(y)< u(x).
P oo . Le x∈Fand suppose ha o e e y e ex y∈¯
Fadjacen o x, we ha e u(x)≤u(y).
Then we a i e o he ollowing con adic ion:
0<L(u)(x) = Z¯
F
c(x, y)(u(x)−u(y))dy ≤0.
As a consequence o he Minimum P inciple, we ob ain he ollowing p ope y o he
Di ichle - o-Neumann map o any DC ne wo k.
P oposi ion 1.6.5. Le Γ=(V, c)be a DC ne wo k, F⊂V, and le Λ: C(Fc)−→ C(Fc)
be he Di ichle - o-Neumann map o Γand F, whose ke nel is N∈C(Fc×Fc). Then, o
any x, y ∈Fcsuch ha x=y, we ha e ha N(x, y)≤0. Mo eo e , N(x, y)<0i and only
i x∼yo xand ya e connec ed h ough F.
P oo . Gi en x, y ∈Fcsuch ha x=y, we ha e ha
N(x, y) = Λ(εy)(x) = ∂uεy
∂nF
(x) + LFc(εy)(x).
On one hand, LFc(εy)(x)≤0 and LFc(εy)(x)<0 i x∼y. On he o he hand, as
K(x, y) = εy(x) = 0, we ge :
∂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 P oposi ion 1.4.8, i x /∈δ(F) o y /∈δ(F), ∂uεy
∂nF(x) = 0. Now, o e e y z∈Fsuch
ha z∼x, we deno e by Hz⊆F he connec ed componen o F ha con ains he e ex
z. Fo any z∈Fsuch ha z∼x,x∈δ(Hz)=∅and uεy≥0 on δ(Hz), so we ge ha
K(z, y) = uεy(z)≥0 applying he Mono onici y P inciple o uεy, which is ha monic on F.
As a consequence, N(x, y)≤0.
Mo eo e , o any z∈Fsuch ha z∼x, by he Minimum P inciple, K(z, y)>0 i
y∈δ(Hz). Gi en ha xand ya e connec ed h ough Fi he e exis s z∈Fwi h z∼x
such ha y∈δ(Hz), we inish he p oo .
42 The in e se conduc ance p oblem
The disc e e e sion o Calde ´on’s p oblem, called he In e se conduc ance p oblem is
conce ned wi h he eco e y o he conduc ance o a gi en ne wo k om he esponse ma-
ix. O cou se, his (disc e e) in e se p oblem is no limi ed o he ealm o nume ical
econs uc ion o conduc i i ies, bu makes sense in i s own igh and can be posed on a bi-
a y g aphs and ne wo ks. I was p oposed in he las decade o he pas cen u y mainly by
he Sea le school, led by E.B. Cu is and J. Mo ow. The explana ion in e ms o disc e e
ec o calculus, mimicking he con inuous o mula ion, is mo e ecen , da ing back o he
las en yea s and is based on he wo k o he MAPTHE g oup in Ba celona. In ac , i Γ
is a ne wo k wi h bounda y, i.e., Γ = ( ¯
F, c), he Di ichle - o-Neumann map is a mime ic
disc e iza ion o he con inuous Di ichle - o-Neumann map, (as s a ed in Sec ion 1.5) and
hence he esolu ion o he disc e e p oblem can be in e p e ed as he econs uc ion s ep o
he con inuous one. The e o e, wi h he no a ions in oduced in Sec ion 1.5, in his chap e ,
we s udy he ollowing p oblem, (see [7, 8, 10, 54]).
P oblem 2.0.2 (In e se conduc ance p oblem).Le Γ = (V, c)be a DC elec ical ne wo k
wi h unknown conduc ance c, bu wi h a known opology, G(Γ) = (V, E(Γ)). Le F⊂Vand
le Λbe he Di ichle - o-Neumann map o Γand F. The p oblem consis s in de e mining c
om Λ.
2.1 Backg ound o he p oblem
The (con inuous) in e se conduc i i y p oblem has ecei ed a lo o a en ion since i s in-
oduc ion in 1980. The e a e abundan pape s dedica ed o i , such as [5, 6, 23, 24, 26, 32,
34, 86, 97].
Two o he mos s udied aspec s a e he uniqueness o i s solu ion, and in he cases
whe e he e is a unique solu ion, he cons uc ion o an algo i hm o ob ain i . In he case
o dimension n= 2, he solu ion was p o ed o be unique in [13]. Mo eo e , an algo i hm o
eco e he conduc i i y in his case was ob ained in [12]. In he case o dimension n≥3,
he ques ion o uniqueness in gene al emains open o his da e, al hough some au ho s ha e
p o ed ha he solu ion is unique i u he egula i y assump ions a e added o he p oblem.
Fo ins ance, in [40] he uniqueness o he p oblem was p o ed i he conduc i i y and he
su ace a e Lipschi z con inuous. Fu he mo e, an algo i hm o eco e he solu ion unde
his hypo hesis was ob ained in [39].
E en when he conduc i i y σcan be uniquely ob ained om he Di ichle - o-Neumann
map Λσ, he solu ion σdoes no depend con inuously on Λσin gene al, so he p oblem is
ill-posed, (see [6, 15]). Because o ha , se e al au ho s ha e in es iga ed i knowing some a
p io i in o ma ion abou σmakes he p oblem s able. Fo example, in [14, 75] o he case
o dimension n= 2 and in [5] o he case n≥3, he au ho s p o ed ha i i is a p io i
known ha σis bounded o a ce ain sui able no m, hen σdepends con inuously on Λσ,
bu wi h his a p io i hypo hesis we only ha e he so-called loga i hmic s abili y. The e o e,
he p oblem s ill exhibi s a bad nume ical beha io , which ep esen s a se e e obs uc ion
o he econs uc ion s ep.
In ha line o esea ch, we highligh he pape [6] by Alessand ini and Vessella, whe e hey
p o ed ha i i is a p io i known ha he e is a known pa i ion o he se Ω wi h a bounded
Backg ound o he p oblem 43
numbe o connec ed subse s sa is ying some addi ional hypo hesis such ha he conduc i i y
is piecewise cons an on ha pa i ion, ( ha is, σis equal o an unknown cons an alue a
each subse ), hen Calde ´on’s p oblem becomes Lipschi z s able. Fu he mo e, he Lipschi z
cons an g ows exponen ially wi h he numbe o subse s in he pa i ion, as demons a ed
in [77, 85]. In o de o imp o e he s abili y o he eco e y p ocess, he e a e au ho s ha
ha e used egula iza ion me hods, mainly o Tikhono ype, (see [61, 76, 86]). O he au ho s
ha e used machine lea ning echniques, (see [41]).
The (disc e e) in e se conduc ance p oblem has ga he ed ela i ely less a en ion han
i s con inuous coun e pa , wi h pape s such as [8, 10, 30, 45, 51, 65, 66]. Addi ionally,
se e al au ho s ha e s udied he p oblem wi h he goal o ob aining an app oxima e solu ion
o Calde ´on’s p oblem, (see [23, 24, 26, 27, 28, 62]).
The si ua ion in he esea ch abou his p oblem is analogous o he one in he con inuous
p oblem. On one hand, he e a e wo ks ha s udy he uniqueness o he p oblem, also
known as he iden i ica ion p oblem, which depends on he g aph associa ed o he elec ical
ne wo k G(Γ). To he bes o ou knowledge, he s a emen o his p oblem o gene al
ne wo ks appea ed in [47], and was sol ed unde some mono onici y hypo hesis, see also
[22]. In hese wo ks, he au ho s emphasize he need o o mula e ne wo k p oblems using
an ope a ional calculus ha allows ollowing he de elopmen s o he con inuum. In ac ,
he backg ound o mos o he au ho s comes om he ield o PDEs. The used ope a o s a e
he g adien , he no mal de i a i e and he Laplacian, which a e su icien o desc ibe he
analogue o he Di ichle - o-Neumann map and o use he a ia ional app oach. The mos
gene al amewo k including he conside a ion o gene al (disc e e) ellip ic ope a o s and a
comple e ec o calculus was p esen ed in [20], whe e again unde mono onici y hypo hesis,
simila esul s o he men ioned pape s we e ob ained.
The ex ension o P oblem 2.0.2 o he case o eco e ing he admi ance ain an AC
ne wo k was aised in [30]. In his pape , he au ho s also conside cases in which he
imagina y pa o ais no nonposi i e (which we do no conside in De ini ion 1.3.1), i.e.
he au ho s ex end he p oblem o he case in which each edge has a complex weigh wi h
posi i e eal pa . Fo his ex ension, hey gi e a c i e ion o iden i y he g aphs o which
he p oblem has a unique solu ion o almos all ne wo ks wi h ha opology.
In p e ious wo ks (see [52, 53, 54, 55]), Cu is and Mo ow p o ed ha he in e se
conduc ance p oblem has a unique solu ion when he ne wo k opology is a c i ical plana
g aph, and hus, in pa icula , when i is a well-connec ed spide g aph. They also in oduced
an explici me hod o eco e he conduc ance o a well-connec ed spide ne wo k om a
ini e numbe o elemen a y algeb aic ope a ions, which is called he laye peeling me hod.
This me hod was gene alized in [10] o include he case in which he e is a Sch ¨odinge
po en ial a he e ices.
The e a e o he ne wo k opologies o which he he solu ion o he in e se conduc ance
p oblem is also known o be unique and he e is an explici me hod simila o laye peeling
o ob ain he conduc ance, including he n×ng ids (see [11]), and any ee wi hou e ices
o combina o ial deg ee wo, (see [66]). The me hod in oduced in he las e e ence also
allows o iden i y which ee is he ne wo k opology up o e ices o combina o ial deg ee
wo, al hough he me hod is only alid o ees, because i exploi s he ac ha he e ec i e
esis ance be ween any wo nodes coincides wi h he esis ance dis ance be ween hem.
44 The in e se conduc ance p oblem
An al e na i e line o esea ch in he cons uc ion o explici algo i hms o sol ing he
in e se conduc ance p oblem o some opologies is ela ed o he s udy o ce ain G ass-
mannians. In ha line, in [71], an algo i hm is p oposed o sol e he p oblem o a ce ain
amily o ne wo ks called s anda d ne wo ks. The alues o he solu ion a e ob ained as a
bi a io o P a ians cons uc ed om he esponse ma ix. A ela ed algo i hm, which wo ks
o any well-connec ed elec ical ne wo k can be ound in [65], al hough he only example
o ne wo k in which he conduc ances a e compu ed is a well-connec ed spide ne wo k wi h
m= 3 bounda y nodes.
Despi e being ini e-dimensional, he in e se conduc ance p oblem is also se e ely ill-
posed in gene al, (see [54]). Among he explici me hods o eco e he conduc ance men-
ioned so a , he ones in well-connec ed spide ne wo ks and in g ids (in [10, 11, 52, 53,
54, 55]) a e known o be ill-posed o ne wo ks o medium o la ge size; and o he es o
he me hods (in [65, 66, 71]) he s abili y is no s udied and he compu a ional examples o
eco e y p esen ed a e only in ne wo ks wi h small size.
Se e al au ho s, (see [45]), ha e de eloped nume ical me hods wi h egula iza ion o
eco e an app oxima e solu ion o he in e se conduc ance p oblem wi h mo e s abili y
han he men ioned explici me hods. In [45], he in e se p oblem is e o mula ed o ob ain
an equi alen p oblem in which he goal is o es ima e a po en ial a he e ex se . Then, he
p oblem is sol ed u ilizing a disc e e e sion o he in e se Bo n se ies wi h egula iza ion.
The me hod is es ed in 12 ×12 g ids. In he expe imen s, he me hod con e ges when he
de ia ion om a cons an po en ial is small; and he me hod di e ges o he wise.
Some o he wo ks ha sol e he disc e e in e se p oblem o app oxima e he con inuous
one ha e also con ibu ed o he s udy o he s abili y o he disc e e p oblem and he
de elopmen o nume ical me hods o sol e i . L. Bo cea alongside se e al collabo a o s
ha e w i en se e al pape s in which hey app oxima e he con inuous p oblem using well-
connec ed spide ne wo ks, including [23, 24, 26, 27, 28]. In [27], he au ho s p opose o
o mula e he disc e e p oblem as an op imiza ion p oblem which includes a Tikhono - ype
egula iza ion and o sol e i wi h an op imiza ion me hod. The egula iza ion e m penalizes
he de ia ion om a e e ence conduc ance whose alue has o be known and ixed a p io i.
The expe imen al esul s o he me hod a e ca ied ou in ne wo ks wi h mode a e size
(wi h 29 o less e ices in he bounda y). In he es o hose wo ks ([23, 24, 26, 28]), he
conduc ance is eco e ed using he laye peeling algo i hm ([55]). In o de o ha e s abili y,
he au ho s limi he size o he ne wo ks, choosing he opology wi h g ea es numbe o
bounda y nodes such ha he algo i hm does no yield nega i e alues o he conduc ance;
which gene ally has ewe han 11 bounda y nodes.
In o he wo ks, he con inuous p oblem is app oxima ed sol ing he disc e e one in g ids.
Fo example, in [24, 25], he disc e e p oblem is sol ed using an algo i hm ha con e ges
o he eal ne wo k i and only i i is asymp o ically close o a e e ence ne wo k ha has
o be known and ixed a p io i. In [62], he au ho s sol e he disc e e p oblem using a
disc e e analogous o he complex geome ic op ics app oach. They also use hese solu ions
o ob ain a s abili y es ima e o he disc e e p oblem, which is in |log(e o )|α, o some
α < 0, whe e e o s ands o he e o in he Di ichle - o-Neumann map, i.e., he p oblem
is exponen ially uns able.
In he ecen wo k [38], he au ho s explo e whe he knowing a p io i he hypo hesis
Ill-posedness o he in e se conduc ance p oblem 45
ha he conduc ance is piecewise cons an on a pa i ion wi h ew subse s makes he dis-
c e e in e se conduc ance p oblem s able. This hypo hesis, called he “piecewise cons an
conduc ance hypo hesis”, mimics he hypo hesis o piecewise cons an conduc i i y consid-
e ed in [6]. They p opose o o mula e he p oblem as a polynomial op imiza ion p oblem,
wi h a egula iza ion e m `a la Tikhono ha penalizes he de ia ion wi h espec o ha
hypo hesis. The au ho s p esen nume ous expe imen al examples in which i is possible
o sol e he in e se conduc ance p oblem wi h s abili y in well-connec ed spide ne wo ks
sa is ying ha hypo hesis wi h up o m= 47 bounda y e ices, which a e la ge han he
ne wo ks conside ed in he p e ious li e a u e.
Mo eo e , his wo k is ex ended by he same au ho s in he pape [37]. In ha wo k,
hey show ha he app oach in [38] can be used o sol e he in e se conduc ance p oblem
wi h s abili y e en in some cases in which he piecewise cons an conduc ance hypo hesis is
no exac ly sa is ied by he eal ne wo k. Mo eo e , hey s udy he a ia ion o he e o in
he eco e ed conduc ance wi h espec o he penal y pa ame e , and hey use echniques o
sum o squa es o polynomials o seek o a gua an ee ha he ob ained nume ical solu ion
o he polynomial op imiza ion p oblem is a global minimum.
The es o he chap e is dedica ed o e iew and ex end he esul s o [37, 38] abou
he in e se conduc ance p oblem in well-connec ed spide ne wo ks.
2.2 Ill-posedness o he in e se conduc ance p oblem
The aim o his sec ion is o p o e ha he in e se conduc ance eco e y p oblem is in insi-
cally se e ely ill-posed, in o de o emphasize he impo ance o e o mula ing he p oblem
and seeking o me hods ha allow us o eco e he conduc ance wi h s abili y. This sec ion
is a e iew o [38, Sec ion 2].
We conduc se e al es s in which we compu e he Di ichle - o-Neumann map o a well-
connec ed spide ne wo k, and hen we apply he algo i hm in [10] o sol e he in e se
conduc ance p oblem. We eco e a conduc ance ha , when he numbe o bounda y e ices
is high, widely di e s om he one o he o iginal ne wo k. This is due o he ill-posedness o
he p oblem: despi e he ac ha he algo i hm is based on explici o mulas, any e o in
he en ies o he esponse ma ix (which a e s o ed wi h ini e p ecision) could be ampli ied
se e al o de s o magni ude in he algo i hm.
Fo he sake o comple eness we gi e he e he highligh s o he algo i hm o [10] ha a e
mainly based on inding solu ions o a ba e y o o e de e mined bounda y alue p oblems.
Each s ep equi es he in o ma ion ob ained in he las one.
Le Γ = ( ¯
F, c) be a DC well-connec ed spide ne wo k and le A, B ⊂δ(F) nonemp y
subse s such ha A∩B=∅. Mo eo e we deno e by R he se R=δ(F) (A⊔B), so
δ(F) = A⊔B⊔Ris a pa i ion o δ(F). We ema k ha Rcan be an emp y se . Fo any
∈C(F), g∈C(A⊔R) and h∈C(A), he o e de e mined pa ial Di ichle –Neumann
bounda y alue p oblem on Fwi h da a , g, h consis s in inding a unc ion u∈C(¯
F) such
46 The in e se conduc ance p oblem
ha
Lq(u) = on F, ∂u
∂nF
=hon Aand u=gon A⊔R. (2.1)
In Figu e 2.1 we show he ep esen a ion o a gene al o e de e mined bounda y p oblem.
We ix a labeling in he e ex se o Γ, and we deno e by Li s Laplacian ma ix, by Ni s
F
B
A
R
Figu e 2.1: Bounda y pa i ion in an o e de e mined bounda y alue p oblem.
esponse ma ix, and by ,gand h he ec o s associa ed wi h ,gand h, espec i ely. In
[10] he au ho s p o ed he exis ence and uniqueness o a solu ion o his p oblem o any
da a ∈C(F), g∈C(A⊔R), h∈C(A) i |A|=|B|and N(A;B) is in e ible. Mo eo e ,
i u∈C(¯
F) is he unique solu ion o he o e de e mined pa ial bounda y alue p oblem
(2.1), hen i s associa ed ec o usa is ies
u(B) = −N(A;B)−1·L(A;F)·L(F;F)−1· +N(A;A⊔R)·g−h,
u(F) = L(F;F)−1· −L(F;B)·u(B)−L(F;A⊔R)·g
and, clea ly, u(A⊔R) = g.
We conside also he wha we called bounda y spike o mula. I x∈Rhas a unique
neighbou y∈F, hen
c(x, y) = N(x;x)−N(x;B)·N(A;B)−1·N(A;x).
Once we ge he alue o he conduc ances on he bounda y edges, and aking ad an age
o he null zone o he solu ion o P oblem (2.1) when = 0, h= 0 and g=εz, o each
z∈A⊔R, we can eco e he alue o he solu ion on he se o e ices ha a e a dis ance 1
om he bounda y. Then, he p ocess ollows al e na ing he knowledge o he conduc ance
and he unc ion alue om he bounda y o he in e io e ex.
The ollowing example e e s o he case o well-connec ed spide ne wo ks, as ep esen ed
in Figu e 2.2.
Example 2.2.1 ([38]).Fo m= 7,11,15,19,23,27,31 and 35, we s a om he well-
connec ed spide ne wo k wi h m adii and cons an conduc ance c= 1. In all cases, we
compu e he esponse ma ix No he ne wo k, and om i we eco e he conduc ance c′
using he explici o mulas om [10]. The algo i hm has been implemen ed in Ma lab.
Ill-posedness o he in e se conduc ance p oblem 47
A
R
B
Figu e 2.2: The bounda y pa i ion in a well-connec ed spide ne wo k.
In Figu e 2.3 we show he loga i hm o he e o in he eco e ed conduc ance in he
Euclidean no m, log(||c′−c||), o all alues o m, whe e log s ands o he decimal loga i hm,
and he no m o c′−c∈C(Γ) = C(G(Γ)) is he one de ined in Rema k 1.2.3. Mo eo e ,
Table 2.1 displays he e o on he conduc ances. We see ha he e o is almos ze o o
m= 7 and inc eases app oxima ely exponen ially wi h m om m= 7 o m= 23. The e o
keeps inc easing wi h m o m≥23.
5 10 15 20 25 30 35
-15
-10
-5
0
5
Figu e 2.3: Loga i hm o he e o in he eco e ed conduc ance.
We show he eco e ed conduc ance o m= 19 and o m= 23 in Figu es 2.4 and 2.5,
espec i ely. In bo h igu es, he wid h o each edge is p opo ional o he absolu e alue o
he eco e ed conduc ance c′. Fo he sake o cla i y, he alues displayed on each edge ha e
been ounded o he nea es in ege wi hin he g aphical illus a ions.
48 The in e se conduc ance p oblem
Table 2.1: E o in he eco e ed conduc ance.
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
Figu e 2.4: Reco e ed ne wo k wi h m= 19 adii in Example 1.
Figu e 2.5: Reco e ed ne wo k wi h m= 23 adii in Example 1.
S able e o mula ion: he disc e e piecewise cons an conduc ance hypo hesis 49
The e o o m= 19 is app oxima ely 3.5·10−3, and we see ha he nea es in ege
o he alue o he eco e ed conduc ance a e e y edge is equal o he ue alue c= 1.
Howe e , he e o o he nex bigge ne wo k, he one wi h m= 23, is app oxima ely
5.2·10. We can see ha he alue o he eco e ed conduc ance is e y a om 1 and in
some cases e en nega i e, especially in edges ha a e a om he bounda y. Fo example
he e is an edge wi h conduc ance close o −31.
As a conclusion o he pe o med es s, he eco e y o he conduc ance o a well-
connec ed spide ne wo k is uns able excep o small ne wo ks. Mo eo e , he big dis-
c epancies appea on edges ha a e a away om he bounda y. This si ua ion is analogous
o he one ha appea s in he con inuous Calde ´on in e se conduc i i y p oblem, which is
se e ely ill-posed, and he ins abili ies inc ease as we mo e a he away om he bounda y,
(see [26]).
2.3 S able e o mula ion: he disc e e piecewise con-
s an conduc ance hypo hesis
Calde ´on’s p oblem is ill-posed, bu in [6] i was shown ha i he hypo hesis ha he
conduc i i y is piecewise cons an on a pa i ion o he se Ω wi h a bounded numbe o
connec ed subse s is a p io i known, hen he p oblem becomes Lipschi z s able. As in
he p e ious sec ion we ha e seen ha i s disc e e coun e pa is analogously ill-posed, we
p opose o ansla e his hypo hesis o he disc e e se ing and o s udy he conduc ance
eco e y knowing a p io i his hypo hesis. This sec ion is a e iew and ex ension o [38,
Sec ion 3].
In he disc e e case, we say ha a conduc ance is piecewise cons an on a pa i ion
E=E1⊔···⊔Esi i is cons an on each Ei. O cou se, as he numbe o edges is ini e, any
conduc ance is inhe en ly piecewise cons an on some pa i ion. In his wo k, we unde s and
ha a piecewise cons an conduc ance hypo hesis holds i and only i s, he numbe o subse s
in he pa i ion, sa is ies s≪ |E|. No e ha we do no equi e o any j= 1, ..., s ha he
subne wo k wi h edge se Ejand whose e ex se is he se o e ices o he ne wo k which
a e joined by edges o Ejis connec ed. The e o e his disc e e hypo hesis can be seen as
a gene aliza ion o he s ic disc e e analogue o he hypo hesis in [6] o he con inuous
p oblem in which he subse s o he pa i ion mus be connec ed.
As demons a ed in he p eceding sec ion, e en when conside ing he ex eme scena io
whe e he eal conduc ance sa is ies he hypo hesis wi h s= 1, i has been obse ed ha
he explici eco e y me hods ha sol e he gene al in e se conduc ance p oblem lead o
ins abili ies. Tha is due o he ac ha he me hods do no use he in o ma ion o he
hypo hesis o being piecewise cons an on a pa icula pa i ion: hey do no en o ce ha
he solu ion mus sa is y he hypo hesis, no penalize he de ia ion wi h espec o he
hypo hesis in he eco e y p ocess.
Consequen ly, i becomes impe a i e o de elop al e na i e algo i hms ha ensu e s abil-
i y. Ou p oposal is o e o mula e he in e se p oblem as a polynomial op imiza ion p oblem
ha includes he de ia ion in he eco e ed conduc ance wi h espec o being piecewise con-
50 The in e se conduc ance p oblem
s an on a gi en pa i ion as a penal y. We o mula e he p oblem o any possible pa i ion
E=E1⊔···⊔Eso he se o edges o he eal ne wo k Γ = ( ¯
F, c), whe he i s conduc ance
cis piecewise cons an on his pa i ion o no . In he case in which s≪ |E|, he penal y
e m penalizes he de ia ion wi h espec o a piecewise cons an conduc ance hypo hesis.
2.3.1 Polynomial op imiza ion p oblem
The polynomial op imiza ion p oblem ha we p opose o sol e he disc e e in e se p oblem
can be s a ed as ollows.
P oblem 2.3.1. [[38]] Le Γ=(¯
F, c)be a well-connec ed spide DC ne wo k wi h known se
o edges E(Γ) bu unknown conduc ance c, le Nbe he ke nel o he Di ichle - o-Neumann
map o Γand F, le E(Γ) = E1⊔ ··· ⊔ Esbe a pa i ion and le µ≥0be a penal y
pa ame e . We deno e by Γ′= ( ¯
F, c′) he DC ne wo k ha we wan o eco e , which mus
sa is y E(Γ′)⊆E(Γ). We de ine ano he unknown DC ne wo k Γω= ( ¯
F, ω)such ha
E(Γω)⊆E(Γ) and ωis piecewise cons an on E1⊔···⊔Es. Fo each z∈δ(F), we de ine a
unc ion uz∈C(V)such ha uz=εzon δ(F). The p oblem consis s in de e mining alues
o he a iables
(i) c′(exy) (= c′(x, y) = c′(y, x)) o all exy ∈E(Γ);
(ii) ω(Ej) o all j= 1, . . . , s;
(iii) uz(x) o all x∈Fand z∈δ(F),
which minimize he objec i e unc ion
p=Zδ(F)×δ(F)N(x, z)−ZV
c′(x, y) (uz(x)−uz(y)) dy2
dxdz
+µ
s
X
j=1 X
exy∈Ej
(c′(x, y)−ω(Ej))2
(2.2)
subjec o he cons ain s
gz
x:= ZV
c′(x, y) (uz(x)−uz(y)) dy = 0 (2.3)
o all x∈Fand z∈δ(F); and c′(exy)≥0 o all exy ∈E.
Le c′be a ixed easible alue o he conduc ance in he p oblem, and we deno e by L′,
Λ′and N′ he Laplacian, he Di ichle - o-Neumann map and he ke nel o he Di ichle - o-
Neumann map o he eco e ed ne wo k Γ′= ( ¯
F, c′), espec i ely. Then, o any x∈Fand
z∈δ(F) we ha e ha gz
x=L′(uz)(x). Because o ha , he cons ain s (2.3) a e equi alen
o ha , o each z∈δ(F), uz∈C(V) is a solu ion o he bounda y alue p oblem (1.7) o
g=εz, ha is, he bounda y alue p oblem o inding u∈C(V) such ha
L′(u) = 0 on F, u =εzon δ(F),(2.4)
S able e o mula ion: he disc e e piecewise cons an conduc ance hypo hesis 51
Now, o each x, z ∈δ(F), he e alua ion a xo he no mal de i a i e o uzwi h espec
o Fin Γ′is equal o
∂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 o Rema k 1.4.4, we ha e ha
∂uz
∂nF
(x) = ∂uεz
∂nF
(x)=Λ′(εz)(x) = N′(x, z).
Then, he objec i e unc ion (2.2) can be ew i en as
p=||N′−N||2
F +µ||c′−ω||2,(2.5)
so a solu ion o P oblem 2.3.1 minimizes he squa ed F obenius no m o he di e ence be-
ween he esponse ma ix N′o he eco e ed ne wo k and Nplus a penal y e m which
is he squa ed no m (de ined in Rema k 1.2.3) o he di e ence be ween he eco e ed con-
duc ance and any piecewise cons an conduc ance on E=E1⊔···⊔Esmul iplied by he
penal y pa ame e µ. In he con ex o Tikhono -like egula iza ion me hods he pa ame e
µis o en called egula iza ion pa ame e (see [61, 76, 86]).
Rema k 2.3.2. In P oblem 2.3.1, we allow he possibili y ha c′(x, y) = 0 o some exy ∈
E(Γ), and hus E(Γ′)⊊E(Γ). As we ha e discussed, his is no a p oblem o he objec i e
unc ion p o sa is y (2.5), e en i some subse o e ices o Fis isola ed in Γ′. Ne e heless,
i we know a p io i a alue λ > 0 such ha c(exy)≥λ o all exy ∈E(Γ), we can sligh ly
modi y he o mula ion o he p oblem, adding he es ic ion c′(exy)≥λ o all exy ∈Ei we
wan o ensu e ha he opology o Γ′and Γ a e he same. In ha case, Γ′is a ne wo k wi h
bounda y, so uz=uεz o each z∈δ(F). No e ha his a p io i in o ma ion is analogous
o he known lowe bound o he conduc i i y in he o mula ion o Calde ´on’s p oblem.
We de ine he unc ion : [0,∞]−→ [0,∞] which assigns o each µ he alue o he
minimum o pin a solu ion o P oblem 2.3.1, i.e.,
(µ) = min
{c′,ω}||N′−N||2
F +µ||c′−ω||2.
We also de ine has he minimum alue o ||N′−N||2
F among he conduc ances c′ ha a e
piecewise cons an on he pa i ion E=E1⊔···⊔Es. No e ha , o e e y µ, we ha e ha
(µ)≤min
{c′,ω:c′=ω}||N′−N||2
F +µ||c′−ω||2=h.
By he las inequali y, o e e y µ, he e alua ion o he e m µ||c′−ω||2in a solu ion o
P oblem 2.3.1 mus be lowe han o equal o h. Then, o any µ > 0, we ha e ha
(µ) = min
c′,ω:||c′−ω||≤qh
µ||N′−N||2
F +µ||c′−ω||2.
F om ha exp ession, we see ha he limi case o µ→ ∞ co esponds wi h en o cing
he hypo hesis ha he eco e ed conduc ance is piecewise cons an on E=E1⊔ ···⊔ Es
58 The in e se conduc ance p oblem
0 10 20 30 40 50 60
0
1
2
3
4
5
6
7
8
9
N N
Figu e 2.7: Maximum log ||c′−c||
||N′−N||F in eco e ed conduc ance o 100 ne wo ks wi h m= 11
and s= 1,...,55. (Example 2.4.2).
be ween 1 and 13, he e o in he eco e ed conduc ances is e y low in all he ne wo ks.
Besides, o alues o sbe ween 14 and 22, he e o is g ea e in some cases, bu smalle
han he no m o he eal conduc ances. Finally, o s > 23, he e a e ne wo ks in which he
eco e ed conduc ances ha e a g ea e o .
We inish his wo k by conside ing again he es o Example 2.2.1 bu wi h ou app oach.
These esul s will show he obus ness o ou me hod, since as we will see all he cases a e
s able and e en i we pe u b he esponse ma ix we can eco e he conduc ance.
Example 2.4.3. Fo m= 7,11,15,19,23,27,31,35,39,43 and 47,we s a om he well-
connec ed spide ne wo k wi h m adii and cons an conduc ance c= 1. In all cases, we
compu e he esponse ma ix No he ne wo k, and om i we eco e he conduc ance c′
ob aining an app oxima ion o P oblem 2.3.1 wi h s= 1. Addi ionally, o each mwe epea
10 imes he p ocess o adding andom pe u ba ions o each en y o Nsampled om a
uni o m dis ibu ion in each o he in e als [−10−8,10−8],[−10−7,10−7]and [−10−1,10−1],
and hen eco e ing he conduc ance wi h he pe u bed ma ix.
As in Example 2.4.1, we se µ= 1, we eco e he conduc ance c′, we compu e he e o
||c′−c||, and we compu e he quo ien ||c′−c||
||N′−N||F
. In he i s ow o Table 2.4 we show
he e o in he eco e ed conduc ance in he unpe u bed case. As we see he e o is e y
small, especially in compa ison wi h he esul s displayed in Table 2.1. We can ini ially
see ha o m= 7,11 he e o is smalle in he explici case, howe e o mbigge o
equal han 15, when he explici case becomes uns able, no only he e o is smalle wi h
ou algo i hm bu also he eco e ed alue accu a ely app oxima es he spide ne wo k wi h
cons an conduc ance 1, see Figu e 2.8 o he case m= 23. In his las case, obse e ha
he maximum e o in he conduc ance alues is 1.4·10−8.
In he es o he en ies o Table 2.4 we show, o each ne wo k and each in e al o
S able eco e y o piecewise cons an conduc ances 59
pe u ba ion, he maximum e o in he 10 eco e ed ne wo ks. Mo eo e , in Table 2.5, we
display he maximum o he alues o ||c′−c||
||N′−N||F
. As we can see he esul s a e simila o he
ones ob ained by conside ing he unpe u bed N,excep o he case whe e he magni ude
o he pe u ba ion is 10−1. In his case, he e o is much bigge bu s ill compa able wi h
he magni ude o he pe u ba ion pe o med. Besides, he alue o he conduc ance is
close enough o 1, see Figu e 2.9. This also shows he obus ness o ou algo i hm. We can
compa e hese esul s in Table 2.4 wi h he ones ob ained in [55, Sec ion 13], whe e a simila
expe imen was conduc ed only o m= 15. The e, he au ho s pe u bed he en ies o
N andomly by e ms o magni ude 10−8ob aining he conduc ance alues wi h an e o o
up o 0.5. Also, he au ho s pe u bed he en ies o N andomly by e ms o magni ude
10−7ob aining se e al nega i e alues in he conduc ance. In con as , using ou algo i hm
he maximum e o in he conduc ance o an edge is 1.1·10−8 o pe u ba ions o o de o
magni ude 10−8; and he maximum e o in he conduc ance is 8.7·10−8 o pe u ba ions
o o de o magni ude 10−7. We ha e con inued his expe imen wi h pe u ba ions o o de
o magni ude 10−1, ob aining a conduc ance whose maximum e o is 7.8·10−2.
Figu e 2.8: Reco e ed ne wo k wi h m= 23 adii in Example 2.4.3.
Table 2.4: Maximum e o in he eco e ed conduc ance wi h one signi ican digi .
In e al m7 11 15 19 23 27 31 35 39 43 47
Unpe u bed 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 in e se conduc ance p oblem
Figu e 2.9: Reco e ed ne wo k wi h m= 35 adii in Example 2.4.3 and pe u ba ions in he
in e al [−10−1,10−1]. (α= 0.96).
Table 2.5: Maximum ||c′−c||
||N′−N||F in he eco e ed conduc ance wi h wo signi ican digi s.
In e al m7 11 15 19 23 27 31 35 39 43 47
Unpe u bed 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 E o Va ia ion wi h espec o he penal y pa am-
e e
This sec ion is a e iew o [37, Sec ion 2]. The o mula ion o P oblem 2.3.1 in oduces
he de ia ion wi h espec o he piecewise cons an hypo hesis as a penal y a he han
imposing he hypo hesis and minimizing he di e ence be ween N′and N. As µ→ ∞, he
o mula ion o he p oblem co esponds wi h his las scena io.
As discussed in he p e ious sec ion, in he case ha he eal conduc ance cis piecewise
cons an on he pa i ion E=E1⊔···⊔ Es, wi h s≪ |E|, he solu ion o he p oblem is
almos equal o e e y µ > 0, eco e ing a conduc ance ha is e y close o c, excep when
µ→0, ha is when he p oblem becomes uns able. The e o e, in ha case, he penal y
o mula ion o any alue o µ ha is big enough gi es almos he same expe imen al esul s
as he app oach o imposing he hypo hesis and minimizing he di e ence be ween N′and
N.
Ne e heless, he penal y o mula ion has he ad an age o making possible o conside
E o Va ia ion wi h espec o he penal y pa ame e 61
in e media e alues o µ∈(0,∞) ha allow us o ob ain a good app oxima ion o he
conduc ance a oiding he ins abili ies in cases in which he conduc ance is no piecewise
cons an on he pa i ion E=E1⊔···⊔Es, as we can see in he ollowing example.
Example 2.5.1. We conside he DC spide ne wo k Γ = ( ¯
F, c)wi h m= 19 adii, see
Figu e 2.10, and we show how he e o in eco e ing he conduc ance a ies wi h µwhen a
piecewise cons an conduc ance hypo hesis which does no hold in he ne wo k is used.
Figu e 2.10: Well-connec ed spide ne wo k Γ wi h m= 19.
The conduc ance is piecewise cons an on a pa i ion E=E1⊔E2⊔E3⊔E4, wi h
c(E1) = 1, c(E2) = 5, c(E3) = 2 and c(E4) = 4.
We un ou algo i hm assuming ha he conduc ance is piecewise cons an on a di e en
pa i ion E=A1⊔A2⊔A3, wi h A1=E1,A2=E2and A3=E3⊔E4.
We ob ain a nume ical app oxima ion o a local minimum o P oblem 2.3.1 wi h his
alse hypo hesis o he ollowing 498 alues o µ:µ= 0, µ= 10−10j,µ= 10−8j,µ= 10−6j,
µ= 10−4jand 10−2j o j= 1,2, ..., 99, µ= 1 and µ= 105. The e o in he eco e ed
conduc ances ||c′−c|| is shown in Figu e 2.11 o he alues such ha µ≤5·10−7wi h a
linea in e pola ion. Addi ionally, he e o ||c′−c|| is shown in Figu e 2.12 in a loga i hmic
scale wi h a linea in e pola ion o all he posi i e alues excep µ= 105, o which he
eco e ed conduc ance is almos equal o he one eco e ed wi h µ= 1. In all igu es, he
eco e ed alues o he conduc ances ha e been ounded wi h one decimal digi o he sake
o cla i y.
Fo µ= 0, we ob ain he ne wo k in Figu e 2.13. The e o is 7.8519, which is much
highe han o any o he o he alues o µ. Despi e in his case we ha e he minimum
di e ence wi h espec o he da a ||N′−N||F = 5.9512 ·10−6, and hus also his is he
solu ion a which he e alua ion o pis minimum (equal o 3.5417 ·10−11), he eco e ed
62 The in e se conduc ance p oblem
Figu e 2.11: E o in he eco e ed conduc ance as a unc ion o µ.
Figu e 2.12: E o in he eco e ed conduc ance as a unc ion o log(µ).
ne wo k di e s a lo om he eal one, being max |c−c′|= 2.9997, because he in e se
conduc ance p oblem wi hou egula iza ion is ill-posed.
When we eco e he conduc ance o he p oblem wi h a posi i e alue o µ, he e o
dec eases d as ically, and in µ= 4 ·10−10 he e o is minimum, ||c′−c|| = 2.3567. In
Figu e 2.14, we show he eco e ed ne wo k o his alue. Despi e he e o in he da a,
||N′−N||F = 1.0791 ·10−5, is g ea e han o µ= 0, he eco e ed conduc ance is much
close o he eal one, wi h max |c−c′|= 1.3334. The e alua ion o pis equal o 2.6808·10−9.
Fo µ > 4·10−10, he e o mono onically inc eases wi h µ. F om µ= 4.7·10−1onwa ds,
he eco e ed conduc ance almos does no a y wi h µ, being almos piecewise cons an
on he pa i ion E=A1⊔A2⊔A3, wi h c′(A1) = 0.9999, c′(A2) = 5.0145 and c′(A3) =
2.1943. The e o is ||c′−c|| = 3.7250. The de ia ion wi h espec o he da a is maximum,
||N′−N||F = 0.0078, he e alua ion o pis equal o 6.0897 ·10−5, and max |c−c′|= 1.8057.
E o Va ia ion wi h espec o he penal y pa ame e 63
Figu e 2.13: Reco e ed ne wo k wi h µ= 0.
Figu e 2.14: Reco e ed ne wo k wi h µ= 4 ·10−10.
The eco e ed conduc ance o µ= 105can be seen in Figu e 2.15, and in Table 2.6 he e is
a summa y o he esul s o his alue o µ, and also o µ= 0 and o he alue o µwi h
minimum e o .
This example illus a es ha i we conside a piecewise cons an conduc ance hypo h-
esis on a gi en pa i ion ha does no sui he eal ne wo k, bu he eal conduc ance is
no a om a piecewise cons an conduc ance in his pa i ion, he e o in he eco e ed
conduc ance is lowe when in oducing he penaliza ion (µ > 0) han i we do no use i
64 The in e se conduc ance p oblem
Figu e 2.15: Reco e ed ne wo k wi h µ= 10000.
Table 2.6: E o in he eco e ed conduc ance o di e en alues o µ.
µ||c−c′|| max{|c−c′|} ||N′−N||F
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 esul s suppo using a penal y e m in ou o mula ion o P oblem 2.3.1 and will
be use ul in many applied in e se conduc ance p oblems. F om an applied pe spec i e, i
is easonable o wo k wi h a piecewise cons an conduc ance hypo hesis ha may no be
en i ely accu a e bu closely app oxima es eali y. This can be in en ional, such as when
using an app oxima e piecewise cons an model, o unin en ional, because we a e eco e ing
a ne wo k whose conduc ance should be piecewise cons an on a pa i ion unde no mal
ci cums ances, bu may exhibi pe u ba ions in ce ain unknown edges.
In he gi en example, we achie e he minimum e o o an in e media e alue o µ∈(0,∞)
o which he e is a comp omise be ween de ia ing wi h espec o he da a Nand wi h e-
spec o he piecewise cons an conduc ance hypo hesis.
In he solu ion wi h µ= 4 ·10−10, we see ha he eco e ed conduc ance c′is close o
being cons an on A1and on A2, on which he eal conduc ance is cons an , while c′is a
om being piecewise cons an on A3, and he alue o c′a any edge o E3is lowe han he
alue o c′a any edge o E4. This sugges s he idea o choosing a ine pa i ion han he
o iginal one o he subse s on which he solu ion is a om being cons an . Then, we would
eco e he conduc ance again P oblem 2.3.1 by conside ing his e ined pa i ion seeking a
solu ion wi h a lowe e o .
2.6. OPTIMALITY GUARANTEES OF THE RECOVERED CONDUCTANCES 65
2.6 Op imali y gua an ees o he eco e ed conduc ances
This sec ion is a e iew o [37, Sec ion 3]. In he p e ious sec ion we ha e shown an example
in which ob aining an app oxima ion o a local minimum ∗∈Ao P oblem 2.3.1 wi h a
alue µ > 0 and a pa i ion E=E1⊔ ···⊔ Eswi h s≪ |E|such ha cis no piecewise
cons an on i allow us o eco e an app oxima ion o cwi h some s abili y. Recall ha , in
his case o a alse piecewise cons an conduc ance hypo hesis, a solu ion ˆ
∈A o P oblem
2.3.1 mus sa is y p(ˆ
)>0. In his case, we do no know a p io i he alue o p(ˆ
), so we can
no ell whe he ∗is an app oxima ion o a global minimum o no jus om he alue o
p( ∗), e en i he eco e y is s able. Ne e heless, we can apply echniques o Sum o Squa es
(SOS) decomposi ions o polynomials [81] o his p oblem o y o ind a gua an ee ha
∗is an app oxima ion o a global minimum, and as a consequence, an app oxima ion o a
solu ion o P oblem 2.3.1.
SOS decomposi ions a e elaxa ions used in polynomial op imiza ion o ob ain a lowe
bound o a eal polynomial in a eal algeb aic se . We say ha a polynomial is SOS i i
can be w i en as a sum o squa es o eal polynomials and we deno e by I(V(J)) he ideal
o polynomials anishing on V(J). We deno e by he ec o con aining all he a iables o
P oblem 2.3.1, and we de ine he coo dina e ing o he algeb aic se V(J) as he quo ien
ing R[ ]/I(V(J)). We o mula e he ollowing SOS p oblem, which is a pa icula case o
he main p oblem s udied in [56].
P oblem 2.6.1. Gi en a bound d∈N, a qua ic p, an algeb aic se V(J), and a alue
z≥0, is he e any polynomial q such ha
p( )−z=q( )in R[ ]/I(V(J)); qis SOS, and deg(q)≤2d?
Le z=p( ∗) o ∗∈Aand suppose ha P oblem 2.6.1 has an a i ma i e answe o
p,V(J), zand some d, hen p( )≥zin V(J). The e o e, ∗is a global minimum o pin A
and hus a solu ion o P oblem 2.3.1. In Example 2.6.2, we will show a ne wo k in which we
a e able o gua an ee ha a minimum o P oblem 2.3.1 is global by inding an a i ma i e
answe o P oblem 2.6.1.
I could be possible ha he e is a global minimum ∗∈A o P oblem 2.3.1 such ha
P oblem 2.6.1 has a nega i e answe o V(J), z=p( ∗) and any d, because o mos
algeb aic a ie ies he e exis nonnega i e polynomials which a e no SOS in he coo dina e
ing. Ne e heless, p−p( ∗) in V(J) can always be app oxima ed by SOS polynomials, and
he minimum deg ee o hose polynomials depends on he closeness o he app oxima ion
[56], (see also [73] o mo e de ails).
Gi en a G ¨obne basis o I(V(J)), P oblem 2.6.1 educes o a semide ini e p og am (SDP)
[56]. I is equi alen o ind a symme ic posi i e semide ini e ma ix Qsuch ha he no mal
o m o p−z−uTQu in he G ¨obne basis is ze o, whe e u is a ec o whose en ies a e he
s anda d monomials co esponding o he G ¨obne basis, ( ha is, he monomials which a e
no di isible by any leading e m o he polynomials in ha basis) wi h deg ee a mos d,
see [81].
In gene al, i is compu a ionally complex o de e mine a G ¨obne basis o he eal adical
I(V(J)) o J. Al e na i ely, we can check i p−zis sum o squa es in R[ ]/J, which is a
66 The in e se conduc ance p oblem
SDP p oblem ha only equi es a G ¨obne basis o J, and ob aining an a i ma i e answe
o his p oblem is a su icien condi ion o ob aining an a i ma i e answe o P oblem 2.6.1,
because he e alua ion o a polynomial which is equal o p−zin R[ ]/J a any poin o V(J)
is equal o he e alua ion o p−za ha poin .
E en wi h he elaxa ion o he abo e pa ag aph, he compu a ion o a G ¨obne basis o
he ideal Jis compu a ionally expensi e when Jis he ideal o a spide ne wo k o a medium
o la ge numbe o adii, because he numbe o a iables o P oblem 2.3.1 and he numbe
o polynomials in (2.3) inc ease wi h he numbe o adii. Ne e heless, he ideal Jdepends
only on he numbe o adii, and i does no depend on he Di ichle - o-Neumann ma ix
no on he pa i ion used in P oblem 2.3.1, so once a G ¨obne basis o Jco esponding o
a numbe o adii is compu ed, i could be used o check i a local minimum o any case o
P oblem 2.3.1 in a spide ne wo k wi h his numbe o adii is a global minimum.
Example 2.6.2. We conside he spide ne wo k Γ=(¯
F, c)wi h m= 3 adii in Figu e
2.16, we eco e i s conduc ance using a piecewise cons an conduc ance hypo hesis which
does no hold in he ne wo k, and we check i he ob ained solu ion is a global minimum o
P oblem 2.3.1.
Figu e 2.16: Real ne wo k wi h m= 3.
In he eal ne wo k, we ha e c(x1, x4) = 1, c(x2, x4) = 2 and c(x3, x4) = 3. The Laplacian
ma ix o Γ is
L=
100−1
020−2
003−3
−1−2−3 6
,
and i s Di ichle - o-Neumann ma ix is
N=1
6
5−2−3
−2 8 −6
−3−6 9
.
We se µ= 1 and we ob ain a nume ical app oxima ion o a local minimum o P oblem
2.3.1 unde he hypo hesis ha he conduc ance is piecewise cons an on E=E1⊔E2, wi h
E1={ex2x4, ex1x4}and E2={ex3x4}; which is alse in Γ. In P oblem 2.3.1, we do no include
Op imali y gua an ees o he eco e ed conduc ances 67
he a iable ω(E2), no he e m (c′(x3, x4)−ω(E2))2in p, since as E2only has one edge, in
he solu ion we will ha e ω(E2) = c′(x3, x4) i ially. The p oblem is o minimize
p=c′(x1, x4)−c′(x1, x4)ux1(x4)−5
62+−c′(x2, x4)ux1(x4) + 1
32
+−c′(x3, x4)ux1(x4) + 1
22+−c′(x1, x4)ux2(x4) + 1
32
+c′(x2, x4)−c′(x2, x4)ux2(x4)−4
32+ (−c′(x3, x4)ux2(x4) + 1)2
+−c′(x1, x4)ux3(x4) + 1
22+ (−c′(x2, x4)ux3(x4) + 1)2
+c′(x3, x4)−c′(x3, x4)ux3(x4)−3
22+ (c′(x1, x4)−ω(E1))2+ (c′(x2, x4)−ω(E1))2.
subjec o
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 o all exy ∈E.
Using an in e io poin me hod, we ob ain a local minimum ∗such ha p( ∗) = 0.1995,
and he alues o all he a iables in ∗a e 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 de ine he ideal J=⟨g1
4, g2
4, g3
4⟩. We choose he deg ee e e se lexicog aphic o de
wi h c′(x1, x4)> c′(x2, x4)> c′(x3, x4)> ux1(x4)> ux2(x4)> ux3(x4), and we compu e he
G ¨obne basis J=⟨h1, h2, h3, h4, h5, h6⟩o Jwi h espec o ha monomial o de using he
gbasis unc ion in Ma lab. The polynomials o he basis a e
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 sol e P oblem 2.6.1 o p,z=p( ∗) and d= 2, bu wi h he elaxa ion ha
consis s in subs i u ing he coo dina e ing R[ ]/I(V(J)) by R[ ]/J. Tha is, we check i he e
is a symme ic posi i e semide ini e ma ix Qsuch ha he no mal o m o p−0.1995−uTQu
in ⟨h1, h2, h3, h4, h5, h6⟩is null, whe e uis a ec o whose en ies a e he s anda d monomials
wi h deg ee a mos 2 co esponding o ⟨h1, h2, h3, h4, h5, h6⟩.
Using he unc ion indbound om SOOSTOOLS, a oolbox o Ma lab o sol ing sum
o squa es p og ams [80], and he SDP sol e SeDuMi [103], we ob ain an a i ma i e answe
o he aised ques ion.
74 Simul aneous eco e y o he opology and admi ance o a ne wo k
Any NNLS p oblem is a con ex quad a ic op imiza ion p oblem, (see [92]), so e e y local
minimum o i is a global minimum. We can ob ain a solu ion Γ o P oblem 3.1.2 calcula ing
a minimum o i s associa ed NNLS p oblem wi h an in e io poin me hod. The in e io poin
me hods a e among he main nume ical algo i hms used o sol e NNLS p oblems, (see [43]).
We deno e he nume ical solu ion Γ wi h e o ms ≡ ms(Γ,u,s) ob ained om Eand
(u,s) as [Γ, ms] = ne wo k eco e y(E, u,s).
A su icien condi ion ha implies ha P oblem 3.1.2 has a unique solu ion is ha
m≥|E|
|V|and κ(ME,u)<∞,i.e., he condi ion numbe o ME,uis ini e, (see [92]). We will
equi e in Sec ion 3.6 ha he da a se s used o es he spa se ne wo k eco e y algo i hm
sa is y m≥|E|
|V|. Ne e heless, o en he condi ion κ(ME,u)<∞is no sa is ied, and hus
he e a e mul iple solu ions o P oblem 3.1.2; as seen in Example 3.1.1, in which he e a e
mul iple solu ions wi h ze o e o .
As we will see in Sec ion 3.6, in cases in which he pai (u,s) con ains ol age and powe
da a co esponding o an elec ical ne wo k wi h some e o , he alue o he condi ion
numbe κ(ME,u) is ini e bu i is e y high, so P oblem 3.1.2 has a unique solu ion bu i
is se e ely ill-posed.
3.2 Re o mula ion o he p oblem: Reco e y o a spa se
elec ical ne wo k
This sec ion is a e iew o he beginning o [88, Sec ion 4]. As we ha e discussed in he
p e ious sec ion, gi en a da a da a pai (u,s) and a se o edges E, he P oblem 3.1.2 o
eco e ing a ne wo k Γ wi h minimum e o such ha E(Γ) ⊆Eis ill-posed. Because o
ha , e en i he e is a solu ion Γ∗ o he exac P oblem 3.0.2 whose opology is much mo e
spa se han (V, E), i.e.,|E(Γ∗)|≪|E|, sol ing P oblem 3.1.2 we usually ge a solu ion whose
opology is (V, E). I he numbe o edges in Eis high, a solu ion wi h ha opology is no
e icien o applica ions. We a e in e es ed in eco e ing a spa se ne wo k such ha he
i ing e o o he da a is below a ixed ole ance. Such a ne wo k would allow he e icien
and accu a e esolu ion o usual p oblems in elec ical ne wo ks which equi e he admi ance
and opology. Those applica ions include ailu e iden i ica ion, powe low op imiza ion o
gene a ion scheduling [57].
We o mula e he ollowing p oblem o eco e ing a spa se ne wo k. Gi en a ixed ole -
ance, we seek o eco e a ne wo k such ha i s ms is below his ole ance and none o he
ne wo ks wi h he same se o e ices as ou ne wo k and a subse o i s edges has a ms
below he ole ance.
P oblem 3.2.1 ([88]).Le Vbe a ini e se o e ices, le Ebe a se o edges, le 0<|u|min ≤
|u|max be posi i e alues, le m∈N∗, le u,s∈C(V, Cm), espec i ely u,s∈C(V, Rm), such
ha |u|min ≤ |uj| ≤ |u|max o all j= 1, . . . , m and le ol >0be a ole ance. De e mine an
AC ne wo k Γ = (V, a), espec i ely a DC ne wo k Γ = (V, c), wi h se o edges E(Γ) ⊆E
such ha ms(Γ,u,s)≤ ol and Γis “minimal” in he ollowing sense: Gi en any elec ical
ne wo k Γ′= (V, a′), espec i ely Γ′= (V, c′), wi h edge se E(Γ′), we ha e ha
1. I E(Γ′) = E(Γ), hen ms(Γ′,u,s)≥ ms(Γ,u,s).
3.3. SPECTRAL NETWORK SPARSIFICATION 75
2. I E(Γ′)⊊E(Γ), hen ms(Γ′,u,s)> ol.
Rema k 3.2.2. In pa icula , we ha e ms(Γ′,u,s)> ol ≥ ms(Γ,u,s) i E(Γ′)⊊E(Γ).
Howe e , no ice ha he e could be an elec ical ne wo k E(Γ′) = (V, a′) such ha
ms(Γ′,u,s)< ms(Γ,u,s) and E(Γ′)⊂ E(Γ).
A i s nai e idea o sol e P oblem 3.2.1 could be o eco e a ne wo k Γ sol ing P oblem
3.1.2 wi h he se o edges E,i.e., [Γ, ms] = ne wo k eco e y(E, u,s), and hen o emo e
om E(Γ) he edges whose admi ance alues a e close o ze o. Howe e , his app oach
p esen s some p oblema ic issues.
Fi s , le Γ∗be a solu ion o P oblem 3.2.1, wi h se o edges E(Γ∗). As we will see
in Sec ion 3.6, i E(Γ∗) is much smalle han E, hen usually he condi ion numbe o he
ope a o associa ed wi h he ne wo k eco e y P oblem 3.1.2 using se E,κ(ME,u), is much
bigge han he condi ion numbe o he ope a o associa ed wi h he ne wo k eco e y
P oblem 3.1.2 using se E(Γ∗), κ(ME(Γ∗),u). Then, he alues o he admi ance o Γ a he
edges o E E(Γ∗) a e usually a om ze o. Fo ins ance, in Example 3.3.4, sol ing he
P oblem 3.1.2 wi h he edge se E(KV) = {exy, exz, eyz}, we can ge solu ions wi h ze o e o
such ha he alues o he admi ance a all edges o E(KV) a e a om ze o, despi e he
ac ha he e a e solu ions wi h ze o e o and less han h ee edges.
Second, in Γ could exis edges wi h admi ance close o ze o whose emo al would lead
o a ne wo k which would no co ec ly i he da a (see Example 3.6.1). In o de o a oid
hose p oblems, he algo i hm ha we p opose in Sec ion 3.5 algo i hm uses echniques o
spec al spa si ica ion o ne wo ks in o de o emo e edges om ne wo ks.
3.3 Spec al ne wo k spa si ica ion
This sec ion is a e iew o [88, Subsec ion 4.1]. Spielman and Teng in oduced he no ion
o spec al spa si ica ion o a eal weigh ed g aph, ( ha is, a DC ne wo k), in [95], (see also
he subsequen pape s [16, 93, 94] on his opic).
De ini ion 3.3.1 ([93]).Fo ε > 0, we say ha a DC ne wo k Γ′= (V, c′) wi h ene gy E′is
an ε-app oxima ion o a DC ne wo k Γ = (V, c) wi h ene gy Ei o all u∈C(V):
1
1 + εE(u, u)≤ E′(u, u)≤(1 + ε)E(u, u).(3.5)
The ene gy o an AC ne wo k Γ = (V, a), wi h a=c−ib and c, b ∈C+(E(Γ)), is a
complex bilinea o m, so we can no apply De ini ion 3.3.1 o i . Ne e heless, we can
apply his de ini ion sepa a ely o i s conduc ance and suscep ance ne wo ks, Γc= (V, c)
and Γb= (V, b). We in oduce he ollowing de ini ion.
De ini ion 3.3.2. Fo ε > 0, we say ha an AC ne wo k Γ′is an ε-app oxima ion o an AC
ne wo k Γ i he conduc ance and suscep ance ne wo ks o Γ′a e ε-app oxima ions o he
conduc ance and suscep ance ne wo ks o Γ, espec i ely.
76 Simul aneous eco e y o he opology and admi ance o a ne wo k
Algo i hm 1 Γ′=Spa si y(Γ, ε).
Se = 8|V|·log(|V|)/ε2,c′= 0, and E(Γ′) = ∅.
o each edge exy ∈E(Γ) do
Assign o edge exy a p obabili y pxy p opo ional o c(x, y) e(x, y).
end o
Take samples independen ly wi h eplacemen om E(Γ), and each ime he edge exy is
sampled, inc ease he alue o c′(x, y) and c′(y, x) by c(x, y)/ pxy, (and as a consequence,
add he edge exy o E(Γ′) i i is he i s ime ha exy is sampled).
In [16] he e is a p ocedu e (Algo i hm 1) ha can be used o cons uc a spa se app ox-
ima ion Γ′= (V, c′) o a DC ne wo k Γ = (V, c) such ha E(Γ′)⊆E(Γ).
Algo i hm 1 is no gua an eed o p oduce an ε-app oxima ion o Γ, bu in [16] he e is a
p oo o he ollowing heo em:
Theo em 3.3.3 (Ba son, Spielman, S i as a a, Teng).Le Γbe a DC ne wo k, le ε∈R,
0< ε ≤1and le Γ′=Spa si y(Γ, ε). Then Γ′is an ε-app oxima ion o Γwi h p obabili y a
leas 1/2.
No e ha he edges ha a e emo ed in Algo i hm 1 a e he ones ha a e ne e sam-
pled. The choice o he sampling p obabili ies in he algo i hm has an in e es ing physical
in e p e a ion. By (1.13), o each edge exy ∈E, he p obabili y o sampling i , pxy, is
p opo ional o he dimensionless a io
c(x, y) e(x, y) = c(x, y)
ce(x, y)=c(x, y)
c(x, y) + ce
exy (x, y)∈(0,1],
whe e ce
exy (x, y)≥0 is he e ec i e conduc ance be ween xand yin he ne wo k Γ exy
ob ained om Γ by emo ing he edge exy, which is equal o he con ibu ion o he e ec i e
conduc ance ce(x, y) o he pa hs be ween xand y h ough he es o e ices o he ne wo k
Γ.
The p obabili y o choosing edge exy in each sample is high i he con ibu ion o he
alue c(x, y) o he e ec i e conduc ance be ween xand yin Γ, ce(x, y), is e y impo an ,
ha is, i c(x, y) is big compa ed o ce
exy (x, y). The limi case is ha in which he emo al o
exy isola es xand y, in which ce
exy (x, y) = 0, so c(x, y) e(x, y) = 1; and hus he p obabili y
o keeping exy in Γ′is he highes possible.
The p obabili y pxy is low in he opposi e case, ha is, when c(x, y)≪ce
exy (x, y). In
ha case emo al o edge exy does no signi ican ly a ec he e ec i e conduc ance be ween
xand y, because ce
exy (x, y)≈ce(x, y). In ha case, he p obabili y o keeping exy in Γ′is
low.
Example 3.3.4. We conside he DC ne wo k in Figu e 3.2, wi h conduc ance cwhose
alues a each edge a e gi en in Table 3.1. In he same able we indica e he sampling
p obabili ies calcula ed o each edge in Algo i hm 1.
The alues o he conduc ance a edges {x1, x2}and {x3, x4}a e wo o de s o magni ude
smalle han a he es o edges, ne e heless, edge {x3, x4}is c ucial because i is he only
3.4. SPARSIFICATION OF RECOVERED ELECTRICAL NETWORKS 77
Figu e 3.2: Topology o he ne wo k in Example 3.3.4.
Table 3.1: Conduc ances and sampling p obabili ies o he edges in he ne wo k.
Edges
{x1, x2} {x1, x3} {x2, x3} {x3, x4} {x4, x5} {x4, x6}
Conduc ance 0.5797 75.980 75.980 0.4698 94.599 79.909
Conduc ance imes
e ec i e esis ance
0.0150 0.9925 0.9925 1 1 1
Sampling p obabili y 0.0030 0.1985 0.1985 0.2 0.2 0.2
connec ion be ween e ices x3and x4, so i has a g ea p obabili y o being sampled o
o m any spa se app oxima ion o he ne wo k, while edge {x1, x2}is expendable, because
i s conduc ance c(x1, x2) is equal o only 1.5% o he e ec i e conduc ance be ween nodes
x1and x2. The cu en can low om node x1 o node x2wi h much g ea e ease by edges
{x1, x3}and {x2, x3}, so he sampling p obabili y o {x1, x2}is close o ze o.
In he case o an AC ne wo k Γ = (V, a), we will deno e by Γ′=Spa si y(Γ, ε) an AC
ne wo k cons uc ed ollowing he nex p ocedu e. Fi s , we apply Algo i hm 1 sepa a ely
o he conduc ance and suscep ance ne wo ks, Γcand Γb, o Γ; ge ing Γ′
c= (V, c′) and Γ′
b=
(V, b′), espec i ely. Then, Γ′= (V, a′) = (V, c′−ib′). No e ha E(Γ′) = E(Γ′
c)∪E(Γ′
b), so in
he spa si ica ion p ocess o an AC ne wo k we emo e he edges e ased in he spa si ica ion
o bo h Γcand Γb.
By de ini ion, Γ′will be an ε-app oxima ion o Γ i Γ′
cis an ε-app oxima ion o Γcand Γ′
b
is an ε-app oxima ion o Γb. By Theo em 3.3.3, i 0 < ε ≤1, hen Γ′is an ε-app oxima ion
o Γ wi h p obabili y a leas 1
4.
3.4 Spa si ica ion o eco e ed elec ical ne wo ks
This sec ion is a e iew o [88, Subsec ion 4.2]. Once we ha e a p ocedu e o spa si y any
ne wo k, he key obse a ion o de elop ou algo i hm o spa se ne wo k eco e y is ha
spec al spa si ica ion is gua an eed o p ese e he i ing p ope ies o a ne wo k o some
ex en .
We in oduce some no a ion o he main esul o he chap e in he case o DC ne wo ks.
Le Γ = (V, c) be a DC ne wo k wi h Laplacian Land le u,s∈C(V, Rm), such ha
0<|u|min ≤ |uj| ≤ |u|max o all j= 1, . . . , m. Fo each j= 1, ..., m, we deno e as QΓ,uj
he linea ope a o on C(V) de ined o each ∈C(V) as QΓ,uj( ) = ujL(uj ). Clea ly,
QΓ,ujis a sel -adjoin and posi i e semide ini e ope a o . Now, we deno e as QΓ,u he
linea ope a o on C(V, Rm) de ined o each ( 1, ..., m)∈C(V, Rm) as QΓ,u( 1, ..., m) =
78 Simul aneous eco e y o he opology and admi ance o a ne wo k
(QΓ,u1( 1), ..., QΓ,um( m)). Fo any = ( 1, ..., m),w= (w1, ..., wm)∈C(V, Rm), we ha e
ha ⟨QΓ,u( ),w⟩=Pm
j=1 RVL(uj j)ujwjdx =Pm
j=1 RVuj jL(ujwj)dx
=⟨ ,QΓ,u(w)⟩,
so he ope a o QΓ,uis sel -adjoin . F om he same exp ession, when =w, we can see ha
QΓ,uis also posi i e semide ini e. We deno e by 1m= (χV, ..., χV)∈C(V, Rm) he ec o
unc ion whose alue is equal o 1 a all e ices. No e ha QΓ,u(1m) = ME(Γ),u(c).
Fo each j= 1, ..., m, we deno e as u−1
j∈C(V) he unc ion de ined o each x∈Vas
u−1
j(x) = 1/uj(x). We also de ine he ec o unc ion
ϕu=RVu−1
1dx
||u−1
1||2u−1
1, ..., RVu−1
mdx
||u−1
m||2u−1
m∈C(V, Rm).
Ou main o iginal esul consis s in he ollowing uppe bound o he ms o any spa se
app oxima ion in a ixed da a se .
Theo em 3.4.1 (Main heo em).Gi en a DC ne wo k Γ = (V, c), posi i e alues 0<
|u|min ≤ |u|max,m∈N∗and u,s∈C(V, Rm)such ha |u|min ≤ |uj| ≤ |u|max o all
j= 1, . . . , m; i Γ′is an ε-app oxima ion o Γ, hen:
ms(Γ′,u,s)≤ ms(Γ,u,s) + ε∥QΓ,u∥2·∥1m−ϕu∥
pm|V|.
P oo . Le Γ′= (V, c′) be an ε-app oxima ion o Γ, wi h Laplacian L′. As QΓ′,u(1m) =
ME(Γ′),u(c′), by (3.3) we ge ha
ms(Γ′,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)∥
= ms(Γ,u,s) + 1
pm|V|∥(QΓ′,u−QΓ,u) (1m)∥.
The cons an unc ions belong o he null space o any Laplacian, he e o e ϕubelongs
o he null space o QΓ′,u−QΓ,u, and hus
∥(QΓ′,u−QΓ,u) (1m)∥=∥(QΓ′,u−QΓ,u) (1m−ϕu)∥
≤ ∥QΓ′,u−QΓ,u∥2·∥1m−ϕu∥.(3.6)
In o de o comple e he p oo , i is enough o show ha ∥QΓ′,u−QΓ,u∥2≤ε∥QΓ,u∥2.
Now, QΓ′,u−QΓ,uis a sel -adjoin ope a o , so i s spec al no m is equal o he maximum
o he absolu e alue o i s eigen alues. I is s aigh o wa d o p o e ha i s eigen alues a e
hose o he ope a o s QΓ′,uj−QΓ,uj o all 1 ≤j≤m. In pa icula , he e is a leas one
index ksuch ha
∥QΓ′,u−QΓ,u∥2=∥QΓ′,uk−QΓ,uk∥2.
Spa si ica ion o eco e ed elec ical ne wo ks 79
Le u0∈C(V) be an eigen ec o o QΓ′,uk−QΓ,ukco esponding wi h i s eigen alue ha
has he la ges absolu e alue such ha ∥u0∥= 1. Then
∥QΓ′,u−QΓ,u∥2=|⟨u0,(QΓ′,uk−QΓ,uk) (u0)⟩|.
Now, deno ing as Eand E′ he ene gy o Γ and Γ′, espec i ely, we ha e ha
⟨u0,(QΓ′,uk−QΓ,uk) (u0)⟩=⟨u0, uk(L′−L)(uku0)⟩
=ZV
u0uk(L′−L)(u0uk)dx
=E′(u0uk, u0uk)−E(u0uk, u0uk).
E alua ing (3.5) a u=u0uk∈C(V) we ge
1
1 + εE(u0uk, u0uk)≤ E′(u0uk, u0uk)≤(1 + ε)E(u0uk, u0uk).(3.7)
F om he igh inequali y o (3.7), we ha e:
E′(u0uk, u0uk)−E(u0uk, u0uk)≤εE(u0uk, u0uk),
and om he le inequali y in (3.7):
−(E′(u0uk, u0uk)−E(u0uk, u0uk)) ≤ε
1 + εE(u0uk, u0uk)< εE(u0uk, u0uk).
Joining he las wo inequali ies, we ge
∥QΓ′,u−QΓ,u∥2≤εE(u0uk, u0uk).
Mo eo e ,
E(u0uk, u0uk) = ZV
u0ukL(u0uk)dx
=⟨u0, ukL(uku0)⟩
=⟨u0,QΓ,uk(u0)⟩.
By he Cou an -Fishe heo em [94], he e alua ion o he quad a ic o m associa ed wi h
he ope a o QΓ,uka any uni ec o is less o equal han i s maximum eigen alue, which
is equal o he no m o his ope a o because i is posi i e semide ini e, so:
∥QΓ′,u−QΓ,u∥2≤ε∥QΓ,uk∥2≤ε∥QΓ,u∥2,(3.8)
whe e he las inequali y holds because he eigen alues o QΓ,ua e hose o he ope a o s
QΓ,uj o all 1 ≤j≤m.
Rema k 3.4.2. In (3.6), i is possible o in oduce any ec o unc ion equal o
λ1u−1
1, ..., λmu−1
m∈C(V, Rm), o any choice o λ1, ..., λm∈R, because all o hem be-
long o he null space o QΓ′,u−QΓ,u. Among hem, we choose o in oduce he e m
ϕubecause i is he choice ha minimizes ρ(λ1, .., λm)≡
1m−λ1u−1
1, ..., λmu−1
m
2=
80 Simul aneous eco e y o he opology and admi ance o a ne wo k
Pm
j=1 RVχV−λju−1
j2dx. E ec i ely, i we look o a minimum o ρ, i s pa ial de i a i es
mus be ze o:
∂ρ(λ1, .., λm)
∂λk
= 2 ZV−u−1
k+λku−1
k2dx = 0,
so he only possible choice o he λkis:
λk=RVu−1
kdx
||u−1
k||2,
which is indeed he global minimum o ρbecause i s Hessian is posi i e de ini e: i j=k,
hen ∂2ρ(λ1,..,λm)
∂λk∂λj= 0, and o each k= 1, ..., m,
∂2ρ(λ1, .., λm)
∂λ2
k
= 2 ZVu−1
k2dx > 0.
Rema k 3.4.3. The e m ∥QΓ,u∥2·∥1m−ϕu∥
√m|V| ha appea s in he uppe bound gi en by he
las heo em depends only on he elec ical ne wo k Γ and he i s elemen o he da a pai
(u,s), so i we wan a spa se app oxima ion o Γ such ha he ms o he app oxima ion
does no inc ease (wi h espec o ms(Γ,u,s)) in he spa si ica ion p ocedu e abo e a ixed
alue, he e is an ε > 0 such ha any ε-app oxima ion o Γ is gua an eed o mee his
equi emen .
In he case o an AC elec ical ne wo k Γ, we deno e by Γc= (V, c) and Γb= (V, b)
he conduc ance and suscep ance ne wo ks o Γ, whose espec i e Laplacians a e Lcand Lb.
Addi ionally, we de ine he unc ion
∆(Γ,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)21/2
,
and we ha e he ollowing esul , which is he AC analogous o Theo em 3.4.1:
Theo em 3.4.4. Gi en an AC ne wo k Γ = (V, a),m∈N∗and u,s∈C(V, Cm), i Γ′is
an ε-app oxima ion o Γ, hen:
ms(Γ′,u,s)≤ ms(Γ,u,s) + ε∆(Γ,u)
p2m|V|,
whe e ∆(Γ,u)is a unc ion which depends only on Γand u.
P oo . Fi s , o e e y u∈C(V, C), we ha e ha
uL(u) = uL∗(u) = (ℜ(u) + iℑ(u))(Lc+iLb)((ℜ(u)−iℑ(u))),
and he e o e
ℜ(uL(u)) = ℜ(u)Lc(ℜ(u)) + ℜ(u)Lb(ℑ(u)) + ℑ(u)Lb(ℜ(u)) + ℑ(u)Lc(ℑ(u)),(3.9)
Spa si ica ion o eco e ed elec ical ne wo ks 81
and also
ℑ(uL(u)) = ℑ(u)Lc(ℜ(u)) + ℑ(u)Lb(ℑ(u)) + ℜ(u)Lb(ℜ(u)) + ℜ(u)Lc(ℑ(u)).(3.10)
Now, le Γ′= (V, a′) be an ε-app oxima ion o Γ, wi h Laplacian L′. Le Γ′
c= (V, c′) and
Γ′
b= (V, b′) be he conduc ance and suscep ance ne wo ks o Γ′, whose espec i e Laplacians
a e L′
cand L′
b. By (3.3) we ge ha
ms(Γ′,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)∥
= ms(Γ,u,s) + 1
pm|V|∥ME(Γ′),u(c′, b′)−ME(Γ),u(c, b)∥.
The squa e o he no m in he las equa ion is equal o
∥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 equa ions (3.9), (3.10) and (3.11), we can w i e
∥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)
whe e:
β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 ge
∥β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 ob ain ha ∥β4∥ ≤ εpm|V|∥QΓc,ℑ(u)∥2,
∥β6∥ ≤ εpm|V|∥QΓb,ℑ(u)∥2and ∥β7∥ ≤ εpm|V|∥QΓb,ℜ(u)∥2.
On he o he hand, Lc=QΓc,χV,L′
c=QΓ′
c,χV,Lb=QΓb,χVand L′
b=QΓ′
b,χV, so, by
he p oo o Theo em 3.4.1, we ha e ha ∥L′
c−Lc∥2≤ε∥Lc∥2and ∥L′
b−Lb∥2≤ε∥Lb∥2.
82 Simul aneous eco e y o he opology and admi ance o a ne wo k
As a consequence, o any ( ,w) = (( 1, ..., m),(w1, ..., wm)) ∈C(V, Rm)×C(V, Rm) i is
sa is ied ha
∥(Pc′−Pc) ( ,w)∥2=
m
X
j=1 ZV
2
j(L′
c−Lc)(wj)2dx
≤ ∥ ∥2
∞
m
X
j=1 ZV
(L′
c−Lc)(wj)2dx =∥ ∥2
∞
m
X
j=1 ∥(L′
c−Lc)(wj)∥2
2
≤ ∥ ∥2
∞
m
X
j=1 ∥(L′
c−Lc)∥2
2·∥wj∥2
2=∥ ∥2
∞·∥(L′
c−Lc)∥2
2·∥w∥2
2
≤ε2∥Lc∥2
2·∥ ∥2
∞·∥w∥2
2.
And, analogously, i is sa is ied ha ∥(Pb′−Pb) ( ,w)∥ ≤ ε∥Lb∥2·∥ ∥∞·∥w∥2. Applying
his esul , we ge he ollowing 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.
Conside ing in (3.12) all he uppe bounds ob ained o ∥β1∥, ..., ∥β8∥, we conclude he
p oo .
3.5 Algo i hm o spa se ne wo k eco e y
This sec ion is a e iew o [88, Subsec ion 4.3]. In his sec ion we p opose an algo i hm
o sol e he P oblem 3.2.1 o eco e ing simul aneously he opology and admi ance o a
spa se elec ical ne wo k.
I we ha e an elec ical ne wo k Γ = (V, a), a da a pai (u,s) and we choose an εsuch
ha he ms o any ε-app oxima ion o Γ in he da a pai (u,s) does no su pass a ixed
ole ance ol >0 (by Theo ems 3.4.1 and 3.4.4 such a εexis s i ms(Γ,u,s)< ol), he
only gua an ee abou he numbe o edges ha any ε-app oxima ion ob ained by execu ing
Spa si y(Γ, ε) will ha e is ha his numbe o edges will be less o equal han he numbe o
edges sampled in Algo i hm 1, = 8|V| · log(|V|)/ε2. I ol is small, he numbe o edges
sampled will be la ge, so mos ε-app oxima ions o Γ will ha e he same numbe o edges as
he o iginal ne wo k, hus hey will no be use ul o ou pu poses.
In he expe imen a ion we ha e ound ha , i we choose an εsuch ha Γ′=Spa si y(Γ, ε)
sa is ies ha |E(Γ′)|<|E(Γ)|, and hen we sol e P oblem 3.1.2 wi h he se E(Γ′); ( ha is,
we execu e [Γ′′, ms′′] = ne wo k eco e y(E(Γ′),u,s), de e mining a ne wo k Γ′′ = (V, a′′)
wi h se o edges E(Γ′′)⊆E(Γ′) such ha he e o ms′′ = ms(Γ′′,u,s) is minimum), hen
we ha e ms′′ ≤ ol in many cases, e en in cases in which ms(Γ′,u,s)> ol.
Ou app oach o sol e P oblem 3.2.1 consis s in he applica ion o Algo i hm 2. The
algo i hm s a s by i ing a ne wo k Γ = ne wo k eco e y(E, u,s) sol ing P oblem 3.1.2
wi h he da a pai (u,s) and he se o edges E. Then, ou goal is o pe o m a spa si ica ion
o Γ, Γ′=Spa si y(Γ, ε), ollowed by a eco e y o ano he ne wo k Γ′′ sol ing P oblem 3.1.2
3.6. EXPERIMENTAL RESULTS AND DISCUSSION 83
wi h he se o edges o he spa se app oxima ion, E(Γ′), as in he pa ag aph abo e, looking
o a ne wo k wi h less edges han he cu en one, and wi h a ms below he inpu ole ance
ol.
We do no know which choices o εcan lead us o a ne wo k wi h hese cha ac e is ics,
so we use a p ocedu e o explo a ion o le Algo i hm 2 ind sui able alues o ε. We s a
he algo i hm wi h an ini ial inpu alue o ε, and we do an i e a i e p ocedu e. Each
i e a ion begins by checking i Γ′=Spa si y(Γ, ε) has less edges han he cu en ne wo k Γ.
I his is no he case, he e is a high p obabili y, om Theo em 3.3.3, o Γ′being a spa se
app oxima ion so close o Γ ha i has he same se o edges, so we inc ease he alue o ε
mul iplying i by he inpu pa ame e ψ > 1, and we inish he i e a ion. In his way, in he
nex i e a ion he numbe o edges sampled in Spa si y will be lowe han in he p e ious
one, inc easing he p obabili y o ge ing spa se app oxima ions wi h less edges han Γ.
I , on he con a y, |E(Γ′)|<|E(Γ)|, we eco e he ne wo k Γ′′ sol ing P oblem 3.1.2
wi h se o edges E(Γ′), ha is, we compu e [Γ′′, ms′′] = ne wo k eco e y(E(Γ′),u,s).
Then, we check i ms′′ ≤ ol. I his is he case, we eplace he cu en ne wo k Γ by his
new Γ′′ and we inish he i e a ion, using he new ne wo k as inpu o Spa si y in he nex
i e a ion, epea ing he p ocess, in o de o look o ne wo ks wi h less edges han i . I , on
he opposi e case, ms′′ > ol, his means we ha e emo ed edges ha a e necessa y o he
ne wo k o co ec ly i he da a in he spa si ica ion p ocess, because he e a e no ne wo ks
wi h se o edges con ained in E(Γ′) whose ms is lowe o equal han ol. We ejec he
ne wo k Γ′′, we dec ease he alue o εdi iding i by ψand we inish he i e a ion because,
om heo ems 3.4.1 and 3.4.4, we know ha dec easing he alue o εassu es ha he ms
on any subsequen ε-app oxima ion o Γ will ha e a smalle uppe bound.
I is possible o de ine di e en s opping c i e ia o Algo i hm 2, such as he o al unning
ime i we a e in e es ed on he bes ne wo k ha he algo i hm can ind in ha pe iod, o
a maximum numbe o consecu i e i e a ions in which he ne wo k has no changed. In he
case o dis ibu ion ne wo ks, i is usual ha he posi ion o he swi ches is se so ha he
ne wo k opology is a ee, so in his case, eaching a ee opology can be ano he s opping
c i e ion. A de ailed discussion abou he s opping c i e ia is le o u u e wo k.
3.6 Expe imen al esul s and discussion
Las ly, we p esen some esul s o he applica ion o Algo i hm 2 o sol e examples o P oblem
3.2.1. This sec ion is a e iew o [88, Sec ion 5]. The algo i hm has been w i en in MATLAB
using Casadi [101], an open-sou ce so wa e ool ha p o ides a symbolic amewo k sui ed
o nume ical op imiza ion, and he in e io -poin sol e IPOPT [102], an open-sou ce so -
wa e package o la ge-scale nonlinea op imiza ion, o he ne wo k eco e y p ocess. The
ole ance used in IPOPT is equal o 10−8. In all he examples, we use ψ= 1.5 as inpu o
Algo i hm 2.
In each example, we ha e chosen a ne wo k Γ and we ha e sampled a da a pai (u,s)
consis ing in m= 1000 pai s o ol age and powe injec ed a Γ. Each pai (uj, sj) has
been compu ed nume ically sol ing he powe low equa ions o Γ, sj=ujL(uj), along wi h
90 Conclusions
Chap e 2 was dedica ed o s udying o he in e se conduc ance p oblem on a DC ne -
wo k. This p oblem consis s in eco e ing he conduc ance o a ne wo k om i s Di ichle -
o-Neumann map, and i is ill-posed. In pa icula , we ha e e iewed and ex ended he
esul s om [38] and [37]. In [38] he au ho s p oposed P oblem 2.3.1 as a e o mula ion
o he in e se conduc ance p oblem. We ha e seen ha P oblem 2.3.1 is a polynomial op-
imiza ion p oblem wi h a egula iza ion e m. This e m penalizes de ia ions wi h espec
o he conduc ance being piecewise cons an on a pa i ion o he edge se known a p io i.
We ha e p esen ed nume ous expe imen al examples ha sugges ha when he conduc-
ance is uly piecewise cons an on he conside ed pa i ion, he Lipschi z s abili y cons an
o he p oblem g ows exponen ially wi h he numbe o subse s in he pa i ion. In pa icu-
la , when he numbe o subse s is small ela i e o he o al numbe o edges, we ha e been
able o sol e he in e se conduc ance p oblem wi h s abili y, o di e en pa i ions and sizes
o he ne wo k.
We ha e also discussed an example om [37] o esolu ion o he in e se conduc ance
p oblem using he o mula ion o P oblem 2.3.1 wi h a pa i ion such ha he ac ual con-
duc ance is no piecewise cons an on i . In his example, he esolu ion o P oblem 2.3.1
wi h a ce ain posi i e alue o he penal y pa ame e yields be e esul s han en o cing
he eco e ed conduc ance o be piecewise cons an on he pa i ion o sol ing he p oblem
wi hou any egula iza ion. This suppo s ou penal y o mula ion o P oblem 2.3.1 and he
applicabili y o his app oach o sol e eal-wo ld p oblems, in which i is expec ed ha he
ac ual conduc ance is no exac ly piecewise cons an on he known pa i ion. We ha e also
explained how we can look o a gua an ee ha a minimum o his op imiza ion p oblem
ob ained wi h a nume ical me hod is a global minimum using echniques o Sum o Squa es
(SOS) decomposi ions o polynomials, (see [37]).
We hink ha ou app oach o e o mula ion o sol e he in e se conduc ance p oblem
is p omising, conside ing he esul s p esen ed in his hesis. In pa icula , i would be
in e es ing o sol e he in e se conduc ance p oblem wi h his app oach as pa o a p ocess
o ge a nume ical solu ion o Calde ´on’s p oblem. Cu en ly, he use o spide ne wo ks
in applica ions o Calde ´on’s p oblem o nonin asi e medical imaging is ypically es ic ed
o ne wo ks wi h ewe han 16 nodes on he bounda y. As we ha e seen ha ou me hod
emains s able when he size o he ne wo k inc eases, ou me hod would enable he use o
la ge ne wo ks, hus imp o ing he nume ical esul s.
We belie e ha i would also be in e es ing o sol e P oblem 2.3.1 o o he ne wo k
opologies o which we know ha he in e se conduc ance p oblem has a unique solu ion,
such as o c i ical plana g aphs di e en om he spide g aphs. Also, i would be in e es -
ing o ca y ou expe imen s wi h a supe compu e applying he men ioned SOS echniques
o la ge ne wo ks. I , in an expe imen , a nume ical me hod p o ides a minimum o P ob-
lem 2.3.1, bu SOS echniques do no gua an ee i is a global minimum, hen we could look
o ano he minimum o P oblem 2.3.1 by using he nume ical me hod wi h ano he ini ial
guess, o by using a di e en nume ical me hod.
Chap e 3 has been de o ed o ex end and e iew he esul s om [88]. The aim o
he chap e was o s udy he in e se p oblem o simul aneously eco e ing he admi ance
and opology o an AC o DC ne wo k om a se o measu emen s o ol age and i s co e-
sponding powe injec ed a all e ices. Ne e heless, as we ha e discussed, his p oblem is
Conclusions 91
ill-posed, and hus we usually ge a solu ion wi h a la ge se o edges, which is no e icien
o applica ions. The e o e, P oblem 3.2.1 was p oposed as a e o mula ion. The goal o his
e o mula ed in e se p oblem is o eco e a spa se ne wo k such ha he i ing e o o
he da a is below a ixed ole ance. A solu ion o his p oblem would be desi able om an
applied poin o iew because i would allow he e icien and accu a e esolu ion o usual
p oblems in elec ical ne wo ks.
Mo i a ed by ou men ioned no el physical insigh s on Algo i hm 1, we ha e s udied i s
applica ion o sol e P oblem 3.2.1. We ha e seen ha gi en ε > 0 and a ne wo k Γ = (V, c),
his algo i hm gene a es a ne wo k Γ′= (V, c′) by emo ing edges om Γ, and he e is a
ce ain p obabili y ha Γ′is an ε-app oxima ion o Γ, (see De ini ion 3.3.1). Then, we ha e
p o ed o iginal heo e ical esul s (see Theo ems 3.4.1 and 3.4.4) ha gi e an uppe bound
on he i ing e o o any ε-app oxima ion a ne wo k.
La e , we ha e p oposed Algo i hm 2 o ob ain a solu ion o P oblem 3.2.1, which is
based on Theo ems 3.4.1 and 3.4.4. This algo i hm consis s in an i e a i e p ocedu e o
sol ing a con ex p oblem and applying Algo i hm 1. We p esen ed di e se expe imen al
esul s, which sugges ha Algo i hm 2 is p omising o e icien ly sol ing he p oblem. In
all expe imen s, a e jus a ew i e a ions, we eco e ed a ne wo k ha was ei he he eal
one, elec ically equi alen o he eal one unde he condi ions sa is ied by he da a se , o
a spa se app oxima ion o he eal ne wo k.
The e o e, we belie e i would be in e es ing o u he s udy Algo i hm 2 in he u u e.
One line o esea ch cu en ly in p og ess is he s udy o s opping c i e ia o i . Ano he
p omising di ec ion o u u e esea ch is explo ing he applica ion o al e na i e g aph spa -
si ica ion p ocedu es o emo e edges in he algo i hm.
To conclude, he disc e e ec o calculus on ne wo ks de eloped in his hesis has p o ided
us he ools and de ini ions necessa y o o mula e and achie e signi ican ad ances in in e se
p oblems on ne wo ks. In pa icula , we ha e p oposed a s able e o mula ion o he in e se
conduc ance p oblem and we ha e in oduced an algo i hm o sol e P oblem 3.2.1, based on
o iginal heo e ical esul s.
Bibliog aphy
[1] Abdulla, U.G., Buksh yno , V., Sei , S., 2021. Cance de ec ion h ough elec ical
impedance omog aphy and op imal con ol heo y: heo e ical and compu a ional
analysis. Ma h. Biosci. Eng. 18, 4834–4859.
[2] Abu , A., G´omez, A., 2004. Powe Sys em S a e Es ima ion: Theo y and Implemen-
a ion. Ma cel Dekke , Inc.
[3] Adams, R.A., Fou nie , J., 2003. Sobole spaces. olume 140 o Pu e and Applied
Ma hema ics (Ams e dam). Second ed., Else ie /Academic P ess, Ams e dam.
[4] Adle , A., Holde , D., 2022. Elec ical Impedance Tomog aphy: Me hods, His o y and
Applica ions. Second ed., CRC P ess.
[5] Alessand ini, G., 1988. S able de e mina ion o conduc i i y by bounda y measu e-
men s. Appl. Anal. 27, 153–172.
[6] Alessand ini, G., Vessella, S., 2005. Lipschi z s abili y o he in e se conduc i i y
p oblem. Ad . Appl. Ma h. 35, 207–241.
[7] A a´uz, C., 2014. The in e se p oblem on ini e ne wo ks. PhD Thesis, UPC.
[8] A a´uz, C., Ca mona, ´
A., Encinas, A.M., 2015a. Di ichle - o-Robin maps on ini e
ne wo ks. Appl. Anal. Disc e e Ma h. 9, 85–102.
[9] A a´uz, C., Ca mona, ´
A., Encinas, A.M., 2015b. Disc e e Se in’s p oblem. Linea
Algeb a Appl. 468, 107–121.
[10] A a´uz, C., Ca mona, ´
A., Encinas, A.M., 2015c. O e de e mined pa ial bounda y
alue p oblems on ini e ne wo ks. J. Ma h. Anal. Appl. 423, 191–207.
[11] A a´uz, C., Ca mona, ´
A., Encinas, A.M., Mi jana, M., 2016. Reco e ing he conduc-
ances on g ids: a heo e ical jus i ica ion, in: A pano ama o ma hema ics: pu e
and applied. Ame . Ma h. Soc., P o idence, RI. olume 658 o Con emp. Ma h., pp.
149–166.
[12] As ala, K., P¨ai ¨a in a, L., 2006a. A bounda y in eg al equa ion o Calde ´on’s in e se
conduc i i y p oblem. Collec . Ma h. (2006) 57, 127–139.
[13] As ala, K., P¨ai ¨a in a, L., 2006b. Calde ´on’s in e se conduc i i y p oblem in he
plane. Ann. Ma h. 163, 265–299.
Bibliog aphy 93
[14] Ba cel´o, J.A., Ba cel´o, T., Ruiz, A., 2001a. S abili y o he in e se conduc i i y p ob-
lem in he plane o less egula conduc i i ies. J.Di e en ial Equa ions 173, 231–270.
[15] Ba cel´o, J.A., Ba cel´o, T., Ruiz, A., 2001b. Unicidad y es abilidad pa a el p ob-
lema de conduc i idad in e so, in: Ma ga i a Ma em´a ica en Memo ia de Jos´e Ja ie
Guadalupe Hen´andez, Se icio de Publicaciones de la Uni e sidad de La Rioja,
Log o˜no, Spain. pp. 401–413.
[16] Ba son, J., Spielman, D., S i as a a, N., Teng, S., 2013. Spec al Spa si ica ion o
G aphs: Theo y and Algo i hms. Commun. ACM 56, 87–94.
[17] Bendi o, E., Ca mona, ´
A., Encinas, A.M., 2000. Sol ing bounda y alue p oblems on
ne wo ks using equilib ium measu es. J. Func . Anal. 171, 155–176.
[18] Bendi o, E., Ca mona, ´
A., Encinas, A.M., 2004. Di e ence schemes on uni o m g ids
pe o med by gene al disc e e ope a o s. Appl. Num. Ma h. 50, 343–370.
[19] Bendi o, E., Ca mona, ´
A., Encinas, A.M., 2005. Po en ial heo y o Sch ¨odinge
ope a o s on ini e ne wo ks. Re . Ma . Ibe oame icana 21, 771–818.
[20] Bendi o, E., Ca mona, ´
A., Encinas, A.M., 2008. Bounda y alue p oblems on weigh ed
ne wo ks. Disc e e Appl. Ma h. 156, 3443–3463.
[21] Benning, M., Bu ge , M., 2018. Mode n egula iza ion me hods o in e se p oblems.
Ac a Nume . 27, 1–111.
[22] Bensoussan, A., Menaldi, J., 2005. Di e ence equa ions on weigh ed g aphs,. J. Con ex
Anal. 12, 13–44.
[23] Bo cea, L., D uskin, V., Gue a a, F., 2008. Elec ical Impedance Tomog aphy wi h
esis o ne wo ks. In e se P oblems 24, 035013.
[24] Bo cea, L., D uskin, V., Gue a a, F., Mamono , A., 2011. Resis o ne wo k app oaches
o elec ical impedance omog aphy, in: In e se p oblems and applica ions: inside ou .
II (G. Uhlmann ed.). Camb idge Uni . P ess, Camb idge. olume 60 o Ma h. Sci. Res.
Ins . Publ., pp. 55–118.
[25] Bo cea, L., D uskin, V., Knizhne man, L., 2005. On he con inuum limi o a disc e e
in e se spec al p oblem on op imal ini e di e ence g ids. Comm. Pu e Appl. Ma h.
58, 1231–1279.
[26] Bo cea, L., D uskin, V., Mamono , A.V., 2010. Ci cula esis o ne wo ks o elec ical
impedance omog aphy wi h pa ial bounda y measu emen s. In e se P oblems 26,
045010.
[27] Bo cea, L., Gue a a, F., Mamono , A.V., 2013. S udy o noise e ec s in elec ical
impedance omog aphy wi h esis o ne wo ks. In e se P obl. Imaging 7, 417–443.
[28] Bo cea, L., Gue a a, F., Mamono , A.V., 2017. A disc e e Liou ille iden i y o nu-
me ical econs uc ion o Sch ¨odinge po en ials. In e se P obl. Imaging 11, 623–641.
94 Bibliog aphy
[29] Bo u a, R., Babazadeh, D., Zhu, K., Bo ghe i, A., No ds ¨om, L., Nucci, C.A., 2013.
Si l and hla co-simula ion pla o ms: Tools o analysis o he in eg a ed ic and elec ic
powe sys em, in: Eu ocon 2013, IEEE. pp. 918–925.
[30] Boye , J., Ga zella, J.J., Gue a a-Vasquez, F., 2016. On he sol abili y o he disc e e
conduc i i y and Sch ¨odinge in e se p oblems. SIAM J. Appl. Ma h. 76, 1053–1075.
[31] B ezis, H., 2011. Func ional analysis, Sobole spaces and pa ial di e en ial equa ions.
Uni e si ex , Sp inge , New Yo k.
[32] B own, R.M., Uhlmann, G.A., 1997. Uniqueness in he in e se conduc i i y p oblem
o nonsmoo h conduc i i ies in wo dimensions. Comm. Pa ial Di e en ial Equa ions
22, 1009–1027.
[33] Bunge, A., Bo sch, M., 2023. A Su ey on Disc e e Laplacians o Gene al Polygonal
Meshes. Compu . G aph. Fo um 42, 521–544.
[34] Calde ´on, A.P., 2006. On an in e se bounda y alue p oblem. Compu . Appl. Ma h.
25, 133–138. (Rep in o he o iginal wo k in Semina on Nume ical Analysis and i s
Applica ions o Con inuum Physics, Soc. B asil. Ma . Rio de Janei o 65-73, 1980.).
[35] Ca mona, ´
A., 2018. Bounda y alue p oblems on ini e ne wo ks, in: Combina o ial
Ma ix Theo y (Encinas A.M. and Mi jana, M. eds.). Bi kh¨ause /Sp inge , Cham.
Ad anced Cou ses in Ma hema ics. CRM Ba celona, pp. 173–217.
[36] Ca mona, ´
A., Encinas, A.M., 2024. Disc e e ope a o s on g aphs and ne wo ks, in:
In e se P oblems, Regula iza ion Me hods and Rela ed Topics. A Volume in Honou o
Thamban Nai (Pe e e zye , S.V. and Radha, R. and S. Sampa h, S. eds.). Sp inge .
Indus ial and Applied Ma hema ics, o appea .
[37] Ca mona, ´
A., Encinas, A.M., Jim´enez, M.J., Sampe io, ´
A., 2024a. S able and op imal
conduc ance eco e y on ne wo ks. Submi ed .
[38] Ca mona, ´
A., Encinas, A.M., Jim´enez, M.J., Sampe io, ´
A., 2024b. S able eco e y o
piecewise cons an conduc ance on spide ne wo ks. In . J. Compu . Ma h. , 1–18.
[39] Ca o, P., Ga c´ıa-Fe e o, M.´
A., Roge s, K.M., 2024. Recons uc ion o he Calde ´on
p oblem wi h Lipschi z conduc i i ies. A Xi p ep in : 2401.06120 1 .
[40] Ca o, P., Roge s, K.M., 2016. Global uniqueness o he Calde ´on p oblem wi h Lips-
chi z conduc i i ies. Fo um Ma h., Pi 4, 20 pages.
[41] Chan, M., Tae, J., Jeongchan, N., Hyeuknam, K., Kiwan, J., Kyounghun, L., 2023.
Machine lea ning-based signal quali y assessmen o ca diac olume moni o ing in
elec ical impedance omog aphy. Mach. Lea n.: Sci. Technol. 4, 015034.
[42] Cheney, M., Isaacson, D., Newell, J.C., 1999. Elec ical impedance omog aphy. SIAM
Re . 41, 85–101.
[43] Chou, H., Maly, J., Ve dun, C., 2022. Non-nega i e Leas Squa es ia O e -
pa ame iza ion. a Xi p ep in : 2207.08437 .
Bibliog aphy 95
[44] Chung, F., 1997. Spec al G aph Theo y. olume 92 o CBMS Regional Con . Se . in
Ma h. Ame ican Ma hema ical Socie y, P o idence, RI,.
[45] Chung, F., Gilbe , A., Hoskins, J., Scho land, J., 2017. Op ical omog aphy on g aphs.
In e se P oblems 33, 055016, 21.
[46] Chung, F., Yau, S.T., 2000. Disc e e G een’s Func ions. J. Combin. Theo y Se . A
91, 191–214.
[47] Chung, S., Be ens ein, C., 2005. ω-ha monic unc ions and in e se conduc i i y p ob-
lems on ne wo ks. SIAM J. Appl. Ma h. 65, 1200–1226.
[48] Colin de Ve di`e e, Y., 1994. R´eseaux ´elec ique planai es i. Commen a ii Ma hema ici
Hel e ici 69, 351–374.
[49] Conway, J.B., 2007. A Cou se in Func ional Analysis. olume 96 o G adua e Tex s in
Ma hema ics. Sp inge New Yo k, NY.
[50] C ab ee, D.E., Haynswo h, E.V., 1969. An iden i y o he Schu complemen o a
ma ix. P oc. Am. Ma h. Soc. 22, 364–366.
[51] Cu is, E.B., Inge man, D., Mo ow, J.A., 1998. Ci cula plana g aphs and esis o
ne wo ks. Linea Algeb a Appl. 283, 115–150.
[52] Cu is, E.B., Mo ow, J.A., 1990. De e mining he esis o s in a ne wo k. SIAM J.
Appl. Ma h. 50, 918–930.
[53] Cu is, E.B., Mo ow, J.A., 1991. The Di ichle o Neumann map o a esis o ne wo k.
SIAM J. Appl. Ma h. 51, 1011–1029.
[54] Cu is, E.B., Mo ow, J.A., 2000. In e se p oblems o elec ical ne wo ks. olume 13.
Wo ld Scien i ic.
[55] Cu is, E.B., Mo ow, J.A., Mooe s, E., 1994. Finding he conduc o s in ci cula
ne wo ks om bounda y measu emen s, ai o model. RAIRO Mod´el. Ma h. Anal.
Num´e . 28, 781–814.
[56] D., C., Pa ilo, P., 2017. Sampling algeb aic a ie ies o sum o squa es p og ams.
SIAM J. Op imiz. 27, 2381–2404.
[57] Deka, D., Backhaus, S., Che ko , M., 2015. S uc u e Lea ning in Powe Dis ibu ion
Ne wo ks. IEEE T ans. Con ol Ne w. Sys . 5, 1061–1074.
[58] De iend , K., 2022. E ec i e esis ance is mo e han dis ance: Laplacians, Simplices
and he Schu complemen . Linea Algeb a Appl. 639, 24–49.
[59] Dodziuk, J., 1986. Laplacian on mani olds and analogous di e ence ope a o o g aphs,
in: Complex di e en ial geome y and nonlinea di e en ial equa ions (B unswick,
Maine, 1984). Ame . Ma h. Soc., P o idence, RI. olume 49 o Con emp. Ma h., pp.
45–49.
[60] Do le , F., Bullo, F., 2013. K on educ ion o g aphs wi h applica ions o elec ical
ne wo ks. IEEE T ans. Ci cui s Sys . I. Regul. Pap. 60, 150–163.
96 Bibliog aphy
[61] Engl, H., Hanke, M., Neubaue , A., 1996. Regula iza ion o in e se p oblems. ol-
ume 375 o Ma hema ics and i Applica ions. Kluwe Academic Publishe s G oup,
Do d ech .
[62] E edoza, S., de Gou nay, F., 2011. Uni o m s abili y es ima es o he disc e e
Calde ´on p oblems. In e se p oblems 27, 125012.
[63] F aunho e IEE and Uni e si y o Kassel, a. Pandapowe documen a ion. CIGRE ne -
wo ks. h ps://pandapowe . ead hedocs.io/en/ 2.6.0/ne wo ks/cig e.h ml.
Accessed: 22/07/2024.
[64] F aunho e IEE and Uni e si y o Kassel, b. Pandapowe documen a ion. Ke be Ne -
wo ks. h ps://pandapowe . ead hedocs.io/en/ 2.6.0/ne wo ks/ke be .h ml.
Accessed: 22/07/2024.
[65] Geo ge, T., 2024. The wis o elec ical ne wo ks and he in e se p oblem. In . Ma h.
Res. No ices 8, 1073–7928.
[66] Ge nand , H., Rohlede , J., 2022. A Calde ´on ype in e se p oblem o ee g aphs.
Linea Algeb a Appl. 646, 29–42.
[67] G igo ´yan, A., 2018. In oduc ion o analysis on g aphs. olume 71 o Uni e si y
Lec u e Se ies. Ame ican Ma hema ical Socie y, P o idence, RI.
[68] Hyman, J., Shashko , M., 1997. Adjoin ope a o s o he na u al disc e iza ions o
he di e gence, g adien and cu l on logically ec angula g ids. Appl. Nume . Ma h.
25, 413–442.
[69] Hyman, J., Shashko , M., S einbe g, S., 2001. The e ec o inne p oduc s o disc e e
ec o ields on he accu acy o mime ic ini e di e ence me hods. Compu . Ma h.
Appl. 42, 1527–1547.
[70] Kayano, T., Yamasaki, M., 1988/89. Disc e e Di ichle in eg al o mula. Disc e e
Appl. Ma h. 22, 53–68.
[71] Kenyon, R., Wilson, D., 2017. The space o ci cula plana elec ical ne wo ks. SIAM
J. Disc e e Ma h. 31, 1–28.
[72] Khan, A., Chak aba i, S., Sha ma, A., Alam, M., 2019. Pa ame e and Topology
Es ima ion o Elec ical Powe Dis ibu ion Sys em, in: 2019 8 h In e na ional Con-
e ence on Powe Sys ems (ICPS), pp. 1–5.
[73] Lasse e, J., 2010. Momen s, posi i e polynomials and hei applica ions. olume 1 o
Impe ial College P ess Op imiza ion Se ies. Impe ial College P ess, London.
[74] Lim, L.H., 2020. Hodge Laplacians on g aphs. SIAM Re . 62, 685–715.
[75] Liu, L., 1997. S abili y es ima es o he wo-dimensional in e se conduc i i y p oblem.
PhD Thesis, Uni e si y o Roches e , New Yo k.
[76] Lukaschewi sch, M., Maass, P., Pidcock, M., 2003. Tikhono egula iza ion o elec-
ical impedance omog aphy on unbounded domains. In e se P oblems 19, 585–610.
Bibliog aphy 97
[77] Mandache, N., 2001. Exponen ial ins abili y in an in e se p oblem o he Sch ¨odinge
equa ion. In e se P oblems 17, 1435–1444.
[78] Mil on, G.W., Seppeche , P., 2008. Realizable esponse ma ices o mul i- e minal
elec ical, acous ic and elas odynamic ne wo ks a a gi en equency. P oc. R. Soc. A.
464, 967–986.
[79] Mon es, A., Cas o, J., 1995. Sol ing he load low p oblem using G ¨obne basis. ACM
SIGSAM Bulle in 29, 1–13.
[80] Papach is odoulou, A., Ande son, J., Valmo bida, G., P ajna, S., Seile , P., Pa ilo,
P., Pee , M., Jag , D., 2021. SOSTOOLS Ve sion 4.00 Sum o Squa es Op imiza ion
Toolbox o MATLAB. A Xi p ep in : 1310.4716 .
[81] Pa ilo, P., 2005. Exploi ing Algeb aic S uc u e in Sum o Squa es P og ams. Sp inge ,
Be lin, Heidelbe g. pp. 181–194.
[82] Pu ensen, C., Hen ze, B., Muens e , S., Mude s, T., 2019. Elec ical impedance o-
mog aphy o ca dio-pulmona y moni o ing. J. Clin. Med. 8, 1176.
[83] Ramon, S., Pu ina , M., 2007. Complex symme ic ope a o s and applica ions II.
T ans. Ame . Ma h. Soc. 359, 3913–3931.
[84] Ribando-G os, E., Wang, R., Chen, J., Tong, Y., Wei, G.W., 2024. Combina o ial and
Hodge Laplacians: Simila i ies and di e ences. SIAM Re . 66, 575–601.
[85] Rondi, L., 2006. A ema k on a pape by Alessand ini and Vessella. Ad . Appl. Ma h.
36, 67–69.
[86] Rondi, L., 2016. Disc e e app oxima ion and egula isa ion o he in e se conduc i i y
p oblem. Rend. Is i . Ma . Uni . T ies e 48, 315–352.
[87] Ro e, G., 2020. Cha ac e iza ion o he esponse maps o al e na ing-cu en ne wo ks.
Elec on. J. Linea Algeb a 36, 698–703.
[88] Sampe io, ´
A., 2023. Spa se eco e y o an elec ical ne wo k. A Xi p ep in :
2304.06676 .
[89] Sa ode, V., Pa ka , S., Chee an, A.N., 2013. Compa ison o 2-d algo i hms in ei based
image econs uc ion. In . J. Compu . Appl. 69, 6–11.
[90] Shashko , M., 1996. Conse a i e ini e-di e ence me hods on gene al g ids. Symbolic
and Nume ic Compu a ion Se ies, CRC P ess, Boca Ra on, FL.
[91] Shi, Y., Yang, Z., Xie, F., Ren, S., Xu, S., 2021. The esea ch p og ess o elec ical
impedance omog aphy o lung moni o ing. F on . Bioeng. Bio echnol. 9, 726652.
[92] Slawski, M., Hein, M., 2013. Non-nega i e leas squa es o high-dimensional linea
models: Consis ency and spa se eco e y wi hou egula iza ion. Elec on. J. S a is .
7, 3004–3056.
[93] Spielman, D., 2017. G aphs, Vec o s and Ma ices. Bull. Ame . Ma h. Soc. (N.S.) 54,
45–61.
98 Bibliog aphy
[94] Spielman, D., S i as a a, N., 2011. G aph Spa si ica ion by E ec i e Resis ances.
SIAM J. Compu . 40, 1913–1926.
[95] Spielman, D., Teng, S.H., 2011. Spec al Spa si ica ion o G aphs. SIAM J. Compu .
40, 981–1025.
[96] S agg, G., El-Abiad, A., 1968. Compu e Me hods in Powe Sys em Analysis. McG aw-
Hill se ies in elec onic sys ems, McG aw-Hill.
[97] Syl es e , J., Uhlmann, G., 1987. A global uniqueness heo em o an in e se bounda y
alue p oblem. Ann. Ma h. , 153–169.
[98] Uhlmann, G., 1998. In e se bounda y alue p oblems o pa ial di e en ial equa ions,
in: P oceedings o he In e na ional Cong ess o Ma hema icians, Vol. III (Be lin,
1998), pp. 77–86.
[99] Wadhwa, C.L., 2012. Elec ical Powe Sys ems. New Academic Science Limi ed.
[100] Webpage, 2019. Calculus on ini e weigh ed g aphs. URL: h ps://en.wikipedia.
o g/wiki/Calculus_on_ ini e_weigh ed_g aphs.
[101] Webpage, 2024a. Casadi. URL: h ps://web.casadi.o g/.
[102] Webpage, 2024b. Ipop documen a ion. URL: h ps://coin-o .gi hub.io/Ipop /.
[103] Webpage, 2024c. Sedumi. URL: h ps://sedumi.ie.lehigh.edu/.
[104] Zhang, T., Jang, G.Y., Oh, T.I., Jeung, K.W., Wi, H., Woo, E.J., 2020. Sou ce
consis ency elec ical impedance omog aphy. SIAM J. Appl. Ma h. 80, 499–520.
