Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 2019 | Submitted
Book Section - Chapter Open

Learning Graph Parameters from Linear Measurements: Fundamental Trade-offs and Application to Electric Grids


We consider a specific graph learning task: reconstructing a symmetric matrix that represents an underlying graph using linear measurements. We study fundamental trade-offs between the number of measurements (sample complexity), the complexity of the graph class, and the probability of error by first deriving a necessary condition (fundamental limit) on the number of measurements. Then, by considering a two-stage recovery scheme, we give a sufficient condition for recovery. In the special cases of the uniform distribution on trees with n nodes and the Erdös-Rényi (n, p) class, the sample complexity derived from the fundamental trade-offs is tight up to multiplicative factors. In addition, we design and implement a polynomial-time (in n) algorithm based on the two-stage recovery scheme. Simulations for several canonical graph classes and IEEE power system test cases demonstrate the effectiveness of the proposed algorithm for accurate topology and parameter recovery.

Additional Information

© 2019 IEEE.

Attached Files

Submitted - 1909.05487.pdf


Files (1.4 MB)
Name Size Download all
1.4 MB Preview Download

Additional details

August 19, 2023
October 20, 2023