Structure-based learning in wireless networks via sparse approximation

A novel framework for the online learning of expected cost-to-go functions characterizing wireless networks performance is proposed. The framework is based on the observation that wireless protocols induce structured and correlated behavior of the finite state machine (FSM) modeling the operations of the network. As a result, a significant dimension reduction can be achieved by projecting the cost-to-go function on a graph wavelet basis set capturing typical sub-structures in the graph associated with the FSM. Sparse approximation with random projection is then used to identify a concise set of coefficients representing the cost-to-go function in the wavelet domain. This Compressed Sensing (CS) approach enables a considerable reduction in the number of observations needed to achieve an accurate estimate of the cost-to-go function. The proposed method is characterized via stability analysis. In particular, we prove that the standard CS approach of the Least Angle Selection and Shrinkage Operator (LASSO) will not provide stability. We also determine a connection between the structure of the FSM induced by the wireless protocols and the restricted isometry property of the effective projection matrix. Simulation results of our approximation method show that 15 wavelet functions can accurately represent a cost-to-go function defined on a state space of 2000 states. Moreover, the number of state-cost observations needed to estimate the cost-to-go function is orders of magnitude smaller than that required by traditional online learning techniques.