Block Simplex Signal Recovery: Methods, Trade-Offs, and an Application to Routing

This paper presents the problem of block simplex constrained signal recovery, which has been demonstrated to be a suitable formulation for estimation problems in networks such as route flow estimation in traffic. There are several natural approaches to this problem: compressed sensing, Bayesian inference, and convex optimization. This paper presents new methods within each framework and assesses their respective abilities to reconstruct signals, with the particular emphasis on sparse recovery, ability to incorporate prior information, and scalability. We then apply these methods to route flow estimation in traffic networks of various sizes and network topologies. We find that both compressed sensing and Bayesian inference approaches are appropriate for structured recovery but have scalability limitations. The convex optimization approach does not directly incorporate prior information, but scales well and has been shown to achieve 90% route flow accuracy on a full-scale network of over 10,000 links and 280,000 routes on a synthetic benchmark based on the I-210 corridor near Los Angeles, CA, USA.