Learning Graphs From Linear Measurements: Fundamental Trade-Offs and Applications

You are here

Top Reasons to Join SPS Today!

1. IEEE Signal Processing Magazine
2. Signal Processing Digital Library*
3. Inside Signal Processing Newsletter
4. SPS Resource Center
5. Career advancement & recognition
6. Discounts on conferences and publications
7. Professional networking
8. Communities for students, young professionals, and women
9. Volunteer opportunities
10. Coming soon! PDH/CEU credits
Click here to learn more.

Learning Graphs From Linear Measurements: Fundamental Trade-Offs and Applications

By: 
Tongxin Li; Lucien Werner; Steven H. Low

We consider a specific graph learning task: reconstructing a symmetric matrix that represents an underlying graph using linear measurements. We present a sparsity characterization for distributions of random graphs (that are allowed to contain high-degree nodes), based on which we study fundamental trade-offs between the number of measurements, the complexity of the graph class, and the probability of error. We first derive a necessary condition on the number of measurements. Then, by considering a three-stage recovery scheme, we give a sufficient condition for recovery. Furthermore, assuming the measurements are Gaussian IID, we prove upper and lower bounds on the (worst-case) sample complexity for both noisy and noiseless recovery. In the special cases of the uniform distribution on trees with n nodes and the Erdős-Rényi (n,p) class, the fundamental trade-offs are tight up to multiplicative factors with noiseless measurements. In addition, for practical applications, we design and implement a polynomial-time (in n ) algorithm based on the three-stage recovery scheme. Experiments show that the heuristic algorithm outperforms basis pursuit on star graphs. We apply the heuristic algorithm to learn admittance matrices in electric grids. Simulations for several canonical graph classes and IEEE power system test cases demonstrate the effectiveness and robustness of the proposed algorithm for parameter reconstruction.

SPS on Twitter

  • The Brain Space Initiative Talk Series continues on Friday, 31 March when Dr. Dean Salisbury presents "From searchi… https://t.co/jvnsJ6jX7K
  • On 26 April, join Dr. Preeti Kumari, Dr. Nitin Jonathan Myers, and Dr. Robert W. Heath Jr. for a new SPS Webinar, "… https://t.co/x5Mm6Djvmz
  • We have several 75th anniversary activities in store for - join SPS leaders in conversation about the p… https://t.co/nsPV0a5RW5
  • Join us on 7 April 2023 when Dr. Chao Zuo presents "Lens-Free On-Chip Digital Holographic Microscopy: Resolution An… https://t.co/Bklm6qy6zp
  • Join Dr. Pan Gao and Dr. Aljosa Smolic for a new SPS Webinar on 12 April! Register for "Quality Assessment for Omni… https://t.co/WoYqv1oJq1

SPS Videos


Signal Processing in Home Assistants

 


Multimedia Forensics


Careers in Signal Processing             

 


Under the Radar