Data

Learning and Estimation Applications of an Online Homotopy Algorithm for a Generalization of the LASSO

Hofleitner, Aude
Rabbani, Tarek
Rafiee, Mohammad
Bayen, Alexandre M.
2014

The LASSO is a widely used shrinkage and selection method for linear regression. We propose a generalization of the LASSO in which the l1 penalty is applied on a linear transformation of the regression parameters, allowing to input prior information on the structure of the problem and to improve interpretability of the results. We also study time varying system with an l1-penalty on the variations of the state, leading to estimates that exhibit few “jumps”. We propose a homotopy algorithm that updates the solution as additional measurements are available. The algorithm takes advantage of...

Solutions to Estimation Problems for Scalar Hamilton–Jacobi Equations Using Linear Programming

Claudel, Christian G.
Chamoin, Timothée
Bayen, Alexandre M.
2014

This brief presents new convex formulations for solving estimation problems in systems modeled by scalar Hamilton-Jacobi (HJ) equations. Using a semi-analytic formula, we show that the constraints resulting from a HJ equation are convex, and can be written as a set of linear inequalities. We use this fact to pose various (and seemingly unrelated) estimation problems related to traffic flow-engineering as a set of linear programs. In particular, we solve data assimilation and data reconciliation problems for estimating the state of a system when the model and measurement constraints are...

The Path Inference Filter: Model-Based Low-Latency Map Matching of Probe Vehicle Data

Hunter, Timothy
Abbeel, Pieter
Bayen, Alexandre M.
2014

We consider the problem of reconstructing vehicle trajectories from sparse sequences of GPS points, for which the sampling interval is between 1 s and 2 min. We introduce a new class of algorithms, which are altogether called the path inference filter (PIF), that maps GPS data in real time, for a variety of tradeoffs and scenarios and with a high throughput. Numerous prior approaches in map matching can be shown to be special cases of the PIF presented in this paper. We present an efficient procedure for automatically training the filter on new data, with or without ground-truth...

Indoor Occupant Positioning System Using Active RFID Deployment and Particle Filters

Weekly, Kevin
Zou, Han
Xie, Lihua
Jia, Qing-Shan
Bayen, Alexandre M.
2014

This article describes a method for indoor positioning of human-carried active Radio Frequency Identification (RFID) tags based on the Sampling Importance Resampling (SIR) particle filtering algorithm. To use particle filtering methods, it is necessary to furnish statistical state transition and observation distributions. The state transition distribution is obstacle-aware and sampled from a precomputed accessibility map. The observation distribution is empirically determined by ground truth RSS measurements while moving the RFID tags along a known trajectory. From this data, we generate...

Evaluating the Reliability of Phones as Seismic Monitoring Instruments

Dashti, Shideh
Bray, Jonathan D.
Reilly, Jack
Glaser, Steven D.
Bayen, Alexandre
Mari, Ervasti
2014

Emergency responders must “see” the effects of an earthquake clearly and rapidly for effective response. This paper presents a novel use of cell phone and information technology to measure ground motion intensity parameters. The phone sensor is an imperfect device and has a limited operational range. Thus, shake table tests were performed to evaluate their reliability as seismic monitoring instruments. Representative handheld devices, either rigidly connected to the table or free to move, measured shaking intensity parameters well. Bias in 5%-damped spectral accelerations measured by...

Assessment of Uncertainty Propagation in the Dynamic Response of Single-Degree-of-Freedom Structures Using Reachability Analysis

Scacchioli, Annalisa
Bayen, Alexandre M.
Stojadinović, Bozidar
2014

A novel method to compute the bounds of the response of structures to dynamic loads, including earthquakes, is presented. This method, based on reachability analysis, deterministically predicts the sets of states an elastic structural system can reach under uncertain dynamic excitation starting from uncertain initial conditions, where deterministic uncertainty ranges describe uncertainties. Ellipsoidal approximations of these reachable sets for three canonical dynamic problems are presented to demonstrate the applicability of this method to single-degree-of-freedom (SDOF) systems....

Computing the Log-Determinant of Symmetric, Diagonally Dominant Matrices in Near-Linear Time

Hunter, Timothy
Alaoui, Ahmed El
Bayen, Alexandre M.
2014

We present new algorithms for computing the log-determinant of symmetric, diagonally dominant matrices. Existing algorithms run with cubic complexity with respect to the size of the matrix in the worst case. Our algorithm computes an approximation of the log-determinant in time near-linear with respect to the number of non-zero entries and with high probability. This algorithm builds upon the utra-sparsifiers introduced by Spielman and Teng for Laplacian matrices and ultimately uses their refined versions introduced by Koutis, Miller and Peng in the context of solving linear systems. We...

Building-in-Briefcase (BiB)

Weekly, Kevin
Jin, Ming
Zou, Han
Hsu, Christopher
Bayen, Alexandre
Spanos, Costas
2014

A building's environment has profound influence on occupant comfort and health. Continuous monitoring of building occupancy and environment is essential to fault detection, intelligent control, and building commissioning. Though many solutions for environmental measuring based on wireless sensor networks exist, they are not easily accessible to households and building owners who may lack time or technical expertise needed to set up a system and get quick and detailed overview of environmental conditions. Building-in-Briefcase (BiB) is a portable sensor network platform that is trivially...

Environmental Sensing by Wearable Device for Indoor Activity and Location Estimation

Jin, Ming
Zou, Han
Weekly, Kevin
Jia, Ruoxi
Bayen, Alexandre M.
Spanos, Costas
2014

We present results from a set of experiments in this pilot study to investigate the causal influence of user activity on various environmental parameters monitored by occupant-carried multi-purpose sensors. Hypotheses with respect to each type of measurements are verified, including temperature, humidity, and light level collected during eight typical activities: sitting in lab / cubicle, indoor walking / running, resting after physical activity, climbing stairs, taking elevators, and outdoor walking. Our main contribution is the development of features for activity and location...

Anatomy of a Crash

Marzuoli, Aude
Boidot, Emmanuel
Feron, Eric
Erp, Paul B. C. van
Ucko, Alexis
Bayen, Alexandre M.
2014

Transportation networks constitute a critical infrastructure enabling the transfers of passengers and goods, with a significant impact on the economy at different scales. Transportation modes, whether air, road or rail, are coupled and interdependent. The frequent occurrence of perturbations on one or several modes disrupts passengers' entire journeys, directly and through ripple effects. The present paper provides a case report of the Asiana Crash in San Francisco International Airport on July 6th 2013 and its repercussions on the multimodal transportation network. It studies the...