## Invited Session Tue.3.H 1028

#### Tuesday, 15:15 - 16:45 h, Room: H 1028

**Cluster 21: Sparse optimization & compressed sensing** [...]

### Algorithms for sparse optimization I

**Chair: Andreas Michael Tillmann**

**Tuesday, 15:15 - 15:40 h, Room: H 1028, Talk 1**

**Andreas Michael Tillmann**

Heuristic optimality check and computational solver comparison for basis pursuit

**Coauthors: Dirk A. Lorenz, Marc E. Pfetsch**

**Abstract:**

The problem of finding a minimum *l*_{1}-norm solution to an

underdetermined linear system is an important problem in compressed

sensing, where it is also known as basis pursuit. We propose a

heuristic optimality check (HOC) as a general tool for

*l*_{1}-minimization, which often allows for early termination by

"guessing'' a primal-dual optimal pair based on an approximate

support. Moreover, we provide an extensive numerical comparison of

various state-of-the-art *l*_{1}-solvers that have been proposed during

the last decade. The computational evaluation also includes a novel

subgradient algorithm which employs adaptive approximate projections

using conjugate gradients, and provides empirical evidence for the

effectiveness of the proposed HOC.

**Tuesday, 15:45 - 16:10 h, Room: H 1028, Talk 2**

**Spartak Zikrin**

Sparse optimization techniques for solving multilinear least-squares problems with application to design of filter networks

**Coauthors: Mats Andersson, Oleg Burdakov, Hans Knutsson**

**Abstract:**

The multilinear least-squares (MLLS) problem is an extension of the linear least-squares problem. The difference is that a multilinear operator used in place of a matrix-vector product. The MLLS is typically a large-scale problem characterized by a large number of local minimizers. Each of the local minimizers is singular and non-isolated. The MLLS problem originates, for instance, from the design of filter networks.

For the design of filter networks, we consider the problem of

finding optimal sparsity of the sub-filters that compose the network. This results in a MLLS problem augmented by an additional constraint that poses an upper limit on the number of nonzero components in the solution. This sparse multilinear least-squares problem is NP-hard. We present an approach for approximately solving the problem. In our numerical experiments, a greedy-type sparse optimization

algorithm is used for designing 2D and 3D filter networks.

The efficiency of our approach is illustrated by results of numerical experiments performed for some problems related to the design of filter networks.

**Tuesday, 16:15 - 16:40 h, Room: H 1028, Talk 3**

**Maxim Demenkov**

Real-time linear inverse problem and control allocation in technical systems

**Abstract:**

Control allocation is a set of methods for control of modern overactuated mechanical systems (such as aircrafts, marine vehicles, electric cars), and deals with distributing of the total control demand among the individual actuators. The idea of control allocation allows to deal with control constraints and actuator faults separately from the design of the main regulator, which uses virtual control input. Its dimension is usually quite low, while the number of physical actuators can be much higher. Using linearization, control allocation is equivalent to linear inverse problem with interval-constrained vector *x*, which we need to recover from limited linear measurements: *y=Ax*. Depending on the particular application, one can seek a sparse solution (which minimizes number of physical actuators used for control) or optimize convex function of *x*. Note that if *x* constrained to a hypercube, then *y* is constrained to its image, a zonotope. We propose a new real-time method for calculating *x*, which is based on interval analysis ideology. Its basic operations are hypercube bisection and explicit reconstruction of the zonotope as a system of linear inequalities.