Learning Inhibition Graphs Through Boolean Compressive Sensing

Design of efficient sampling methodologies to capture the information content in sparse, and thus, "compressible" signals is well known as compressive sensing (CS) in the signal processing community. These efficient sampling methods that use linear measurements (tests) of signals are known to have significantly low sampling cost compared to naive sampling. An analogous, albeit a non-linear paradigm, called group testing emerged much before the compressive sensing era. Boolean Compressive Sensing (BCS) a.k.a Group Testing was introduced by Dorfman in 1943 to identify a small number of unhealthy individuals (i.e., defective "items") amidst a large population. In the BCS model, the test outcomes are a non-linear function of the input, and the input and the output vectors are binary. The addition and multiplication operations in CS are replaced by Boolean-OR and Boolean-AND operations. The BCS framework has since been used in diverse fields like Bioinformatics, Theoretical Computer Science, Computer Networks, Sports Analytics, and Recreational Mathematics.

This talk will focus on a newly introduced variation of the classical BCS framework that will model a unified problem of pathogen identification and drug discovery. The expression of a pathogen carrying item is inhibited by blocker items in a "pooled" test. Such an activity relationship between the items is modelled as a bipartite graph, called an inhibition graph. The goal is to learn this unknown inhibition graph with least sampling complexity. Upper bounds on the sampling complexity and tight non-trivial lower bounds will be discussed for learning the inhibition graph through "non-adaptive" BCS.

The talk will also highlight a few other topics that I have worked on and my future research plans.

Biography: Abhinav Ganesan is a Senior Systems Engineer at Qualcomm R&D, Bangalore, working on LTE system design for IoT applications. He was a Post Doctoral Fellow at the Institute of Network Coding, The Chinese University of Hong Kong, during 2014-2015. He obtained his PhD from the ECE Department at the Indian Institute of Science in 2014 and his B.E. degree from the College of Engineering, Guindy, Anna University in 2009. He was a recipient of the Best Academic Paper Award at the IEEE Wireless Communications and Networking Conference (WCNC) in 2011.