Won Hwa Kim

Adaptive Signal Recovery on Graphs via Harmonic Analysis


Consider an experimental design of a neuroimaging study, where we need to obtain p measurements for each participant in a setting where p'(< p) are cheaper and easier to acquire while the remaining (p−p') are expensive. For example, the p measurements may include demographics, cognitive scores or routinely offered imaging scans while the (p−p') measurements may correspond to more expensive types of brain image scans with a higher participant burden. In this scenario, it seems reasonable to seek an “adaptive” design for data acquisition so as to minimize the cost of the study without compromising statistical power. We show how this problem can be solved via harmonic analysis of a band-limited graph whose vertices correspond to participants and our goal is to fully recover a multi-variate signal on the nodes, given the full set of cheaper features and a partial set of more expensive measurements. This is accomplished using an adaptive query strategy derived from probing the properties of the graph in the frequency space. To demonstrate the benefits that this framework can provide, we present experimental evaluations on two independent neuroimaging studies and show that our proposed method can reliably recover the true signal with only partial observations directly yielding substantial financial savings.

Fig. A toy example of our framework on a cat mesh (N = 3400). a) Band-limited random signal in [0, 1] with noise on the cat mesh, b) Sampling probability p 1 derived from (3) , c) Sampled signal at m = 340 locations out of 3400, d) Recovered signal using our method with k = 50. Note that our recovery is estimating only 50 parameters instead of N = 3400.

Experimental Results on WRAP Study

Predict whether a participant is amyloid elevated (PiB > 1.18) by recovering PiB-PET measurements on the 79 participants using CSF and PiB measurements from m < 79 participants.

  • Wisconsin Registry for Alzheimer's Prevention (WRAP) Dataset: 79 participants with both Cerebrospinal fluid (CSF) measures and PiB-PET images.
  • Fig. Sorted PiB measures and our estimation results with 10, 30, 60% sampling ratios. Sampled nodes (blue circle), estimation on the sampled nodes (blue asterisk), unsampled nodes (red circle), estimation on the unsampled (red asterisk).


    This research was supported by NIH R01AG040396, NSF CAREER Award RI1252725, UW ADRC AG033514, UW ICTR 1UL1RR025011, UW CPCP AI117924 and Waisman Core Grant P30 HD003352-45.


    1. Won Hwa Kim, Seong Jae Hwang, Nagesh Adluru, Sterling C. Johnson, Vikas Singh, "Adaptive Signal Recovery on Graphs via Harmonic Analysis forExperimental Design in Neuroimaging", European Conference on Computer Vision(ECCV), 2016.