Addition and intersection of linear time-invariant behaviors
ELEC seminar room
Speaker: Ivan Markovsky
Abstract: In the ELEC seminar of 14/05/2019, I talked about intersection of autonomous linear time-invariant behaviors. This talk generalizes and extends the results to open systems (systems with inputs) and addition of behaviors. The new results are formulas for the complexity (number of inputs and order) of the sum and intersection systems and algorithms for obtaining their representations. Addition and intersection of linear time-invariant behaviors appears in the description of the set of exact models of bounded complexity for given data, the decomposition of a response of the system into a free response and a zero-initial conditions response, and interconnection of subsystems.
It's not MPC! Explicit Reference Governors, an alternative approach to the control of nonlinear systems with constraints
ELEC seminar room
Emanuele Garone (ULB)
Abstract: This talk introduces the Explicit Reference Governor, a novel control framework for the control of nonlinear systems subject to constraints. The main merit of this framework is that it allows to ensure systematically the satisfaction of constraints without resorting to any online optimization. The talk will start presenting the basic idea of Explicit Reference Governor based on Lyapunov level sets, and will present its generalization in terms of Dynamic Safety Margins and Navigation Fields. The talk will also present some constructive approach to design Explicit Reference Governors, and some applications to real systems.
Rank in Matrix Analysis: on the Preservers of Maximally Entangled States and Fractional Minimal Rank
ELEC seminar room
Speaker: Ben Grossmann (ELEC)
Abstract: For this talk, we will discuss the topic of my PhD thesis, which consisted of two projects. The first project concerns quantum information theory and the linear preservers of "maximally entangled states". In this context, "maximally entangled states" are a set of (rank-1, positive semidefinite) matrices, which in quantum information theory correspond to the highest-information system configurations. The goal of the project is to answer the following: which linear maps (with matrix inputs and matrix outputs) produce a maximally entangled output for any maximally entangled input? In the quantum context, this corresponds to classifying the "quantum channels" that perfectly preserve information (in a certain sense). The second project concerns the "fractional minimal rank", a new tool related to the problem of finding low-rank completions for "partial matrices" (matrices with some known entries and some unknown entries). The lowest rank that can be achieved by filling in the unknowns in a partial matrix (i.e. "completing" the matrix) is called the "minimal rank" of that partial matrix. We define and consider the "fractional minimal rank", a lower bound for the minimal rank that is found by filling in the unknowns with square matrices rather than with numbers.
Low-rank optimization via iteratively reweighted least squares
ELEC seminar room
Christian Kümmerle (Technical University of Munich)
Abstract:
We propose and discuss new Iteratively Reweighted Least Squares (IRLS) algorithms for the optimization non-smooth rank surrogates. As IRLS algorithms for similar problems, they minimize quadratic upper bounds of rank surrogates with updated smoothing, but we obtain considerably tighter quadratic bounds by drawing a connection to the second-order derivative structure of spectral functions. This leads an improved theoretical behavior of the IRLS algorithm, through fast convergence rates, and improved practical behavior in terms of data-efficiency.
Within this framework, we propose an IRLS algorithm for the recovery of low-rank matrices that are additionally linearly structured such as being a Hankel or Toeplitz matrix. These matrices are of relevance for the harmonic retrieval problem and for system identification.
For Hankel matrix completion, we establish a local convergence guarantee with quadratic rate of the IRLS strategy, if the provided entries of the matrix are sampled uniformly at random, and if the matrix to be completed satisfies a suitable coherence condition. Our strategy combines computational efficiency, as the dimensionality of its optimization variables scales sub-linearly in the matrix dimensions, with a favorable data efficiency which can be observed in experiments on completion tasks with few samples.
Joint work with Juliane Sigl and Claudio Mayrink Verdun (Technical University of Munich).
This talk is based on the works [1, 2, 3, 4]. Related work: [5, 6, 7].
1. C. Kümmerle and J. Sigl, “Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery,” Journal of Machine Learning Research, vol. 19, no. 47, pp. 1–49, 2018.
2. C. Kümmerle and C. M. Verdun, “Completion of Structured Low-Rank Matrices via Iteratively Reweighted Least Squares,” in 13th International Conference on Sampling Theory and Applications (SampTA), 2019. 3. C. Kümmerle and C. M. Verdun, “On the Completion of Structured Low-Rank Matrices via Iteratively Reweighted Least Squares,” preprint in preparation.
4. C. Kümmerle, Understanding and Enhancing Data Recovery Algorithms: From Noise-Blind Sparse Recovery to Reweighted Methods for Low-Rank Matrix Optimization. PhD thesis, Technical University of Munich, in preparation.
5. I. Daubechies, R. DeVore, M. Fornasier, and C. Güntürk, “Iteratively reweighted least squares minimization for sparse recovery,” Commun. Pure Appl. Math., vol. 63, pp. 1–38, 2010.
6. M. Fornasier, H. Rauhut, and R. Ward, “Low-rank matrix recovery via iteratively reweighted least squares minimization,” SIAM J. Optim., vol. 21, no. 4, pp. 1614–1640, 2011.
7. K. Mohan and M. Fazel, “Iterative reweighted algorithms for matrix rank minimization,” J. Mach. Learn. Res., vol. 13, no. 1, pp. 3441–3473, 2012.
Controllability of Differential-Algebraic Systems
ELEC seminar room
Speaker: Vikas Mishra
Common dynamics estimation
ELEC seminar room
Speaker: Ivan Markovsky
Abstract: Estimation of common dynamics among several observed signals occurs in signal processing, system theory, and computer algebra problems. In this talk, we propose subspace and optimization methods for common linear time-invariant dynamics detection and estimation. First, we consider the deterministic problem of detection of common dynamics when the data is exact (noise free). Then, we consider the stochastic estimation problem when the data is corrupted by white Gaussian noise. The methods proposed have a system theoretic interpretation of finding the intersection of autonomous linear time-invariant behaviors.
Reference: I. Markovsky, T. Liu, and A. Takeda. Common dynamics estimation. Technical report, Dept. ELEC, Vrije Universiteit Brussel, 2019. http://homepages.vub.ac.be/~imarkovs/publications/common-dynamics.pdf
Data-driven simulation using the nuclear norm heuristic
ELEC seminar room
Speaker: Philippe Dreesen
Abstract: Applications of signal processing and control are classically model-based, involving a two-step procedure for modeling and design: first a model is built from given data, and second, the estimated model is used for filtering, estimation, or control. Both steps typically involve optimization problems, but the combination of both is not necessarily optimal, and the modeling step often ignores the ultimate design objective. Recently, data-driven alternatives [1] are receiving attention, which employ a direct approach combining the modeling and design into a single step. In earlier work, it was shown that data-driven signal processing problems can often be rephrased as missing data completion problems, where the signal of interest is part of an incomplete low-rank mosaic Hankel structured matrix. In this talk, we consider the data-driven simulation problem, in which the output of a linear dynamic system is simulated for a given input, without first building a model of the system. More precisely, we are given an input/output trajectory of the system, and the question is how to generate the output for a given input sequence, such that the input/output data describes a trajectory of the same system. We consider a mosaic Hankel structured matrix that is built from the input/output data. The given input/output dataset defines the left-most part of the Hankel matrix, which is completely known; while the second part of the data contains only the to-be-simulated inputs, and defines the right-most part of the mosaic Hankel matrix, but contains unknown elements for the simulation outputs. The data-driven simulation problem can then be solved by completing the unknown part of the mosaic Hankel matrix such that the matrix has minimal rank, which imposes that both data sets describe trajectories of same system. Minimal rank matrix completion is in general a tough problem, but in the last decade, the use of the nuclear norm heuristic has been proposed as an efficient convex relaxation. Our findings suggest that, when using an adequate rescaling of the given data, the exact data-driven simulation problem can be solved by replacing the original structured low-rank matrix completion problem by a convex optimization problem, using the nuclear norm heuristic [2]. We will also show how to use the recently proposed tools of Gillard and Usevich [3] to derive bounds on the required scaling factor.
[1] I. Markovsky. A missing data approach to data-driven filtering and control. IEEE Trans. Automat. Contr., 62, pp. 1972-1978, 2017.
[2] P. Dreesen and I. Markovsky. Data-driven simulation using the nuclear norm heuristic. Proceedings of the International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2019), Brighton, UK, 2019.
[3] J. Gillard and K. Usevich. Structured low-rank matrix completion for forecasting in time series analysis. International Journal of Forecasting 34 (4), pp. 582-597, 2018.
A low-rank matrix completion approach to data-driven signal processing
ELEC seminar room
Speaker: Ivan Markovsky
Abstract: In filtering, control, and other mathematical engineering areas it is common to use a model-based approach, which splits the problem into two steps: 1) model identification and 2) model-based design. Despite its success, the model-based approach has the shortcoming that the design objective is not taken into account at the identification step, i.e., the model is not optimized for its intended use. In this talk, I show a data-driven approach, which combines the identification and the model-based design into one joint problem. The signal of interest is modeled as a missing part of a trajectory of the data generating system. Subsequently, the missing data estimation problem is reformulated as a mosaic-Hankel structured matrix low-rank approximation/completion problem. The missing data estimation approach for data-driven signal processing and a local optimization method for its practical implementation are illustrated on examples of control, state estimation, filtering/smoothing, and prediction. Development of fast algorithms with provable properties in the presence of measurement noise and disturbances is a topic of current research.
Blind and off-grid acoustic echoes retrieval using multichannel annihilating filters
ELEC seminar room
Speaker: Antoine Deleforge, Inria Nancy
Abstract: When a sound wave propagates from a point source through a medium and is reflected on surfaces before reaching microphones, the measured signals consist of mixtures of the direct path signal with delayed and attenuated copies of itself. This acoustical phenomenon is referred to as echoes, or reverberation, and is generally considered as a nuisance in audio signal processing. After introducing some basic signal processing and acoustic background, this seminar will present recent works showing how acoustic echoes can be blindly estimated from audio recordings, using a method combining annihilating filter estimation and polynomial rooting. We will then show how the knowledge of such echoes can in fact help some audio signal processing tasks such as beamforming, source separation or sound source localization.