betaFeedback

WorksComputer Science

GraphIT: Iterative reweighted ℓ1\ell_1 algorithm for sparse graph inference in state-space models

Abstract

State-space models (SSMs) are a common tool for modeling multi-variate discrete-time signals. The linear-Gaussian (LG) SSM is widely applied as it allows for a closed-form solution at inference, if the model parameters are known. However, they are rarely available in real-world problems and must be estimated. Promoting sparsity of these parameters favours both interpretability and tractable inference. In this work, we propose GraphIT, a majorization-minimization (MM) algorithm for estimating the linear operator in the state equation of an LG-SSM under sparse prior. A versatile family of non-convex regularization potentials is proposed. The MM method relies on tools inherited from the expectation-maximization methodology and the iterated reweighted-l1 approach. In particular, we derive a suitable convex upper bound for the objective function, that we then minimize using a proximal splitting algorithm. Numerical experiments illustrate the benefits of the proposed inference technique.

Index Terms— State-space model, graphical inference, sparsity, iterative reweighted scheme, MM algorithm.

Introduction

Signal processing applications often involve dealing with discrete-time multi-variate series that need to be processed to perform statistical tasks such as prediction. State-space models (SSMs) relate the observation process with a hidden state that evolves over time. This versatile approach allows to describe complex phenomena through the dynamics of the hidden state. It also allows for the incorporation physical knowledge about the system and to retrieve relevant structure that can be inferred when processing the data. There exists abundant literature in graphical models for multi-variate time series, e.g., [1, 2, 3, 4], and more recently also within SSMs [5, 6], including also fully probabilistic approaches [7, 8]. There are multiple applications of such graphical representa-

tions, e.g., in biology [9, 10], social network analysis [11], or neuroscience [12].

The graphical approach in SSMs benefits from the promotion of sparsity with, at least, the following three advantages. First, sparsity enhances interpretability, which is highly desired for instance in models where the hidden state has a physical interpretation. Second, it reduces the effective dimension of the parameters, alleviating the curse of dimensionality during estimation. Third, it is possible to promote other properties that are complementary with sparsity, allowing to introduce useful prior knowledge on the system, e.g., stability of the hidden process and spectral constraints [13].

In [5, 6], we introduced GraphEM, an expectation-maximization (EM) method for parameter estimation in linear Gaussian (LG) SSMs. Specifically, we addressed the challenging task of estimating the transition matrix that encodes the Markovian dependencies in the evolution of the multi-variate state. GraphEM is based on a novel perspective that relates the transition matrix to the adjacency matrix of a directed graph, encoding causal relationship among state dimensions in the Granger-causality sense. The M-step in the EM procedure relies on a proximal splitting, benefiting from sound convergence guarantees. GraphEM thus extends the well-established EM technique for maximum likelihood estimation of LG-SSM parameters [14, 15, 16, 17] into a maximum a posteriori estimator that suitably encompasses sophisticated prior terms. However, it is limited to convex regularizers. In the literature of sparse graph inference, non-convex penalties such as SCAD [18], MCP [19], CEL0 [20] have shown to be more suited than their convex surrogate ℓ1\ell_1 norm (i.e., Lasso) to properly reconstruct very sparse graphs [21, 22, 23]. These penalties can be viewed as continuous non-convex approximations to the quasi-norm ℓ0\ell_0. However, non-convexity prevents the use of standard optimization tools. An efficient strategy is to resort to iterative reweighted (IR) schemes [24, 25], which are based on the majorization-minimization (MM) principle [26] to recast the complicated objective function into a sequence of tractable upper bounds. IRℓ1\ell_1 algorithms have been widely applied to several signal processing problems [27, 28, 29, 30, 31, 32], but, to our knowledge, remain unstudied within SSMs.

In this paper, we propose a novel method called GraphIT that combines the EM technique with the powerful IRℓ1\ell_1 strategy for the estimation of model parameters in SSMs. More precisely, GraphIT is able to provide an estimation of the LG-SSM transition matrix for a wide class of non-convex sparsity enhancing priors. Thanks to the IRℓ1\ell_1 framework, GraphIT algorithm benefits from simple and not expensive updates. Experimental results on several synthetic datasets allow us to assess the ability of our method for improving the recovery rate for sparse transition matrices.

The paper is structured as follows. In Section 2, we describe the model, the filtering/smoothing algorithms, and revisit the GraphEM framework. The novel GraphIT algorithm is presented in Section 3. The paper ends with numerical results in Section 4 and some concluding remarks in Section 5.

BACKGROUND

Inference in linear state-space model

We consider the LG-SSM described by

xk=Axk−1+qk,yk=Hxk+rk,(1)\begin{aligned} x_k &= A x_{k-1} + q_k,\\ y_k &= H x_k + r_k, \tag*{(1)} \end{aligned}

for k=1,…,Kk = 1,\ldots,K, where xk∈RNxx_k \in\mathbb{R}^{N_x} and yk∈RNyy_k \in\mathbb{R}^{N_y} are the hidden state and observation at time kk, respectively, A=RNx×NxA = \mathbb{R}^{N_x \times N_x}, H=RNy×NxH = \mathbb{R}^{N_y \times N_x}, and {qk}k=1K∼N(0,Q)\{q_k\}_{k=1}^{K} \sim\mathcal{N}(0,Q) and {rk}k=1K∼N(0,R)\{r_k\}_{k=1}^{K} \sim\mathcal{N}(0,R) the i.i.d. state and observation noise processes, respectively. The distribution of the initial state is x0∼N(x0;μ0,Σ0)x_0 \sim\mathcal{N}(x_0;\mu_0,\Sigma_0) with known μ0\mu_0 and Σ0\Sigma_0.

In SSMs, the filtering problem consists in the computation of the so-called filtering distributions, p(xk∣y1:k)p(x_k|y_{1:k}), where y1:k≜{yj}j=1ky_{1:k} \triangleq\{y_j\}_{j=1}^{k}. In the LG-SSM of Eq. (1), the Kalman filter (KF) exactly computes the filtering distributions in a sequential and efficient manner, yielding p(xk∣y1:k)=N(xk∣μk,Σk)p(x_k|y_{1:k}) = \mathcal{N}(x_k|\mu_k,\Sigma_k), i.e., for every k=1,…,Kk = 1,\ldots,K, it computes the mean μk\mu_k and covariance Σk\Sigma_k of each Gaussian filtering distribution [33]. The smoothing problem aims at computing p(xk∣y1:K)p(x_k|y_{1:K}), i.e., the posterior probability density functions (pdfs) conditioning on the whole set of observations instead, for all k=1,…,Kk = 1,\ldots,K. In the LG-SSM, the smoothing pdfs are also available in a closed-form expression (again, Gaussian pdfs) by the Rauch-Tung-Striebel (RTS) smoother, p(xk∣y1:K)=N(xk∣μks,Σks)p(x_k|y_{1:K}) = \mathcal{N}(x_k|\mu_k^s,\Sigma_k^s). Both KF and RTS smoother require to know the model parameters μ0\mu_0, Σ0\Sigma_0, AA, HH, QQ, and RR. The estimation of the model parameters in the model above has been a subject of intense research, e.g., recently [34, 35] (see [36 Ch. 12] for a review).

GraphEM to estimate the transition matrix

GraphEM [5, 6] is an EM-based algorithm that we recently introduced for the maximum a posteriori (MAP) estimation of AA under log-concave prior distribution p(A)p(A). GraphEM aims at finding the minimum of L(A)≜L0(A)+L1:K(A)\mathcal{L}(A) \triangleq\mathcal{L}_0(A) + \mathcal{L}_{1:K}(A) with

L0(A)≜−log⁡p(A)\mathcal{L}_0(A) \triangleq-\log p(A) and L1:K(A)≜−log⁡p(y1:K∣A)\mathcal{L}_{1:K}(A) \triangleq-\log p(y_{1:K}|A). The matrix AA is interpreted in GraphEM to encode a directed graph among the state dimensions. Prior p(A)p(A) can encode structural information on such graph (e.g., sparsity). This graph plays an important role in the SSM interpretation, with links to Granger-causality models (see a discussion in [6]). The likelihood of AA associated to the model in Eq. (1) is

L1:K(A)=∑k=1K12log⁡∣2πSk∣+12zkTSk−1zk,(2)\mathcal{L}_{1:K}(A) = \sum_{k=1}^{K} \frac{1}{2}\log|2\pi S_k| + \frac{1}{2}z_k^{\mathsf{T}}S_k^{-1}z_k, \tag*{(2)}

where zk=yk−HAμk−1z_k = y_k - HA\mu_{k-1} and SkS_k is the covariance matrix of the predictive distribution p(yk∣y1:k−1,A)=N(yk;HAμk−1,Sk)p(y_k|y_{1:k-1},A) = \mathcal{N}(y_k;HA\mu_{k-1},S_k), both being obtained by the KF, run for a given AA (see [36 Section 4.3]). The direct minimization of L\mathcal{L} is difficult due to (i) the implicit form of L1:K\mathcal{L}_{1:K}, and (ii) the possibly non-differentiability of L0\mathcal{L}_0. The GraphEM approach implements an EM strategy, generalizing the one in [16], by relying on successive upper bounds of L1:K\mathcal{L}_{1:K}, that leads to obtain a sequence of tractable inner problems.

Let us consider KF/RTS outputs for a given A′∈RNx×NxA' \in\mathbb{R}^{N_x \times N_x}. Denote, for every k∈{1,…,K}k \in\{1,\ldots,K\}, Gk=Σk(A′)T(A′Σk(A′)T+Q)−1G_k = \Sigma_k(A')^{\mathsf{T}}(A'\Sigma_k(A')^{\mathsf{T}} + Q)^{-1}, and set Ψ=∑k=1KΣks+μks(μks)T\Psi= \sum_{k=1}^{K}\Sigma_k^s + \mu_k^s(\mu_k^s)^{\mathsf{T}}, Φ=∑k=1KΣk−1+μk−1(μk−1)T\Phi= \sum_{k=1}^{K}\Sigma_{k-1} + \mu_{k-1}(\mu_{k-1})^{\mathsf{T}}, and Δ=∑k=1KΣksGk−1+μks(μk−1)T\Delta= \sum_{k=1}^{K}\Sigma_k^sG_{k-1} + \mu_k^s(\mu_{k-1})^{\mathsf{T}}. Then, according to [36 Chap. 12],

(∀A∈RNx×Nx)L1:K(A)≤(\forall A \in\mathbb{R}^{N_x \times N_x})\quad\mathcal{L}_{1:K}(A) \le
−∫p(x0:K,y1:K∣y1:K,A′)log⁡p(x0:K,y1:K∣A) dx0:K+ct/A=12tr⁡(Q−1(Σ−ΔAT−AΔT+AΦAT))+ct/A,(3)\begin{aligned} -\int p(x_{0:K},y_{1:K}|y_{1:K},A')\log p(x_{0:K},y_{1:K}|A)\,\mathrm{d}x_{0:K} + \mathrm{ct}_{/A} \\ &= \frac{1}{2}\operatorname{tr}\left(Q^{-1}\left(\Sigma-\Delta A^{\mathsf{T}}-A\Delta^{\mathsf{T}}+A\Phi A^{\mathsf{T}}\right)\right)+\mathrm{ct}_{/A}, \tag*{(3)} \end{aligned}

where tr⁡\operatorname{tr} is the trace operator, and ct/A\mathrm{ct}_{/A} is a constant term not depending on AA, such that equality holds at A=A′A=A'. The GraphEM algorithm iterates alternating between an E-step, building the right term in (3), and an M-step minimizing the sum of this term with L0\mathcal{L}_0, using a proximal splitting scheme. In the simple case of a Laplace prior (i.e., ℓ1\ell_1 norm penalty), the minimization in the M-step can be performed by a Douglas-Rachford algorithm, leading to the simpler form of GraphEM in [5], while a more sophisticated primal-dual splitting technique is proposed in [6] for dealing with a generic convex penalty. Convergence guarantees for the resulting GraphEM iteration are discussed in [6].

PROPOSED GRAPHIT APPROACH

Considered class of penalties

Our study focuses on the class of non-convex sparsifying penalties that have been studied for instance in [37] (see also [38] in the context of robust estimation). We define

L0(A)=∑1≤i,j≤Nxρ(∣Ai,j∣),(4)\mathcal{L}_0(A) = \sum_{1\le i,j\le N_x}\rho(|A_{i,j}|), \tag*{(4)}

where Ai,jA_{i,j} denotes the (i,j)(i,j) entry of AA, and ρ:R→[0,+∞)\rho:\mathbb{R}\to[0,+\infty) is a potential satisfying:

  1. ρ\rho is continuous, and it is increasing on [0,+∞)[0,+\infty) with ρ(0)=0\rho(0)=0;

  1. ρ\rho is differentiable on (0,+∞)(0,+\infty), with derivative (when defined) denoted ρ′\rho';

  1. ρ′\rho' is decreasing on (0,+∞)(0,+\infty) and lim⁡u→0+ρ′(u)=γ∈(0,+∞)\lim_{u\to0+}\rho'(u)=\gamma\in(0,+\infty).

A large class of potential functions satisfy the above requirements. Some relevant examples are listed in Table 1. Except for SCAD, in our examples, epi-convergence of u↦ρ(∣u∣)u\mapsto\rho(|u|) to the discrete potential u↦δu≠0u\mapsto\delta_{u\ne0} (equals 0 for a zero-valued input; 1 otherwise) is established for λ→0+\lambda\to0^{+}. Then, the prior in (4) can be seen as an approximation of γℓ0\gamma\ell_{0}. Figure 1 shows the plots for a subset of potentials, with γ=1\gamma=1. We also show ℓ1\ell_{1} and ℓ0\ell_{0} penalties for comparison. The considered class of priors is continuous, but still non-convex approximations of ℓ0\ell_{0}.

Nameρ(∣u∣)\rho(|u|)ρ′(∣u∣)\rho'(|u|)
log-sumγλ(log⁡(∣u∣+λ)−log⁡(λ))\gamma\lambda(\log(|u|+\lambda)-\log(\lambda)), with λ>0\lambda>0γλ(∣u∣+λ)−1\gamma\lambda(|u|+\lambda)^{-1}
atanγλarctan⁡(λ∣u∣)\frac{\gamma}{\lambda}\arctan(\lambda|u|), with λ>0\lambda>0γ1+λ2u2\frac{\gamma}{1+\lambda^{2}u^{2}}
Mangasarianγλ(1−exp⁡(−λ∣u∣))\frac{\gamma}{\lambda}(1-\exp(-\lambda|u|))γexp⁡(−λ∣u∣)\gamma\exp(-\lambda|u|)
MCP{γ∣u∣−u22λif ∣u∣≤λγλγ22otherwise\begin{cases}\gamma|u|-\frac{u^{2}}{2\lambda} & \text{if }|u|\le\lambda\gamma\\ \frac{\lambda\gamma^{2}}{2} & \text{otherwise}\end{cases}, with λ>0\lambda>0{γ−∣u∣λif ∣u∣≤λγ0otherwise\begin{cases}\gamma-\frac{|u|}{\lambda} & \text{if }|u|\le\lambda\gamma\\ 0 & \text{otherwise}\end{cases}
SCAD{γ∣u∣if ∣u∣≤γ−u2+2aγ∣u∣−γ22(a−1)if γ<∣u∣≤aγ(a+1)γ22otherwise\begin{cases}\gamma|u| & \text{if }|u|\le\gamma\\ \frac{-u^{2}+2a\gamma|u|-\gamma^{2}}{2(a-1)} & \text{if }\gamma<|u|\le a\gamma\\ \frac{(a+1)\gamma^{2}}{2} & \text{otherwise}\end{cases}, with a>2a>2{γif ∣u∣≤γ2aγ−2∣u∣2(a−1)if γ<∣u∣≤aγ0otherwise\begin{cases}\gamma& \text{if }|u|\le\gamma\\ \frac{2a\gamma-2|u|}{2(a-1)} & \text{if }\gamma<|u|\le a\gamma\\ 0 & \text{otherwise}\end{cases}

Table 1. Example of potential functions and their derivatives with hyper-parameter γ>0\gamma>0 such that ρ′(0+)=γ\rho'(0+)=\gamma.

Plots of example potential functions

Figure 1. Example of functions ρ(∣⋅∣)\rho(|\cdot|), with λ=0.5\lambda=0.5 and γ=1\gamma=1.

IRℓ1\ell_{1} approach

The properties assumed on the potential ρ\rho yield a key property, that is at the core of the so-called IRℓ1\ell_{1} optimization approach [39]. Let v∈Rv\in\mathbb{R}. Then,

(∀u∈R)ρ(∣u∣)≤ρ′(∣v∣)(∣u∣−∣v∣)+ρ(∣v∣),(5)(\forall u\in\mathbb{R})\quad\rho(|u|)\le\rho'(|v|)(|u|-|v|)+\rho(|v|), \tag*{(5)}

where equality holds at u=vu=v. A proof for this result can be found in [29]. The following convex upper bound is then obtained, for (4), at some A′∈RNx×NxA'\in\mathbb{R}^{N_x\times N_x}:

L0(A)≤∥Ω(A′)⊙A∥1+ct/A,(6)\mathcal{L}_{0}(A)\le\lVert\Omega(A')\odot A\rVert_{1}+c_{\mathrm{t}/A}, \tag*{(6)}

where ct/Ac_{\mathrm{t}/A} is such that equality holds at A=A′A=A'. Here-above, Ω(A′)∈[0,+∞)Nx×Nx\Omega(A')\in[0,+\infty)^{N_x\times N_x} is a matrix of weights defined as Ωi,j=ρ′(∣Ai,j∣)\Omega_{i,j}=\rho'(|A_{i,j}|) for every (i,j)(i,j). Moreover, ⊙\odot is the Hadamard (i.e., element-wise) product. We provide in Table 1 the expression for ρ′(∣⋅∣)\rho'(|\cdot|) for our examples. The IRℓ1\ell_{1} technique amounts at minimizing L0+f\mathcal{L}_{0}+f, where ff a simple function (typically a quadratic term), by iteratively solving the tractable problem of the minimization of

∥Ω(A′)⊙⋅∥1+f\lVert\Omega(A')\odot\cdot\rVert_{1}+f. When ff is a least square discrepancy, the inner problem in IRℓ1\ell_{1} can be solved using one of the several efficient approaches proposed in the literature for penalized least squares under Lasso penalty [40, 41, 42].

GraphIT algorithm

In the following, we describe the GraphIT algorithm, which is summarized in Algorithm 1. GraphIT is an MM algorithm, to search for the MAP estimate of AA within our SSM (i.e., the minimizer of L\mathcal{L}), under the prior defined in (4). It has an iterative structure, which alternates over majorization and minimization steps. The difficulty lies in the construction of the majorization approximation and in the required optimization algorithm to minimize it.

Algorithm 1 GraphIT algorithm

Initial A(0)A^{(0)} and penalty parameters. Precision ε>0\varepsilon>0.

Majorization:

Run KF and RTS smoother using A(i−1)A^{(i-1)} and construct

(∀A∈RNx×Nx)Q(A;A(i−1))=12tr⁡(Q−1(Σ−ΔAT−AΔT+AΦAT))+∥Ω(A(i−1))⊙A∥1.(7)(\forall A\in\mathbb{R}^{N_x\times N_x})\quad Q(A;A^{(i-1)})= \frac{1}{2}\operatorname{tr}\left(Q^{-1}(\Sigma-\Delta A^{\mathsf{T}}-A\Delta^{\mathsf{T}}+A\Phi A^{\mathsf{T}})\right)+\lVert\Omega(A^{(i-1)})\odot A\rVert_{1}. \tag*{(7)}

Minimization:

Solve A(i)=argmin⁡A(Q(A;A(i−1)))A^{(i)}=\operatorname*{argmin}_{A}\left(Q(A;A^{(i-1)})\right) using DR solver.

Stopping condition:

If ∥A(i)−A(i−1)∥F≤ε∥A(i−1)∥F\lVert A^{(i)}-A^{(i-1)}\rVert_{F}\le\varepsilon\lVert A^{(i-1)}\rVert_{F}, stop the recursion.

Given an estimation, A(i−1)A^{(i-1)}, coming from the previous iteration, we construct a specific majorization function Q(A;A(i−1))Q(A;A^{(i-1)}) defined in Eq. (7) that combines (i) an EM-based majorization involving outputs from running the KF/RTS with transition matrix A(i−1)A^{(i-1)}, and (ii) a convex upper bound for our prior term in Eq. (4) (coming from IRℓ1\ell_{1} approach). Using (3) and (6), we can show that the function in Eq. (7) is such that, for every A∈RNx×NxA\in\mathbb{R}^{N_x\times N_x} and every iteration i∈Ni\in\mathbb{N}, L(A)≤Q(A;A(i−1))+ct/A\mathcal{L}(A)\le Q(A;A^{(i-1)})+c_{\mathrm{t}/A} (hereagain, the constant term is set so as to have equality at A=A(i−1)A=A^{(i-1)}). In practice, the minimization of the above upper bound is done through the Douglas-Rachford (DR) algorithm [43] initialized at the current iterate A(i−1)A^{(i-1)}. As a virtue of the MM construction, the sequence {L(A(i))}i∈N\{\mathcal{L}(A^{(i)})\}_{i\in\mathbb{N}} is a decreasing sequence converging to a finite limit.

Experimental Evaluation

We illustrate the performance of the proposed GraphIT method on a time series simulated according to model (1), with Nx=Ny∈{8,16}N_x = N_y \in\{8, 16\}. Sparse matrices A are randomly generated, with support size (i.e., number of edges in the associated graph) S∈{4,8,16}S \in\{4, 8, 16\}. For each of the six scenarios, we randomly select SS indexes for which we set the associated entry in A equals to a realization of an i.i.d. standard normal distribution and with the Nx2−SN_x^2-S other entries being set to zero. The non-zero entries of A are scaled so that the spectral norm of A is less than one to guarantee the stability of the Markov process. We finally set H = Id, K=103K = 10^3 and Q = σQ2I\sigma_Q^2\mathbf{I}d, R = σR2I\sigma_R^2\mathbf{I}d, Σ0=σ02I\mathbf{\Sigma}_0 = \sigma_0^2\mathbf{I}d with (σQ,σR,σ0)=(10−1,10−1,10−4)(\sigma_Q,\sigma_R,\sigma_0) = (10^{-1},10^{-1},10^{-4}).

For each of the six datasets, we ran GraphIT using log-sum penalty (Table 1, first row) and precision ξ=10−3\xi= 10^{-3} (with a maximum of 50 iterations). We also display the results of GraphEM using ℓ1\ell_1 penalty, and of the maximum likelihood estimator computed by an EM algorithm (MLEM) [15, 16]. All methods are initialized with a matrix with entries Ai,j=(10−1)∣i−j∣A_{i,j} = (10^{-1})^{|i-j|}, rescaled to have spectral norm equals to 0.99. The methods are compared in terms of relative mean square error (RMSE) on A, accuracy and F1 scores for the graph edge detection, using a threshold of 10−1010^{-10} on the entries of matrix A. All results are averaged on 50 realizations. The regularization parameters of GraphIT and GraphEM are fine-tuned through a grid-search strategy to minimize the RMSE on a single realization.

The results are summarized in Table 2. MLEM does not include sparsity prior on A, which explains its poor performance, especially in terms of edge detectability. GraphEM and GraphIT both reach better scores than MLEM. It is noticeable that, the sparser the graph (i.e., the smaller SS), the better results for GraphIT. The superiority of GraphIT over its competitors on all datasets is remarkable both in terms of RMSE and detection metrics. In particular, despite integrating a sparsifying ℓ1\ell_1 penalty in its estimator, GraphEM struggles for very sparse graphs, leading to an increase in RMSE and a lowered accuracy. In contrast, GraphIT performs well for all metrics. When the level of sparsity decreases (i.e., SS increases), both GraphEM and GraphIT tend to perform similarly. We also include in the last column of Table 2, the averaged computing times over 50 realizations for each methods. All methods take a similar running time (code is run in Matlab 2021a on an 11th Gen Intel(R) Core(TM) i7-1185G7 3.00GHz with 32 Go RAM).

(Nx,S)(N_x,S)methodRMSEaccur.F1Time (s.)
(8,4)GraphIT0.1850.9640.7761.523
GraphEM0.2440.9200.6351.186
MLEM0.4010.0630.1181.862
(8,8)GraphIT0.1610.9760.9011.907
GraphEM0.2140.9360.7843.467
MLEM0.3450.1250.2221.774
(8,16)GraphIT0.1900.9310.8611.663
GraphEM0.1940.8650.7723.506
MLEM0.2480.2500.4002.040
(16,4)GraphIT0.2340.9900.7494.218
GraphEM0.3250.9280.3024.185
MLEM0.7920.0160.0314.741
(16,8)GraphIT0.2570.9870.8084.005
GraphEM0.3220.9070.4033.916
MLEM0.6500.0310.0613.964
(16,16)GraphIT0.3500.9590.6064.393
GraphEM0.3620.9050.4945.572
MLEM0.7100.0630.1183.129

Table 2. Results and computing times for GraphIT, GraphEM, and MLEM.

We finally display two examples of graph reconstruction in Figure 2. We compare the true graph (left), with GraphEM (middle) and GraphIT (right) estimates in both setups, i.e., (Nx,S)=(8,16)(N_x,S) = (8,16) (top) and (Nx,S)=(16,16)(N_x,S) = (16,16) (bottom). We can see the superior ability of GraphIT to recover the graphs shape and weights in the case of two sparse graphs.

True graph, GraphEM, and GraphIT estimates for two sparse graphs

Figure 2. True graph (left), GraphEM (middle), and GraphIT (right) estimates for (Nx,S)=(8,16)(N_x,S) = (8,16) (top) and (Nx,S)=(16,16)(N_x,S) = (16,16) (bottom).

Conclusion

In this paper, we have proposed GraphIT, an MM algorithm for the estimation of a sparse transition matrix describing hidden state interactions in an LG-SSM. A family of non-convex regularization term is considered to enforce the sparsity of the sought matrix, here interpreted as related to the adjacency matrix of a directed graph. The novel method exploits majorization properties inherited from both the EM framework and the iterated reweighted ℓ1\ell_1 methodology. The resulting convex upper bounds can be efficiently minimized through a proximal splitting solver. Through numerical results on controlled scenarios, we illustrate the great ability of the method to properly retrieve sparse transition matrices.

References

  1. [1]M. Eichler, “Graphical modelling of multivariate time series,” Probability Theory and Related Fields, vol. 153, no. 1, pp. 233–268, Jun. 2012.
  2. [2]F. R. Bach and M. I. Jordan, “Learning graphical models for stationary time series,” IEEE Transactions on Signal Processing, vol. 52, no. 8, pp. 2189–2199, Aug. 2004.DOI
  3. [3]D. Barber and A. T. Cemgil, “Graphical models for time-series,” IEEE Signal Processing Magazine, vol. 27, no. 6, pp. 18–28, Nov 2010.DOI
  4. [4]V. N. Ioannidis, Y. Shen, and G. B. Giannakis, “Semi-blind inference of topologies and dynamical processes over dynamic graphs,” IEEE Transactions on Signal Processing, vol. 67, no. 9, pp. 2263–2274, 2019.DOI
  5. [5]E. Chouzenoux and V. Elvira, “GraphEM: EM algorithm for blind Kalman filtering under graphical sparsity constraints,” in Proceedings of the 45th IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2020), 4–8 May 2020, pp. 5840–5844.arxiv.org/abs/2001.03195
  6. [6]V. Elvira and E. Chouzenoux, “Graphical inference in linear-Gaussian state-space models,” IEEE Transactions on Signal Processing, vol. 70, pp. 4757–4771, 2022.DOI
  7. [7]B. Cox and V. Elvira, “Parameter estimation in sparse linear-Gaussian state-space models via reversible jump Markov Chain Monte Carlo,” in Proceedings of the 30th European Signal Processing Conference (EUSIPCO 2022). IEEE, 2022, pp. 797–801.
  8. [8]B. Cox and V. Elvira, “Sparse Bayesian estimation of parameters in linear-gaussian state-space models,” IEEE Transactions on Signal Processing (to appear in), 2023.DOI
  9. [9]A. Pirayre, C. Couprie, L. Duval, and J.-C. Pesquet, “BRANE Clust: Cluster-assisted gene regulatory network inference refinement,” IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 15, no. 3, pp. 850–860, May 2018.DOI
  10. [10]D. Luengo, G. Rios-Munoz, V. Elvira, C. Sanchez, and A. Artes-Rodriguez, “Hierarchical algorithms for causality retrieval in atrial fibrillation intracavitary electrograms,” IEEE Journal of Biomedical and Health Informatics, vol. 12, no. 1, pp. 143–155, Jan. 2019.DOI
  11. [11]C. Ravazzi, R. Tempo, and F. Dabbene, “Learning influence structure in sparse social networks,” IEEE Transactions on Control of Network Systems, vol. PP, pp. 1–1, 12 2017.DOI
  12. [12]J. Richiardi, S. Achard, B. Horst, , and D. V. D. Ville, “Machine learning with brain graphs,” IEEE Signal Processing Magazine, vol. 30, no. 3, pp. 58–70, 2013.
  13. [13]J. Chiu, Y. Deng, and A. M. Rush, “Low-rank constraints for fast inference in structured models,” in Advances in Neural Information Processing Systems, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, Eds., 2021.arxiv.org/abs/2201.02715
  14. [14]S. Roweis and Z. Ghahramani, “A unifying review of linear Gaussian models,” Neural Computation, vol. 11, pp. 305–345, 1999.pubmed.ncbi.nlm.nih.gov/9950734
  15. [15]Z. Ghahramani and G. Hinton, “Parameter estimation for linear dynamic systems,” Tech. Rep., University of Toronto, 1996, http://mlg.eng.cam.ac.uk/zoubin/course04/tr-96-2.pdf.
  16. [16]R. H. Shumway and D. S. Stoffer, “An approach to time series smoothing and forecasting using the EM algorithm,” Journal of Time Series Analysis, vol. 3, no. 4, pp. 253–264, 1982.DOI
  17. [17]O. Cappe, E. Moulines, and T. Ridden, Inference in Hidden Markov Models, Springer Series in Statistics. Springer New York, NY, 1st edition, 2005.DOI
  18. [18]J. Fan and R. Li, “Variable selection via nonconcave penalized likelihood and its oracle properties,” Journal of the American Statistical Association, vol. 96, pp. 1383–1360, 2001.
  19. [19]C.-H. Zhang, “Nearly unbiased variable selection under minimax concave penalty,” The Annals of Statistics, pp. 894–942, 2010.DOI
  20. [20]E. Soubies, L. Blanc-Féraud, and G. Aubert, “A continuous exact l0 penalty (celo) for least-squares regularized problem,” SIAM Journal on Imaging Science, , no. 3, pp. 1574–1606, 2015.
  21. [21]J. Ying, J. de Miranda Cardoso, and D. P. Palomar, “Nonconvex sparse graph learning under Laplacian constrained graphical model,” in Advances in Neural Information Processing Systems, 2020.
  22. [22]J. de Miranda Cardoso, J. Ying, and D. Palomar, “Graphical models in heavy-tailed markov-tiled markov,” in Advances in Neural Information Processing Systems. 2021, vol. 34, pp. 19989–20001, Curran Associates, Inc.
  23. [23]D. Williams, “Beyond Lasso: a survey of nonconvex regularization in Gaussian graphical models,” Tech. Rep., 2020, https://psyarxiv.com/ad57p/.
  24. [24]D. Wipf and S. Nagarajan, “Iterative reweighted ℓ1 and ℓ2 methods for finding sparse solutions,” IEEE Journal of Selected Topics in Signal Processing, vol. 4, no. 2, pp. 317–329, 2010.
  25. [25]P. Huber, Robust Statistics, Wiley, 2nd edition, 2009.
  26. [26]Y. Sun, P. Babu, and D. P. Palomar, “Majorization-minimization algorithms in signal processing, communications, and machine learning,” IEEE Transactions on Signal Processing, vol. 65, no. 3, pp. 794–816, 2017.DOI
  27. [27]I. Daubechies, R. DeVore, M. Fornasier, and C. Gunturk, “Iteratively reweighted least squares minimization for sparse recovery,” Communications on Pure and Applied Mathematics, vol. 63, no. 1, pp. 1–38, 2009.DOI
  28. [28]R. Chartrand and Y. Wotao, “Iteratively reweighted algorithms for compressive sensing,” in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP 2008), 2008, pp. 3869–3872.DOI
  29. [29]P. Ochs, A. Dosovitskiy, T. Brox, and T. Pock, “On iteratively reweighted algorithms for nonsmooth nonconvex optimization in computer vision,” SIAM Journal on Imaging Sciences, vol. 8, no. 1, pp. 331–372, 2015.DOI
  30. [30]R. E. Carrillo, J. D. McEwen, and Y. Wiaux, “Sparsity Averaging Reweighted Analysis (SARA): a novel algorithm for radio-interferometric imaging,” Monthly Notices of the Royal Astronomical Society, vol. 426, no. 2, pp. 1223–1234, 10 2012.
  31. [31]Q. Sun, K. M. Tan, H. Liu, and T. Zhang, “Graphical nonconvex optimization via an adaptive convex relaxation,” in Proceedings of International Conference on Machine Learning (ICML 2018), 2018.
  32. [32]J. Ying, J. V. d. M. Cardoso, and D. P. Palomar, “Does the ℓ1-norm learn a sparse graph under Laplacian constrained graphical models?,” Tech. Rep., 2020, https://arxiv.org/abs/2006.14925.
  33. [33]R. E. Kalman, “A new approach to linear filtering and prediction problems,” Journal of Basic Engineering, vol. 82, pp. 35–45, 1960.DOI
  34. [34]S. Sharma, V. Elvira, E. Chouzenoux, and A. Majumdar, “Recurrent dictionary learning for state-space models with an application in stock forecasting,” Neurocomputing, vol. 450, pp. 1–13, 2021.DOI
  35. [35]S. Sharma, A. Majumdar, V. Elvira, and E. Chouzenoux, “Blind kalman filtering for short-term load forecasting,” IEEE Transactions on Power Systems, vol. 35, no. 6, pp. 4916–4919, 2020.DOI
  36. [36]S. Särkkä, Bayesian Filtering and Smoothing, 3 edition, 2013.
  37. [37]G. Gasso, A. Rakotomamonjy, and S. Canu, “Recovering sparse signals with a certain family of nonconvex penalties and dc programming,” IEEE Transactions on Signal Processing, vol. 57, no. 12, pp. 4686–4698, 2009.DOI
  38. [38]X. Pan, Q. Sun, and W.-X. Zhou, “Iteratively reweighted ℓ1-penalized robust regression,” Electronic Journal of Statistics, vol. 15, no. 1, pp. 3287–3348, 2021.DOI
  39. [39]H. Zou and R. Li, “One-step sparse estimates in nonconcave penalized likelihood models,” Annals of Statistics, vol. 36, pp. 1509–1533, 2008.
  40. [40]P. L. Combettes and J.-C. Pesquet, “Fixed point strategies in data science,” IEEE Transactions on Signal Processing, vol. 69, pp. 3878–3905, 2021.DOI
  41. [41]I. Daubechies, M. Defrise, and C. De Mol, “An iterative thresholding algorithm for linear inverse problems with a sparsity constraint,” Communications on Pure and Applied Mathematics, vol. 57, no. 11, pp. 1413–1457, 2004.arxiv.org/abs/math/0307152
  42. [42]A. Beck and M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems,” SIAM Journal on Imaging Sciences, vol. 2, no. 1, pp. 183–202, 2009.DOI
  43. [43]P. Combettes and J. Pesquet, “A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery,” IEEE Journal of Selected Topics in Signal Processing, vol. 1, no. 4, pp. 564–574, Dec. 2007.DOI

Paper details

vlnc:W_wykrtdtp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 6

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents