Search

This paper presents a multilevel algorithm specifically designed for radio-interferometric imaging in astronomy. The proposed algorithm is used to solve the uSARA (unconstrained Sparsity Averaging Reweighting Analysis) formulation of this image restoration problem. Multilevel algorithms rely on a hierarchy of approximations of the objective function to accelerate its optimization. In contrast to the usual multilevel approaches where this hierarchy is derived in the parameter space, here we construct the hierarchy of approximations in the observation space. The proposed approach is compared to a reweighted forward-backward procedure, which is the backbone iteration scheme for solving the uSARA problem.

We consider the problem of learning a graph modeling the statistical relations of the $d$ variables from a dataset with $n$ samples $X \in \mathbb{R}^{n \times d}$. Standard approaches amount to searching for a precision matrix $\Theta$ representative of a Gaussian graphical model that adequately explains the data. However, most maximum likelihood-based estimators usually require storing the $d^{2}$ values of the empirical covariance matrix, which can become prohibitive in a high-dimensional setting. In this work, we adopt a compressive viewpoint and aim to estimate a sparse $\Theta$ from a \emph{sketch} of the data, i.e. a low-dimensional vector of size $m \ll d^{2}$ carefully designed from $X$ using non-linear random features. Under certain assumptions on the spectrum of $\Theta$ (or its condition number), we show that it is possible to estimate it from a sketch of size $m=\Omega\left((d+2k)\log(d)\right)$ where $k$ is the maximal number of edges of the underlying graph. These information-theoretic guarantees are inspired by compressed sensing theory and involve restricted isometry properties and instance optimal decoders. We investigate the possibility of achieving practical recovery with an iterative algorithm based on the graphical lasso, viewed as a specific denoiser. We compare our approach and graphical lasso on synthetic datasets, demonstrating its favorable performance even when the dataset is compressed.

Pairwise temporal interactions between entities can be represented as temporal networks, which code the propagation of processes such as epidemic spreading or information cascades, evolving on top of them. The largest outcome of these processes is directly linked to the structure of the underlying network. Indeed, a node of a network at given time cannot affect more nodes in the future than it can reach via time-respecting paths. This set of nodes reachable from a source defines an out-component, which identification is costly. In this paper, we propose an efficient matrix algorithm to tackle this issue and show that it outperforms other state-of-the-art methods. Secondly, we propose a hashing framework to coarsen large temporal networks into smaller proxies on which out-components are easier to estimate, and then recombined to obtain the initial components. Our graph hashing solution has implications in privacy respecting representation of temporal networks., Comment: 17 pages, 8 figures

We provide a framework and algorithm for tuning the hyperparameters of the Graphical Lasso via a bilevel optimization problem solved with a first-order method. In particular, we derive the Jacobian of the Graphical Lasso solution with respect to its regularization hyperparameters.

This paper presents a multilevel framework for inertial and inexact proximal algorithms, that encompasses multilevel versions of classical algorithms such as forward-backward and FISTA. The methods are supported by strong theoretical guarantees: we prove both the rate of convergence and the convergence of the iterates to a minimum in the convex case, an important result for ill-posed problems. We propose a particular instance of IML (Inexact MultiLevel) FISTA, based on the use of the Moreau envelope to build efficient and useful coarse corrections, fully adapted to solve problems in image restoration. Such a construction is derived for a broad class of composite optimization problems with proximable functions. We evaluate our approach on several image reconstruction problems and we show that it considerably accelerates the convergence of the corresponding one-level (i.e. standard) version of the methods, for large-scale images.

This paper presents a multilevel FISTA algorithm, based on the use of the Moreau envelope to build the correction brought by the coarse models, which is easy to compute when the explicit form of the proximal operator of the considered functions is known. This approach is supported by strong theoretical guarantees: we prove both the rate of convergence and the convergence of the iterates to a minimum in the convex case, an important result for ill-posed problems. We evaluate our approach on image restoration problems and we show that it outperforms classical FISTA for large-scale images.

The paper proposes a novel medical device based on a 9 dof IMU to help health professionals performing more precisely the electrode placement task in EEG exams. The tool precisely tells the operator if the 10-20 electrode placement system is being correctly followed. The manual task is of major importance and time consuming, because all the electrodes must be correctly and very precisely placed in the head of the patient. The gold standard process is manual, and although several medical devices (developed to other types of medical procedures) can be applied to increase the precision of the electrode placement, they are still very expensive. The proposed medical device, based only on the sensors of a 9 dof IMU, and the processing capabilities of a microprocessor, diminish the price of the device. Moreover, the size of the apparatus is also diminished, when compared with infrared vision based systems. The developed system includes a visualization subsystem that visualises the position of the electrodes in a virtual head of the patient, using a specific tool, 3DSlicer, to receive and visualise the 3D pose of the medical device when point to the patient head. Preliminary results showed the validity of the proposed device., Comment: The Romanian Review Precision Mechanics, Optics & Mechatronics, In press

Diffusing a graph signal at multiple scales requires computing the action of the exponential of several multiples of the Laplacian matrix. We tighten a bound on the approximation error of truncated Chebyshev polynomial approximations of the exponential, hence significantly improving a priori estimates of the polynomial order for a prescribed error. We further exploit properties of these approximations to factorize the computation of the action of the diffusion operator over multiple scales, thus reducing drastically its computational cost.