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


The problem of finding a minimum l1-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
l1-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 l1-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


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


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.


  personal loans online . Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Cheap Levitra, but also as part of its analogs.