Location Estimates from Channel State Information Via Binary Programming

Recent years have witnessed a marked increase in the efficacy and speed to solution of binary program solvers. Leveraging these developments, we propose converting the sparse modelling problem to a binary program, and we derive the conditions under which such a conversion yields the optimal signal support. Furthermore, we derive an upper bound on this condition, which we can minimize by designing a structured tight frame as the dictionary. We apply these theoretical insights to binary optimization of angle of arrival and time of flight estimation (BOAT) using channel state information (CSI), with the goal of localizing a transmitter in an indoor multipath-rich environment. Finally, we show how a covariance array processing approach, together with the novel binary programming paradigm, results in a system that outperforms two state-of-the-art solutions. Our claims are substantiated using both simulated data and experimental data collected using “off-the-shelf” WiFi IEEE 802.11ac routers.