Some inverse problems on finite networks

Abstract

We propose a version of the discrete vector calculus for Alternating Current (AC) and Direct Current (DC) networks. From the definition of the tangent space at each vertex of the network, we can define discrete concepts that mimic the continuous differential operators, vector fields or boundary value problems.

This discrete vector calculus provides a framework to explain the relation between potential, current injected and power injected at the vertices of the network. In particular, it allows us to formulate two inverse problems in electrical networks and also to introduce concepts and results that we use to solve them.

The first inverse problem that we study is the inverse conductance problem, which is the discrete version of Calderon’s problem. The inverse conductance problem consists in determining the conductance of a DC network from its Dirichlet-to-Neumann map. This map gives us the linear relationship between the potential and the respective injected current at a subset of vertices of the network under the condition that there is zero injected current at the rest of the vertices.

Despite for several families of networks it is known that this problem has a unique solution and there are algorithms based on explicit formulas to solve it, the problem is severely ill-posed. In order to get a numerically stable recovery of the conductance, we propose to reformulate the inverse conductance problem as a polynomial optimization one, in which we incorporate a regularization term that penalizes the deviation respect to an a priori known hypothesis. That hypothesis is that the conductance is piecewise constant on a partition of the edge set with few subsets.

We show several examples in which we recover with stability the conductance of well-connected spider networks with up to 47 boundary vertices following our approach, improving the known methods that show instabilities when the number of boundary vertices is greater than 16. Even in some cases in which the hypothesis is false, i.e., the real conductance is not exactly piecewise constant on the partition, we are able to recover a good approximation to the conductance. We study the variation of the error in the problem with the penalty parameter, and the guarantees that a minimum obtained of the problem is global with techniques of Sum of Squares (SOS) decompositions of polynomials.

The second inverse problem that we study is the simultaneous recovery of the admittance and topology of an AC or DC network from a set of measurements of voltage and its corresponding power injected at all vertices. We show that this problem is also ill-posed. As a consequence, even if the network is sparse, i.e., has few edges, we usually recover a network which has many edges, which is not efficient for applications.

Therefore, we reformulate that inverse problem. We seek to recover a sparse network such that the fitting error to the data is below a fixed tolerance. We propose an algorithm to solve it, which is based on techniques of spectral graph sparsification, and it is based on original results bounding the fitting error of a sparse approximation of a network. We show several experimental results in which we are able to recover a sparse network.

Proponemos una versión del cálculo vectorial discreto para redes de Corriente Alterna (CA) y Corriente Continua (CC). A partir de la definición del espacio tangente en cada vértice de la red, podemos definir conceptos discretos que imitan conceptos continuos tales como operadores diferenciales, campos vectoriales o problemas de valores en la frontera.

Este cálculo vectorial discreto proporciona un marco para explicar la relación entre el potencial, la corriente inyectada y la potencia inyectada en los vértices de la red. En particular, nos permite formular dos problemas inversos en redes eléctricas y también introducir conceptos y resultados que utilizamos para resolverlos.

El primer problema inverso que estudiamos es el problema inverso de conductancia, que es la versión discreta del problema de Calderón. El problema inverso de conductancia consiste en determinar la conductancia de una red de CC a partir de su aplicación Dirichlet-Neumann. Esta aplicación nos da la relación lineal entre el potencial y su respectiva corriente inyectada en un subconjunto de vértices de la red, bajo la condición de que la corriente inyectada sea cero en el resto de los vértices.

A pesar de que para varias familias de redes se sabe que este problema tiene una solución única y existen algoritmos basados en fórmulas explícitas para resolverlo, el problema está severamente mal condicionado. Con el fin de obtener una recuperación numéricamente estable de la conductancia, proponemos reformular el problema inverso de conductancia como uno de optimización polinómica, en el cual incorporamos un término de regularización que penaliza la desviación con respecto a una hipótesis conocida a priori. Esta hipótesis consiste en que la conductancia sea constante en cada uno de los subconjuntos de una partición del conjunto de aristas con pocos subconjuntos.

Mostramos varios ejemplos en los que, siguiendo nuestro enfoque, recuperamos con estabilidad la conductancia de redes “bien-conexas” de tipo "araña” con hasta 47 vértices en la frontera, mejorando los métodos conocidos que muestran inestabilidades cuando el número de vertices en la frontera es mayor a 16. Incluso en algunos casos en los que la hipótesis es falsa, es decir, la conductancia real no es exactamente constante en cada subconjunto de la partición, somos capaces de recuperar una buena aproximación de la conductancia. Estudiamos la variación del error en el problema con el parámetro de penalización y las garantías de que un mínimo obtenido del problema es global, utilizando técnicas de descomposiciones de polinomios en sumas de cuadrados.

El segundo problema inverso que estudiamos es la recuperación simultánea de la admitancia y la topología de una red de CA o CC a partir de un conjunto de mediciones de voltaje y su correspondiente potencia inyectada en todos los vértices. Mostramos que este problema también está mal condicionado. Como consecuencia, incluso si la red es dispersa, es decir, tiene pocas aristas, usualmente recuperamos una red con muchas aristas, lo cual no es eficiente para aplicaciones.

Por lo tanto, reformulamos ese problema inverso. Buscamos recuperar una red dispersa de tal manera que el error de ajuste a los datos esté por debajo de una tolerancia fija. Proponemos un algoritmo para resolverlo, el cual se basa en técnicas de aproximación espectral dispersa de redes y en resultados originales que acotan el error de ajuste de una aproximación dispersa de una red. Mostramos varios resultados experimentales en los que somos capaces de recuperar una red dispersa.