SPARSE RECOVERY OF TIME-VARING STREAMING DATA USING HOMOTOPY METHOD

Open Access
Author:
Wang, Xue
Graduate Program:
Industrial Engineering
Degree:
Master of Science
Document Type:
Master Thesis
Date of Defense:
None
Committee Members:
  • Tao Yao, Thesis Advisor
Keywords:
  • sparse recovery
  • regularation
  • online updating
  • homotopy
Abstract:
Many existing algorithms for regularized least square regression assumes that the true parameters to be stable and not change with time. However, the algorithm and framework for recovering time-varying signal with online updating is not well researched. Some people proposed the kind of homotopy l1≠ minimization methods for dealing with online updating data, which has been shown to work well, but there are also some limitations: (1) the result of l1- minimization method is biased; (2) the homotopy algorithm has been proved to be a kind of exponential method. In some special cases, the homotopy l1- minimization method may work bad. In this thesis, we constructs a novel homotopy algorithm for the situation of time-varying signal with online updating. In the algorithm: (1) we fold concave regularation instead of l1-regularation, such as SCAD, which has been proved to have better statistical properties; (2) the complexity bound of our method is O(N^2/sqrt(epslion)). Besides the complexity bound, our method also has a special property. No matter how dramatically the significant parameters changes, our method will converge in very few steps if the significant parameters remain significant and insignificant parameters remain insignificant. In the numerical experiments, we present our method’s performance compared to some other methods in several several situation, such as, urban trafficc travel time and image recovery.