Skip to main content
eScholarship
Open Access Publications from the University of California

UC Berkeley

UC Berkeley Electronic Theses and Dissertations bannerUC Berkeley

Topics in Large-Scale Sparse Estimation and Control

Abstract

In this thesis, we study two topics related to large-scale sparse

estimation and control. In the first topic, we describe a method to

eliminate features (variables) in $\ell_{1}$-regularized convex optimization

problems. The elimination of features leads to a potentially substantial

reduction in computational effort needed to solve such problems, especially

for large values of the penalty parameter. Our method is not heuristic:

it only eliminates features that are guaranteed to be absent after

solving the optimization problem. The feature elimination step is

easy to parallelize and can test each feature for elimination independently.

Moreover, the computational effort of our method is negligible compared

to that of solving the convex problem.

We study the case of $\ell_{1}$-regularized least-squares problem

(a.k.a. LASSO) extensively and derive a closed-form sufficient condition

for eliminating features. The sufficient condition can be evaluated

by few vector-matrix multiplications. For comparison purposes, we

present a LASSO solver that integrates SAFE with the Coordinate Descent

method. We call our method CD-SAFE, and we report the number of computations

needed for solving a LASSO problem using CD-SAFE and using the plain

Coordinate Descent method. We observe at least a $100$ fold reduction

in computational complexity for dense and sparse data-sets consisting

of millions of variables and millions of observations. Some of these

data-sets can cause memory problems when loaded, or need specialized

solvers. However, with SAFE, we can extend LASSO solvers capabilities

to treat large-scale problems, previously out of their reach. This

is possible, because SAFE eliminates variables and thus portions of

our data at the outset, before loading it into our memory.

We also show how our method can be extended to general $\ell_{1}$-regularized

convex problems. We present preliminary results for the Sparse Support

Vector Machine and Logistic Regression problems.

In the second topic of the thesis, we derive a method for open-loop

control of open channel flow, based on the Hayami model, a parabolic

partial differential equation resulting from a simplification of the

Saint-Venant equations. The open-loop control is represented as infinite

series using differential flatness, for which convergence is assessed.

Numerical simulations show the effectiveness of the approach by applying

the open-loop controller to irrigation canals modeled by the full

Saint-Venant equations.

We experiment with our controller on the Gignac Canal, located northwest

of Montpellier, in southern France. The experiments show that it is

possible to achieve a desired water flow at the downstream of a canal

using the Hayami model as an approximation of the real-system. However,

our observations of the measured water flow at the upstream controlled

gate made us realize some actuator limitations. For example, deadband

in the gate opening and unmodeled disturbances such as friction in

the gate-opening mechanism, only allow us to deliver piece-wise constant

control inputs. This fact made us investigate a way to compute a controller

that respects the actuator limitations. We use the CD-SAFE algorithm,

to compute such open-loop control for the upstream water flow. We

compare the computational effort needed to obtain an open-loop control

with certain dynamics using the CD-SAFE algorithm and the plain Coordinate

Descent algoirthm. We show that with CD-SAFE we are able to obain

an open-loop control signal with cheaper computations.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View