Nicolas Martin
email: nicolas.martin@gipsa-lab.fr

Fellow, IEEE Carlos Canudas-De-Wit
email: carlos.canudas-de-wit@gipsa-lab.fr

Subgraph detection for average detectability of LTI systems

Keywords: Network systems, Regular induced subgraph, Observability, Detectability, Network epidemics !

Observation and detection of network systems aim to reconstruct the evolution of the dynamical system based on the measurement of few nodes. In large-scale networks, reconstructing the exact state of each node becomes harduous and is often superfluous in practice, since reconstructing an aggregated version of the system can be sufficient. In the light of this observation, we consider the notion of average detectability: a system is said to be average detectable if it is possible to reconstruct the average of the subset of its unmeasured nodes. We show here that for a particular type of network systems, that is, negative uniform networks, the average detectability property is satisfied when the subgraph induced by the unmeasured nodes is regular. Next, we introduce the relaxed notion of quasi-regularity, which ensures an approximate reconstruction of the average. Motivated by these results, we design algorithms to detect regular induced subgraphs (RIS) and quasi-regular induced subgraph (q-RIS). We also propose an extension to detect multiple quasi-regular induced subgraphs (mq-RIS) that is meant to reconstruct the average of several subgraphs of the system. Finally, we apply our method to the estimation of a linearized SIS model of epidemic diffusion that takes place over a simulated contact network between the largest cities of France.

INTRODUCTION

In the study of dynamical systems over networks, observation problems aims to reconstruct the state of the whole system by knowing only a fraction of the states [START_REF] Wu | Network observability: theory[END_REF]. This subject has been widely studied and has raised the question of the choice of the measured nodes to improve the reconstruction [START_REF] Gou | An improved measurement placement algorithm for network observability[END_REF], [START_REF] Xin | Algorithm research for selecting measurement nodes in measuring network traffic based on adjacency matrix[END_REF], [START_REF] Iudice | On node controllability and observability in complex dynamical networks[END_REF]. While this issue has been solved in some cases, in large-scale networks we often have to leverage a limited number of sensors. Taking into account this complexity and the cost of sensors, it is often difficult to reconstruct the state of a large-scale network. In the past decades, several graph-theoretical approaches for controllability and observability of network systems have been proposed [START_REF] Liu | Controllability of complex networks[END_REF], [START_REF] Notarstefano | Controllability and observability of grid graphs via reduction and symmetries[END_REF], [START_REF] Rahmani | Controllability of multi-agent systems from a graph-theoretic perspective[END_REF], [START_REF] Ji | Observability and estimation in distributed sensor networks[END_REF]. Most of these works aim to reconstruct or to control the whole state of the systems. However in numerous cases, there is no need to reconstruct the state of each node, but only an aggregation of these states. Recently, Niazi et al. [START_REF] Niazi | Average observability of large-scale network systems[END_REF], [START_REF] Niazi | Scale-free estimation of the average state in large-scale systems[END_REF] took advantage of this observation and proposed the notions of average observability and average detectability. These notions refer to the reconstruction of the average state of the unmeasured nodes respectively in closed-loop and in open-loop. In particular, in an average detectable system, it is possible to design an open-loop observer estimating the average of the unmeasured nodes such that the error converges to zero. In the following, we will only focus on this latter notion. In [START_REF] Niazi | Average observability of large-scale network systems[END_REF] the authors propose a sufficient condition for average detectability, which allows testing if a given network and a given subset of measured nodes form an average detectable system. If it is possible to choose the placement of the measured nodes, a question emerges: given a network system what is the smallest subset of measured nodes fulfilling the average detectability condition? Said otherwise, what is the smallest subset of nodes to observe in order to be able to reconstruct the average of the unmeasured nodes? This is the question we address through this article.

In order to transform the condition for average detectability into a structural condition, we will restrict ourselves to a particular type of system: negative uniform graphs. With such system, when a subgraph of unmeasured nodes forms a regular graph 1 , then the system is average detectable. Hence, our problem becomes detecting the largest regular induced subgraph (RIS) out of a given graph. The question of finding induced subgraphs with particular properties has been addressed in several works. For example, we can cite the maximum clique problem [START_REF] Bomze | The maximum clique problem[END_REF] which has implications, in particular, in social networks; Frequent subtree mining [START_REF] Chi | Frequent subtree miningan overview[END_REF] which is applied to data analysis; Induced subgraph isomorphism problem [START_REF] Sysł | The subgraph isomorphism problem for outerplanar graphs[END_REF] or its variant as Snake-in-the-box problem or the maximum independent set problem. In most cases, these problems are either oriented to data analysis or are graphtheoretic problems with no direct application. To our knowledge, the present work is the first to use an induced subgraph problem for a reconstruction concern. As said, here the objective is also to detect subgraph with a particular property which is regularity. The regular subgraph detection have been studied in different contexts and after introducing this property, we propose a brief review of the works in this domain in Section 2.

However, the regular induced subgraph detection raises some difficulties: first, the hypothesis on the system are very restrictive and concern few real systems. Moreover the problem is known to be NP-hard and so it is not scalable. Finally the solution found implies often to measure a large proportion of nodes. Therefore, in Section 3, we relax the problem by introducing the notion of quasiregularity, which qualifies a graph which is close to be regular. We derive then a result linking the error of regularity and the error of reconstruction: the more regular the unmeasured subgraph is, the better is the reconstruction. On these grounds, we treat the problem of quasi-regular induced subgraph detection (q-RIS). We also extend the results, and the algorithm, to multiple quasi-regular induced subgraph (mq-RIS). Finally, in Section 4 we present an application of the mq-RIS approach on an example of epidemic spreading.

Systems and graphs

In this article we will consider a directed graph G = (V, E), where V = {v 1 , v 2 , . . . , v n } is the set of nodes and E ∈ V × V is the set of directed edges. Set N out (v) contains the out-neighbors of node v and its cardinality deg out (v) is the outdegree of v. The graph can be represented by its weighted adjacency matrix A ∈ R n×n , whose ij-th entry is given by

A ij = a ij if (v i , v j ) ∈ E 0 otherwise (1)
where a ij is the weight of edge

(v i , v j ) ∈ E: node v i is influenced by v j if a ij = 0.
We associate to this graph a linear time-invariant (LTI) network system

Σ : ẋ(t) = Ax(t) + Bu(t) y(t) = Cx(t) , (2)
where A is the graph adjacency matrix,

x(t) = [ x 1 (t), . . . , x n (t) ]
T is a state vector, u(t) = [ u 1 (t), . . . , u p (t) ] T is an input vector, and y = [ x 1 (t), . . . , x k (t) ] T an output vector that contains a sample of k components of the state vector x (so that C = I k 0 ). The nodes V 1 := {v 1 , . . . , v k } are called the measured nodes while V 2 := {v k+1 , . . . , v n } are the unmeasured nodes. We denote m the number of unmeasured nodes: m = n -k. We also denote by x 2 (t) = [ x k+1 (t), . . . , x m (t) ] T the states of unmeasured nodes and by x av 2 the average value of the unmeasured nodes:

x av 2 = 1 m 1 T x 2 (3)
Correspondingly, we decompose the matrices A and B as follows:

A = A 11 A 12 A 21 A 22 , B = B 1 B 2 . ( 4
)
With A 11 ∈ R k×k , A 22 ∈ R m×m and all the other block matrices of corresponding dimensions. We denote by σ the deviation vector defined as:

σ = x 2 -1x av 2 =      x k+1 -x av 2 x k+2 -x av 2 . . . x n -x av 2      (5)
This vector contains the difference between the value of each unmeasured nodes and the average value of the unmeasured nodes.

We have 1 T σ = 0. The evolution of x av 2 is described by the following equation:

ẋav 2 (t) = αx av 2 (t) + gy(t) + bu(t) + ησ(t) (6)
with

α = 1 m 1 T A 22 1, g = 1 m 1 T A 21 , b = 1 m 1 T B 2 and η = 1 m 1 T A 22 .
In our analysis of system (2), we shall from now on make the following standing assumptions: matrix A is Hurwitz stable and the input u is bounded.

EXACT AVERAGE DETECTABILITY

Our estimation objective is estimating the average state of the unmeasured nodes. More precisely, system Σ with a subset V 1 of measured nodes is said to be average observable if there exists a scalar observer xav 2 that converges to the true average:

lim t→∞ |x av 2 (t) -x av 2 (t)| = 0.
In order to verify this property, we choose to make use of the following scalar observer

ẋav 2 = αx av 2 + gy(t) + bu(t). (7)
In the following, we first exhibit a sufficient condition for average detectability. We will then introduce a special class of systems, for which finding a subgraph V 1 that ensures average detectability amounts to finding a regular induced subgraph. This fact will lead us to investigate the problem of finding large regular induced subgraphs in a graph.

In order to introduce the condition for average detectability we first define a graph-based notion.

Definition 1 (Outflow balanced graph). Let G be a directed weighted graph represented by its adjacency matrix A. G is said to be outflow balanced if the sum of the weights of the outgoing edges is the same for every nodes, which is :

∃ γ ∈ R, 1 T A = γ1 T . ( 8
)
If moreover γ < 0, then the graph is said to be negatively outflow balanced.

This definition provides a simple sufficient condition for average detectability.

Proposition 1 (Sufficient condition for average detectability). Consider system Σ associated to the graph G and denote by G V2 the subgraph of G induced by the subset of unmeasured nodes. If G V2 is negatively outflow balanced, then system Σ is average detectable.

Proof. Even though this result can be derived as a consequence of the theory in [START_REF] Niazi | Average observability of large-scale network systems[END_REF], [START_REF] Niazi | Scale-free estimation of the average state in large-scale systems[END_REF], we prefer to include a self-contained proof, which is instructive and will inspire our results in Section 3.

Let xav 2 = x av 2 -xav 2 be the reconstruction error. By combining ( 6) and [START_REF] Rahmani | Controllability of multi-agent systems from a graph-theoretic perspective[END_REF], the error dynamics reads

ẋav 2 = 1 m 1 T A 22 1 xav 2 + 1 m 1 T A 22 σ(t).
By the assumption 1 T A = γ1 T and since 1 T σ(t) = 0, the dynamics simplifies to ẋav 2 = γ xav 2 , which is asymptotically stable. This result implies that, if the set of nodes can be partitioned into two subsets such that one induced subgraph is negatively outflow balanced, then measuring the nodes outside this subgraph makes the system average detectable. Figure 1 gives an example of such a system.

v 1 v 2 v 3 v 4 v 5 -3 -1 -1 1 1 -3 -4 2 -2
Fig. 1. By measuring the node v 2 , the unmeasured nodes V 2 = {v 1 , v 3 , v 4 , v 5 } induce a negatively outflow balanced G V 2 with γ = -2. Thus, the system is average detectable.

Regular Induced Subgraph detection

Motivated by Proposition 1, we shall consider the following problem.

Problem 1 (Negatively outflow balanced induced subgraph detection). In a given graph G, find the largest induced subgraph of G which is negatively outflow balanced.

However, in an arbitrary graph with independent weights there is, almost surely, no outflow balanced subgraph. That being said, two approaches can be considered: either we restrict ourselves to particular systems for which we know that negatively outflow balanced subgraphs can be found, or we relax the notion of average detectability and hence the notion of regularity. The latter solution will be explored in Section 3 where we introduce the notion of quasi-regularity. In the remainder of this section, we focus on the first solution: we treat the problem for a particular type of systems: the negative uniform graphs defined hereafter.

Definition 2 (Negative uniform graph: NUG). A graph G, represented by the adjacency matrix A, is said to be negative uniform if all its non-zero weights are equal and negative, which is A ij ∈ {0; a} with a < 0.

Given this definition, the following fact is immediate.

Proposition 2 (Sufficient condition for average detectability of negative uniform graph). Let Σ be a system associated to a negative uniform graph G. Σ is average detectable if G V2 is regular.

Remark 1. While negative uniform graph is a quite restrictive case, we can also consider positive uniform graph with a same negative self-loop η. Indeed in this case, we have 1 T A = a deg out -η1, and even with a > 0 the right side can be negative if the selfloop η is large enough. Proposition 2 remains true if the system is associated with such a graph. This type of graphs includes for example some heat systems with high dissipation [START_REF] Imane | Discrete linear functional observer for the thermal estimation in power modules[END_REF]. The model presented in section 4 falls also in this sclope. In the following, we only consider negative uniform graph for the simplicity of the development.

We can now formulate the problem arising from Problem 1 restricted to the negative uniform graphs case.

Problem 2 (Regular induced subgraph detection). Let G be a negative uniform graph. We look for the largest regular induced (b) The system is excited with sinusoidal inputs. The thin lines are the states of the unmeasured nodes (the highlighted regular subgraph) and the thick blue line their average. The thick red line is the state of observer [START_REF] Rahmani | Controllability of multi-agent systems from a graph-theoretic perspective[END_REF], which converges to the average value. subgraph (RIS) of G, which is:

max I⊂V |I|, s.t. G I is regular. (9)
where G I is the subgraph of G induced by the subset of nodes I.

By measuring the nodes outside the subgraph solution of Problem 2, we obtain an average detectable system. Figure 2 illustrates this problem.

Solving Problem 2 can benefit from the extended literature on the k-regular induced subgraph (or k-RIS) problem, which differs from Problem 2 in fixing the desired degree k.

• Complexity of the k-RIS problem: A first work [START_REF] Lovász | On the Shannon capacity of a graph[END_REF] showed that the problem in the case k = 0 is NPhard. Then several works [START_REF] Cardoso | Maximum k-regular induced subgraphs[END_REF], [START_REF] Asahiro | Complexity of finding maximum regular induced subgraphs with prescribed degree[END_REF] generalized the result for any k and different type of graphs. Even though its complexity is polynomial for some particular types of graphs [START_REF] Lozin | Maximum regular induced subgraphs in 2p3free graphs[END_REF], [START_REF] Kobler | Finding maximum induced matchings in subclasses of claw-free andp 5-free graphs, and in graphs with matching and induced matchingof equal maximum size[END_REF], the k-RIS problem is also hard to approximate [START_REF] Asahiro | Inapproximability of maximum rregular induced connected subgraph problems[END_REF].

• Algorithms for the k-RIS problem: For k = 0, [START_REF] Fomin | Measure and conquer: a simple o(20.288n) independent set algorithm[END_REF], [START_REF] Robson | Algorithms for maximum independent sets[END_REF] propose fast-exponential algorithms (i.e. in O(c n ) with c ≤ 2). For any k, a fast-exponential algorithm based on a branch-and-bound approach is proposed in [START_REF] Gupta | Fast exponential algorithms for maximum r-regular induced subgraph problems[END_REF] and a polynomial algorithm for a particular type of graphs in [START_REF] Agra | The k-regular induced subgraph problem[END_REF]. However these results consider undirected graph and standard regularity (not out-regularity as we need here). Still, the branch-and-bound approach proposed in [START_REF] Gupta | Fast exponential algorithms for maximum r-regular induced subgraph problems[END_REF] can be extended to our case and will be presented later.

• Upper bounds on the size of the largest k-RIS: Facing the complexity of the problem, it is interesting to obtain an upper bound on the size of the optimal solution. An intuitive upper bound on the size of the largest k-RIS is the size of the k-Core of the graph. The k-Core is a subgraph obtained by iteratively removing nodes with a degree smaller than k: since a k-Core is a subgraph in which all vertices have degree at least k, we have that k-RIS(G) ⊂ k-Core(G). More refined upper bounds have been proposed for any k [START_REF] Cardoso | Maximum k-regular induced subgraphs[END_REF], [START_REF] Luz | Improving an upper bound on the size of k-regular induced subgraphs[END_REF] or for particular values of k [START_REF] Lovász | On the Shannon capacity of a graph[END_REF], [START_REF]An upper bound on the independence number of a graph computable in polynomial-time[END_REF]. These insights will be the basis for our approach to RIS, which we elaborate next.

An algorithm for the RIS problem

As discussed in the previous section, the literature proposes only methods to find the largest k-regular induced subgraph but nothing to solve the problem for every k. A simple approach consists in solving the problem for each k and then keeping the best solution:

We denote RIS(G) and k-RIS(G) respectively, the largest regular and k-regular induced subgraphs of G. We have then:

RIS(G) = max k∈N k-RIS(G) (10)
Some tricks can be used to optimize the approach:

• As seen in the previous section, there are some methods allowing to find an upper bound on k-RIS(G). We denote this upper bound by θ k (G). While testing the value of k-RIS(G) for every k, if θ k0 (G) is smaller than the largest k-RIS(G) so far, it is useless to compute k 0 -RIS(G). Noticing that the computation of this upper bound is faster by far than the computation of the k-RIS(G), this helps the computation of the regular induced subgraph.

•

The cases with k = 0 and k = 1 are particular and a specific algorithm can be applied.

• Using an approximate algorithm for the k-RIS would imply a sub-optimal solution for the RIS which can be interesting if the approximation is good.

Based on these remarks, we propose Algorithm 1 to detect the largest regular induced subgraph within a given graph.

θ k = UpperBound k-RIS(k, G) 4: if θ k > | RIS | then 5: k-RIS = Find k-RIS(k, G) 6: RIS = max(RIS, k-RIS) 7:
end if 8: end for Ensure: RIS This is actually a meta-algorithm as we only give the skeleton of the method and not the sub-algorithms UpperBound k-RIS and Find k-RIS. The choice of these sub-algorithm is discussed hereafter.

Our choice for the first sub-algorithm Upper-Bound k-RIS(k, G) is computing the k-Core, as detailed in Algorithm 2.

Algorithm 2 k-Core Require: G, k 1: I ← Nodes in G with out-degree < k 2: while I is not empty do 3:

Remove I from G

4:

I ← Nodes in G with out-degree < k 5: end while 6: θ k ← number of nodes in G Ensure: θ k an upper bound on the size of the k-RIS

The second sub-algorithm Find k-RIS(k, G) is described in Algorithm 3. It is an extension of the branch-and-bound approach proposed in [START_REF] Gupta | Fast exponential algorithms for maximum r-regular induced subgraph problems[END_REF]. It is a recursive algorithm designed as follows: Given a graph G and a degree k, we first compute the k-Core of G (line 1). If the graph obtained is k-regular then the k-RIS is found (line 3) and the algorithm terminates. Otherwise there is at least one node, denoted r, with a degree larger than k (line 5). It is clear that either r is not in the k-RIS either (at least) one of its successors is not (line 6). Thus, we consider the subgraphs obtained by removing r or a successor of r (line 8). Finally we compute the k-RIS for each of them (line 9) and select the largest one (line 11).

Algorithm 3 k-RIS Require: G, k 1: G ← k-Core(G, k) 2: if G is k-regular then 3: k-RIS ← G 4: else 5:
r ← a node of G with degree > k 6: 3 presents a result obtained with Algorithm 1 (and Algorithms 2-3). Considering that the graph is negative uniform, the system is average detectable by measuring the 8 nodes outside of the red subgraph.

I ← N out (r) ∪ r 7: for i ∈ I do 8: G tmp ← remove i in G 9: k-RIS tmp {i} = k-RIS(G tmp , k) 10: end for 11: k-RIS = max(k-RIS tmp ) 12: end if Ensure: k-RIS Simulation 1. Figure

Discussion

The approach we have taken so far suffers from some limitations, which we summarize below:

• Negative uniform systems, which motivate our search for RIS, are rare. Even if we consider positive uniform systems with large negative self-loop, as discussed in Remark 1, the applications are limited (see Section 4 for an example). The upper bound (k-Core) is displayed in blue for k ∈ {1; 2; 3; 4}. Black dots are the real size of k-RIS for k ∈ {1; 2; 3}: 4-RIS is not computed, as σ(4) < |3-RIS|. The red dotted line shows the size of the RIS.

• RIS is a fragile notion: for example, a grid graph is very close to regular (only the nodes on the border have a smaller degree) but does not fulfill the definition.

•

The RIS problem is hard to solve: there is no specific method for the RIS problem besides solving multiple NP-hard k-RIS problems.

•

The largest RIS in a graph is often very small, and suboptimal heuristics return even smaller subgraphs.

Therefore, the RIS detection approach introduced in this section is difficult to apply to real-world problems. This fact motivates the question whether it is possible to accept some error on the regularity while preserving an efficient reconstruction of the average. To this purpose, in the next section we introduce the notion of quasi-regularity.

APPROXIMATE AVERAGE DETECTABILITY

In Proposition 1, the sufficient condition for average detectability was 1 T A 22 = γ1 T with γ < 0: in order to relax the problem, we consider now that this equality is no longer verified. Recalling (8), we define

γ = 1 m 1 T A 22 1,
and we introduce a degree perturbation vector

s T = 1 T A 22 -γ1 T
and a regularity error

= s 1 m|γ| . ( 11
)
The following proposition extends Proposition 1 and provides a relation between this regularity error and the reconstruction error, defined as e ss = lim sup

t→∞ |x av 2 -xav 2 |. ( 12
)
Proposition 3 (Regularity and reconstruction errors). If γ < 0, then the reconstruction and regularity errors satisfy

e ss ≤ max i σi 1 - , (13)
where σi = lim sup

t→∞ |σ i (t)|.
Proof. As in the proof of Proposition 1, we denote by xav 2 := x av 2 -xav 2 the reconstruction error. From equations ( 6) and ( 7) we have then:

ẋav 2 (t) = αx av 2 (t) + ησ(t) (14)
where σ defined in ( 5) is the deviation from average,

α = 1 m 1 T A 22 1 = 1 m (γ1 T + s T )1 = γ + 1 m s T 1
and, since 1 T σ(t) = 0,

ησ(t) = 1 m 1 T A 22 σ(t) = 1 m (γ1 T + s T )σ(t) = 1 m s T σ(t).
Therefore, ( 14) becomes

ẋav 2 (t) = (γ + 1 m s T 1)x av 2 (t) + 1 m s T σ(t),
which is a stable dynamics by virtue of γ < 0. Since A is stable, σ(t) is bounded in magnitude and

lim sup t→∞ xav 2 ≤ - 1 m |s T σ| γ + 1 m s T 1 . ( 15
)
Finally,

- 1 m |s T σ| γ + 1 m s T 1 = |s T σ| m|γ| -s T 1 ≤ |s T σ| |mγ| -|s T 1| ≤ s 1 max i σi m|γ| -s 1
and ( 13) follows from the definition of in [START_REF] Bomze | The maximum clique problem[END_REF].

According to Proposition 3, in order to keep the reconstruction error, it is interesting to find a subgraph having small regularity error . Relation ( 13) is supported by simulations in the following section.

Remark 2. As the reconstruction error e ss grows with the regularity error , it actually grows with the absolute error of regularity s 1 and decreases with the degree of regularity γ and the size of the unobserved subgraph m. This means that the reconstruction will be better if the subgraph of unmeasured nodes is large, close to be regular and with a large degree of regularity.

On the link between regularity error and reconstruction error

Before investigating the q-RIS detection problem, we present some simulations enlightening the relation described in Proposition 3. To this end, we first introduce a family of graphs for which we can control the regularity. Definition 3 (p-reg graph). Given a graph G, we denote N out (i) = {j, (j, i) ∈ E}, the set of successors of i. A graph is said p-reg if it verifies:

|N out (i)| = 1 if i is odd |N out (i)| = p if i is even (16)
Graphs of this family have the particularity to have one half of their nodes with out-degree 1 and the other half with out-degree p. In particular if p = 1, the graph is 1-regular (it is a cycle). By increasing the value of p, the regularity worsens as shown in fig. 4. In the following numerical simulations, we consider a series of graphs composed of a p-reg graph and one additional measured node as in fig. 5. By tuning the value of p we can modify the regularity of G V2 while preserving the shape of the system. The graph used in the experiment contains 101 nodes (100 nodes in the p-reg graph plus one extra node to measure). We add inputs

1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9
Fig. 5. A 2-reg graph as defined in Definition 3 with an additional node to observe. For the experiments, a similar graph is used with 100 nodes and p varying from 1 to 100.

into 10% of the nodes (randomly chosen) to persistently excite the system. These inputs are chosen as sine waves with gain, phase and frequency randomly chosen as:

∀ i ∈ [1, . . . , p], u i (t) = Λ sin(ωt + φ) (17)
with Λ ∈ [0.1, 10], ω ∈ [0.01, 1] and φ ∈ [0, 2π]. We compare the average value of the p-reg subgraph and the reconstructed value of this average for different value of p. The results are displayed in fig. 6. We notice that as predicted by Proposition 3 the error of reconstruction grows with the error of regularity. This simulation enlightens the fact that by minimizing the error of regularity we can reduce the error of reconstruction e ss .

Quasi-Regular Induced Subgraph detection

While detecting quasi-regular, if a small error is imposed on the regularity, the subgraph found might be small (and so the number of nodes to measure would be high). In the other hand, Proposition 3 ensures that the reconstruction would be better. Consequently, a compromise between the number of measure and the quality of the reconstruction has to be found. An interesting way to implement this compromise is by fixing a threshold for the error of regularity and then find the largest subgraph whose regularity error is lower than this threshold. This leads to the q-RIS detection problem defined hereafter. The error of reconstruction is then computed as the bias between the signal and the reconstruction at t = 1000 (which is a good approximation of ess). This emphasizes the link between the regularity of a subgraph and the ability to reconstruct its average.

Problem 3 (Quasi-regular induced subgraph detection). Let G be a graph and 0 > 0 a threshold for the quasi-regularity. We look for the largest quasi-regular subgraph of G, which is:

max I⊂V |I|, s.t. (G I ) < 0 (18)
where (G) is the regularity error (11) associated to G.

Note that this problem may have no feasible solution if is chosen to be too small. After this caveat, we present a beam search algorithm providing a sub-optimal solution to Problem 3. The principle of beam-search algorithms is as follows: A set of candidate solutions is considered as a seed, a set of solution deriving from these candidate is considered and the β most promising are memorized (β is called the beam width) and form the new set of candidate. The algorithm stops when a candidate solution is satisfying enough or when the new candidates are no more satisfying. In this latter case, the final solution is chosen among all the previous candidates. For the quasi-RIS detection the algorithm is described in Algorithm 4: We initialize the set of candidates with the singletons of each node (line 1). Then we iterate while one of the candidate has a regularity error smaller than the minimum accepted 0 (line 2) (see Remark 3 for a discussion on this point). At each iteration, new candidates are derived from the current candidates (line 4-5). These new candidates are all the subsets composed by one current candidate c and any other nodes of the subset S. Finally all these new candidates are united (line 7), the β best form the new candidates (line 8) and the best one is stored as quasi-RIS (line 9). By repeating this operation several times, the size of the candidates grows until none of the candidate have a regularity error small enough. At the end, the candidate with the smallest regularity error is chosen. Figure 7 illustrates this algorithm. Beam-search algorithms, like this one, are a type of greedy algorithm and hence do not provide an optimal solution. However the computation is relatively fast and the solutions found are rather good, as we will see.

Remark 3. In Algorithm 4 the while loop will stop if no candidate has a regularity error small enough. However, this condition is relatively strict as it is possible that it is not verified at some Here the beam width is β = 2, so at each step the best two candidates are kept (solid line). Two small modifications are made to make the example more readable: the seed is a single candidate while in the algorithm the seed is composed of the singletons of each node; the new candidates are the subsets composed of a previous candidate and a node neighboring this candidate, while the latter node can be arbitrary in the algorithm.

iteration but it will be verified in the future. Thus, a relaxed condition would be to stop if the the condition is violated several iterations in a row. Then the solution would be the last candidate verifying the condition. Remark 4. In Algorithm 4, the new candidates are chosen in a way that may induce a disconnected subgraph. However, for some applications the connectedness of the unobserved subgraph may be required. For example, when the network has a geographical nature (as an urban traffic network or an electrical grid), it is relevant to estimate the average of a geographical area. In this case, the algorithm can be adapted by changing line 4 with S ← N in (c) ∪ N out (c): Fig. 7 actually illustrates this variant. Clearly, a connectedness constraint entails some potential loss in the objective function: see [START_REF] Martin | The price of connectedness in graph partitioning problems[END_REF] for a related discussion. Simulation 2. Algorithm 4 does not enjoy any suboptimality bound: we therefore explore its performance by simulations. To this purpose, we construct irregular graphs that however contain a quasi-regular subgraph and test the ability of the algorithm to detect it. A representative example is presented in Fig. 8(ab), together with the average reconstruction corresponding to the subgraph in (a) in Fig. 8(b). In this simulation the parameters are 0 = 0.1 and β = 300, which means that at each step we conserve the 300 best candidates. We observe that the algorithm is able to identify correctly the optimal subgraph.

We have seen how to detect a regular or quasi-regular subgraph in order to estimate their average. We propose to generalize this approach, to detect several subgraphs and estimate different averages. The next section presents an extension of the current results to the multiple subgraphs case.

Multiple quasi-Regular Induced Subgraphs (mq-RIS)

In the previous problems we tried to find one regular or quasiregular subgraph in order to estimate its average. We wonder, now, to which extent it is possible to detect several regular or quasi-regular subgraphs and estimate their respective average. Considering the limitations posed by the regularity case evoked in section 2.3, we focus only on the quasi-regular problem. However a similar generalisation can be led for the regularity case. In the RIS and q-RIS problems we wanted to have the minimum number of nodes to measure leading to the minimisation problems 2 and 3.

Here again we have the same objective to minimize the number of measured nodes. Thus, we want to find disjoint quasi-regular induced subgraphs G I1 , . . . , G Im maximizing the cardinality of the union of all the subgraph. We denote I = [I 1 , . . . , I m ] the set of the subsets. Moreover these subgraphs can not share any successors, i.e. nodes outside the subgraph and pointed by a node of the subgraph. This is because the successors of a subgraph are measured to estimate the average value of the subgraph. If a node is pointed by two nodes belonging to two different subgraphs, the condition for the reconstruction does not hold (see [START_REF] Niazi | Average observability of large-scale network systems[END_REF]).

Problem 4 (Multi quasi-regular induced subgraph detection). Let G be a graph and 0 > 0 a threshold for quasi-regularity. We look for a set of quasi-regular subsets I minimizing the number of nodes to measure, which is:

max I=[I1,...,Im] j I j , s.t. ∀ i, (G Ii ) < 0 ∀ i, j, (I ∪ N out (I i )) ∩ (I j ∪ N out (I j )) = ∅ (19)
The second constraint translates the non-overlapping of the subgraphs and their successors. The quasi-RIS detection Algorithm 4 presented in the previous section can be extended almost straightforwardly to the multiple subgraphs case as follows: a first quasi-regular subgraph is detected, the subgraph and its neighborhood (which are the nodes to measure) are removed from the graph and the process is repeated with the new graph. To limit the number of nodes to measure it is interesting to limit the number of neighbors of the subgraph selected at each iteration. To this aim, we propose to find at each iteration the subgraph maximizing |I|/|N out (I)| i.e. the ratio between its size and the size of its neighborhood instead of the subgraph minimizing (G I ) in Algorithm 4.

The algorithm for multi quasi-RIS detection is described in Algorithm 5 where quasi-RIS refers to the algorithm 4 where line 9 has been replaced by

quasi-RIS = arg max c∈Ω, (Gc)< 0 |c| |N out (c)| (20)

Algorithm 5 Multi quasi-RIS detection

Require: G: graph with n nodes, 0 maximum acceptable error, β beam width, i max maximum number of subgraph detected 1: I = [] 2: I = quasi-RIS (G, 0 , β) 3: while I is not empty do I = quasi-RIS (G, 0 , β) 7: end while Ensure: I set of subsets inducing multiple quasi-RIS Simulation 3. We propose here a simulation of Algorithm 5 for the mq-RIS detection. To this end, we consider an initial graph (fig. 9) designed with five zones more regular than the average. This aims to test the capacity of the algorithm to detect regular subgraphs which are almost invisible to the naked-eye. The result of the simulation is displayed in fig. 10. In this case, the quasi-RIS Fig. 9. The initial graph is a grid with some irregularities making certain zones more regular. The algorithms aims to find these zones.

detection algorithm is applied five times before no more satisfying subgraphs can be found. At each step, we can see that the subgraph and its out-neighborhood found at the previous step is removed and the algorithm is applied to the remaining part of the graph.

APPLICATION TO NETWORK EPIDEMICS

In this last section we apply the mq-RIS algorithm to a real-world case: we consider the spreading of a disease over a contact network of the main cities in France and we aim to estimate the evolution of the proportion of infected people in different areas.

The epidemical model

Several models have been developed to capture the mechanisms of disease spreading, the most common ones are the so-called compartmental models. In these models, the population is divided in compartments representing the state (infected, susceptible, recovered, ...) of the individuals [START_REF] Van Mieghem | The n-intertwined SIS epidemic network model[END_REF], [START_REF] Mei | On the dynamics of deterministic epidemic propagation over networks[END_REF], [START_REF] Nowzari | Analysis and control of epidemics: A survey of spreading processes on complex networks[END_REF]. Moreover these type of models may have an underlying network structure. In this case, nodes represent individuals or group of individuals and edges represent interactions between individuals or between the groups. A state is assigned to each node and a dynamical equation describes the evolution in function of the state of the node, the state of its neighbors and the parameters of the disease. Among this network compartmental models, we consider here one of the most commonly used: the deterministic SIS model. In this model, individuals can be susceptible (S) or infected (I) and can pass from one state to another with a certain probability: as shown in fig. 11, an infected individual may recover with probability δ (the recovery rate) and a susceptible individual may be infected with probability β (the infection rate) scaled by the state of its neighborhood. If we define as p i (t) the probability of node i to be infected at time t, the SIS dynamics postulate ṗ(t) = (AB -∆)p(t) -P (t)ABp(t), p(0) = p 0 , [START_REF] Fomin | Measure and conquer: a simple o(20.288n) independent set algorithm[END_REF] where p = [p 1 , . . . , p n ] are the proportions of infected people in each group (and P = diag(p)), A is the adjacency matrix of the underlying network, B = diag(β 1 , . . . , β n ), ∆ = diag(δ 1 , . . . , δ n ) are the parameters of the epidemic and p 0 is the initial proportion of infected people in each group. In order (c) The second subgraph found and its successors are removed and the algorithm is applied again to detect a third subgraph (in blue).

(d) The graph obtained when merging the subgraphs obtained at each steps. By measuring the remaining nodes, the average of the subgraphs detected can be estimated. to use the approach developed before, we consider a linearized version [START_REF] Nowzari | Analysis and control of epidemics: A survey of spreading processes on complex networks[END_REF] of the dynamics in [START_REF] Fomin | Measure and conquer: a simple o(20.288n) independent set algorithm[END_REF]:

ṗ(t) = (AB -∆) A p(t), p(0) = p 0 (22)
It is apparent that this system is positively uniform with negative self-loop as discussed in Remark 1. In order to include sources of infection that are external to the population (such as travellers from contaminated areas), we define matrix B ∈ {0; 1} n×b to identify nodes that are in contact with a source of infection and function u(t) ∈ R b×1 to represent the temporal evolution of these sources of infection. By including these inputs u, the dynamics becomes ṗ(t) = Ap(t) + Bu(t), p(0) = p 0 .

It is clear how important it is to estimate the evolution of a disease, for instance in order to take appropriate sanitary measures or to study the efficiency of a treatment. As it is very costly to determine the state of each individual, one needs methods to reconstruct the spreading of the epidemic per areas and with relatively few measurements.

We propose here to use our approach to estimate the evolution of the proportion of infected people in different areas, by measuring the state of few groups. In order to construct a concrete example, we shall consider the above linearized SIS dynamics over a contact network beween the main French cities.

Case study: Construction of the graph

We consider a graph of interaction between groups of individuals at a country scale. The graph is structured at two different scales: a level within the cities and a level between cities. It is known that at the level of a city, individuals are strongly interconnected and tend to form clusters [START_REF] Boguná | Models of social networks based on social distance attachment[END_REF], [START_REF] Toivonen | A model for social networks[END_REF]. Here we use the Watts-Strogatz model [START_REF] Watts | Collective dynamics of small-world networks[END_REF] to capture the features of social networks. At the level of the country, there are fewer connections between groups of different cities and the number of connections between Parameters for the graph of interaction and the SIS model two cities is proportional to their number of inhabitants and inversely correlated to their distance. We generate such a network by considering twenty-two of the most populated cities in France (fig. 12). The details of the construction of the graph are given in table 1.

Simulation

Once the graph is obtained, we are ready to apply our algorithms. We begin by Algorithm 5, whose output is presented in Figure 13. The graph has been divided in 11 subgraphs containing 1112 nodes in total. Thus, only 292 nodes remains to measure which represents only 20.80% of the nodes. Some of the parts fit cities while others include a whole region. The figure gives also the regularity error , the number of nodes |V| and the mean degree k for each subgraph.

Next, since we have this partition where each subgraph is quasi-regular, it is possible to estimate the value of the average inside the subgraphs. We choose β = 0.05 and δ = 0.98 and we add 323 inputs which correspond to the sources of infection.The inputs are uniformly distributed in the territory and, as previously, are random sine waves. We use as initial conditions the situation presented in Fig. 14 and available on www.sentiweb.fr. Figure 15 shows the evolution of the proportion of infected individuals inside each subgraph and the estimation made with the openloop observer xav 2 described in [START_REF] Rahmani | Controllability of multi-agent systems from a graph-theoretic perspective[END_REF]. The solid lines are the actual averages while the dotted lines are the estimated average. Figure 16 shows the evolution of the absolute error for each subgraph. We observe that, as expected, the estimations errors decrease quickly and remain relatively small. However, as we did not find exact regular subgraphs, the system is not detectable and the error does not converge to zero. Instead there is a small residual error which is acceptable.

CONCLUSION

Based on the recently proposed notion of average detectability [START_REF] Niazi | Average observability of large-scale network systems[END_REF], [START_REF] Niazi | Scale-free estimation of the average state in large-scale systems[END_REF], we proposed three methods to choose which nodes to measure in order to estimate the average state of a system defined on a graph. Considering a particular type of system, the first method finds a regular induced subgraph to reach exact average detectability, i.e. the estimation of the average is asymptotically unbiased. Due to the limitation of this first problem, we proposed a relaxation: we focused on the detection of quasi-regular induced subgraph which results in an estimation of the average with a bias which depends on the quasi-regularity. The second method achieves this task. The third method allows to detect several quasiregular induced subgraphs to estimate the averages of different subsets of the system. Finally, we applied our tools to estimate the evolution of a disease spreading in a contact network in France.

  (a) Detecting a regular induced subgraph with out-degree 2 (highlighted).

Fig. 2 .

 2 Fig. 2. Illustration of the proposed approach: (a) from an initial negative uniform graph, a regular subgraph of unmeasured nodes is chosen; (b) the observer (7) is used to estimate the average value of the unmeasured nodes.

Algorithm 1

 1 Regular induced subgraph detection Require: G 1: RIS = [] 2: for k = 0 : max deg out do 3:

Fig. 3 .

 3 Fig. 3. Left: The largest regular induced subgraph found is highlighted in red. Thick lines are used for two-way edges for better readibility. Right: The upper bound (k-Core) is displayed in blue for k ∈ {1; 2; 3; 4}. Black dots are the real size of k-RIS for k ∈ {1; 2; 3}: 4-RIS is not computed, as σ(4) < |3-RIS|. The red dotted line shows the size of the RIS.

Fig. 4 .

 4 Fig. 4. The family of p-reg graphs allows to control the regularity of a graph.

  v

Fig. 6 .

 6 Fig. 6. Error of reconstruction in function of the error regularity for the family of p-reg graph. For each p ∈ [1, ..., 100], 25 p-reg graph are generated with different inputs.The error of reconstruction is then computed as the bias between the signal and the reconstruction at t = 1000 (which is a good approximation of ess). This emphasizes the link between the regularity of a subgraph and the ability to reconstruct its average.

Algorithm 4 Fig. 7 .

 47 Fig. 7. Illustration of Algorithm 4 (on an undirected graph for readability).Here the beam width is β = 2, so at each step the best two candidates are kept (solid line). Two small modifications are made to make the example more readable: the seed is a single candidate while in the algorithm the seed is composed of the singletons of each node; the new candidates are the subsets composed of a previous candidate and a node neighboring this candidate, while the latter node can be arbitrary in the algorithm.

  (a) In red, the quasi-regular subgraph detected with algorithm 4. (b) We added noises in the graph of (a) to emphasize the efficiency of the algorithm to find a consistent subset of nodes. (c) Reconstruction of the average of the quasi-regular subgraph obtained in (a).

Fig. 8 .

 8 Fig.8. Illustration of the q-RIS approach. Our algorithm is able to detect a subgraph (a) which is regular enough to ensure a good reconstruction of its average state (b).

G

  = remove I ∪ N out (I) from G 6:

  (a) A first subgraph is found (in blue). On the right the evolution of the regularity error through the iterations. The red dot corresponds to the iteration where the subgraph maximizing (20) is found.(b) The first subgraph found and its successors are removed and the algorithm is applied again to detect a second subgraph (in blue).

Fig. 10 .Fig. 11 .

 1011 Fig. 10. (a-c) left: in blue the subgraph within the current graph; right: the evolution of the regularity error of the best candidate is displayed through the iteration. Moreover a red dot shows the iteration of the selected subgraph. Two other subgraphs are found but it is not shown here. (d) represents the graph obtained by merging the different subgraphs. This reduced graph offers an estimation of the initial graph, and thus can be seen as an aggregation of it.

Fig. 12 .

 12 Fig. 12. Graph of interaction of the main cities of France. It is composed of 1404 nodes, each representing a population of 5000 individuals. The subgraphs within the cities is based on the Watts-Strogatz model while the graph between cities is a random graph where the probability of connection between two nodes decreases exponentially with the distance.

Fig. 13 .

 13 Fig. 13. Partition obtained via the mq-RIS algorithm 5. The legend gives the error of regularity, the number of nodes and the mean degree for each subgraph detected.

Fig. 14 .

 14 Fig. 14. Interpolating map of the number of individual infected with flu for 100000 inhabitants in January 2019 in France. Map available on www.sentiweb.fr R éseau Sentinelles, INSERM, Sorbonne Universit é.

Fig. 15 .

 15 Fig. 15. Proportion of infected individuals within each subgraph. The solid lines are the ground-truth values and the dotted lines are the average estimated from the measurements.

Fig. 16 .

 16 Fig. 16. Semi-log representation of absolute errors between the groundtruth value and the estimated value for each subgraph. The errors decrease but they do not converge to zero.

Nicolas

  Martin received the M.Sc. degree in applied mathematics from Institut National des Sciences Appliqu ées (INSA) of Toulouse, France in 2016. In 2015, he made an internship at the European Southern Observatory (ESO) in Chile, Santiago. In 2016, he made an internship at the Centre National d'Etude Spatiale (CNES) in Toulouse, France. In 2020 he has received the Ph.D. degree from the University of Grenoble, France. Paolo Frasca (M'13, SM'18) received the Ph.D. degree in Mathematics for Engineering Sciences from Politecnico di Torino, Italy, in 2009. From 2013 to 2016, he has been an Assistant Professor at the University of Twente, the Netherlands. Since October 2016, he is a CNRS researcher at GIPSA-lab, Grenoble, France. His research interests are in the theory of network systems and cyber-physical systems, with applications to robotic, sensor, infrastructural, and social networks. Carlos Canudas-de-Wit was born in Villahermosa, Mexico, in 1958. He received the B.S. degree in electronics and communications from the Monterrey Institute of Technology and Higher Education, Monterrey, Mexico, in 1980, and the M.S. and Ph.D. degrees in automatic control from the Department of Automatic Control, Grenoble Institute of Technology, Grenoble, France, in 1984 and 1987, respectively. He is currently a Directeur de recherche (Senior Researcher) with CNRS, Grenoble, where he is the Leader of the NeCS Team, a joint team of GIPSA-Lab (CNRS) and INRIA, on networked controlled systems. Dr. Canudas-de-Wit is an IEEE Fellow and an IFAC Fellow. He served as the President of the European Control Association from 2013 to 2015, and the IEEE Board of Governors of the Control System Society from 2011 to 2014. He holds the ERC Advanced Grant Scale-FreeBack from 2016 (1999-2002).

This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement N. 694209) www.scale-freeback.eu


Clément Elvira

Jérémy E Cohen

Cédric Herzet

Rémi Gribonval

Jeremy E Cohen

Continuous dictionaries meet low-rank tensor approximations

come

1 Sparse and low-rank reconstructions Sparse decompositions. The "k-sparse representation problem" consists in finding an accurate representation of some vector y ∈ R m as the linear combination of k elements from some set D ⊂ R m , commonly called dictionary. Finding the best k-sparse representation of y ∈ R m in D is known to be an NPhard problem for most dictionaries, see [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing[END_REF]Section 2.3]. Hence, the design of tractable methods to find (provably) good sparse representations of certain families of signals y has been a very active area of research during the last decades.

Although most contributions focus on the case where D contains a finite number of elements, several authors have recently placed the sparse-representation problem in the context of "continuous" dictionaries. In this framework, D is made up of an infinite (uncountable) number of elements continuously indexed by some parameter θ:

D = {d(θ) ∈ R m : θ ∈ Θ} (1)
where d : Θ → R m is a continuous function and Θ ⊆ R d . The generalization of the well-kwown Lasso problem to context of continuous dictionaries (1) was considered in [START_REF] Bredies | Inverse problems in spaces of measures[END_REF]. It involves the optimization with respect to a measure µ belonging to the space of Radon measures over Θ, say M(Θ):

µ ∈ arg min µ∈M(Θ) 1 2 y -Dµ 2 2 + λ µ TV , (2)
where Dµ d(θ)dµ(θ), and • TV is the so-called "total variation" norm, see e.g., [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF]Eq (7)]. We note that, despite of its apparent complexity (optimization over a space of measures), efficient procedures based on the conditional gradient method [4, Section 2.2] have been proposed that operate on measures with finite support, see e.g., [START_REF] Boyd | The alternating descent conditional gradient method for sparse inverse problems[END_REF][START_REF] Denoyelle | The sliding frank-wolfe algorithm and its application to super-resolution microscopy[END_REF].

Low-rank approximation of matrices. Inspired by the success of the sparse model, several authors proposed to tackle inverse problems involving different types of low-dimensional structures. One striking example is the reconstruction of lowrank matrices considered by Candès et al in [START_REF] Candès | Exact matrix completion via convex optimization[END_REF]. More specifically, the authors addressed the problem of reconstructing a low-rank matrix X ∈ R n1×n2 from partial observations y ∈ R m as the solution of the following optimization problem:

X ∈ arg min X∈R n 1 ×n 2 1 2 y -A X 2 2 + λ X * . (3)
Here A : R n1×n2 → R m plays the role of some linear observation operator and • * is the so-called "nuclear" norm defined as:

X * = min(n1,n2) =1 σ (X), (4)
where σ (X) denotes the th singular value of X. It can be shown that the rank of solutions to (3) is related to λ, i.e. the nuclear norm induces low-rank solutions. The success of the method proposed by Candès et al. revolves around: (i) theoretical guarantees that the solution to (3) may be the solution of the NP-hard low-rank approximation problem; (ii) efficient solvers such as FISTA [START_REF] Beck | A fast iterative shrinkage thresholding algorithm for linear inverse problems[END_REF] which rely on the closed-form expression of the proximal operator of the matrix nuclear norm.

Low-rank approximation of tensors. Given the success of convex-relaxation methods for the reconstruction of low-rank matrices, it is tempting to extend the ingredients of problem (3) to the low-rank decomposition of t-dimensional tensors. To this end, following [START_REF] Lim | Blind multilinear identification[END_REF], the tensor nuclear norm is defined as the gauge function of the convex hull of normalized rank-one tensors:

X * = inf <∞ |c | : X = <∞ c u (1) ⊗ . . . ⊗ u (t) , u (i) ∈ S ni .
where ⊗ denotes the tensor product and S ni is the n idimensional unit-sphere. Indexation < ∞ means the number of summands must be finite. It is well-known that this definition is equivalent to (4) when t = 2 [START_REF] Friedland | Nuclear norm of higher-order tensors[END_REF]. With this generalized definition (and a proper definition of A ), problem (3) straightforwardly extends to the multidimensional tensorial case. Unfortunately, as shown in [START_REF] Friedland | Nuclear norm of higher-order tensors[END_REF], the evaluation of the nuclear norm is NP-difficult as soon as t > 2. Although this seems to mean that (convex) nuclear norm regularized approximation (3) is not easier to solve than (nonconvex) tensor low-rank approximation, in this contribution we propose a Frank-Wolfe algorithm working on a related BLasso problem that tries to solve (3) globally. We discuss research directions to hopefully provide appropriate assumptions for the global convergence of the algorithm, and show practical results for tensor rank selection.

From low rank to sparsity

The idea underlying the reformulation of the low-rank approximation problem as a sparse-representation problem is as follows: any rank-k tensor can be rewritten as the sum of k rank-1 tensors; hence, rank-k tensors have k-sparse representations in the (continuous) dictionary of rank-1 tensors. In the framework of sparse representations in continuous dictionaries, one may define the parameter set Θ as Θ = (u (1) , . . . , u (t) ) :

u (i) ∈ S ni (5)
and the "atom function" as

d : Θ → R m (u (1) , . . . , u (t) ) → A u (1) ⊗ . . . ⊗ u (t) . (6)
With these definitions, the continuous dictionary D in (1) corresponds to the image of the set of unit-norm rank-1 tdimensional tensors seen through operator A . A sparse decomposition of y in D can then be searched via the resolution of problem [START_REF] Bredies | Inverse problems in spaces of measures[END_REF]. The pertinence of this approach with respect to our initial regularized tensor-approximation problem (3) is given in Proposition 1 below. Before stating our result, we note that any solution µ of (2) defines a t-dimensional tensor as Dµ , where D is defined from ( 5)-( 6). Conversely, any solution X of (3) defines a discrete measure in M(Θ) with mass σ (X ) located at the corresponding singular vector, say (u (1) , . . . , u (t) ). Keeping this remark in mind, our result reads:

Proposition 1. Consider problem (2) with D defined from (5)- [START_REF] Denoyelle | The sliding frank-wolfe algorithm and its application to super-resolution microscopy[END_REF]. Any solution X of (3) defines a discrete solution of (2).

Conversely, any discrete measure µ which is solution of (2) defines a solution of (3).

In other other words, Proposition 1 states that all the solutions of (3) can be found by identifying the discrete solutions of (2). Our proof revolves around the fact that the infimum in the nuclear norm is attained [START_REF] Friedland | Nuclear norm of higher-order tensors[END_REF]Prop. 3.1]. In particular, it implies that there must exist discrete measures that are solutions to the BLasso problem. We can therefore exploit the algorithmic strategies available for solving the BLasso problem to search for the solutions of (3).

Algorithms

A popular algorithm to solve the BLasso problem is the socalled " Frank-Wolfe" algorithm [4, Section 2.2]. We consider hereafter a generalized version of this procedure called "Sliding Frank-Wolfe (SFW)", see [START_REF] Denoyelle | The sliding frank-wolfe algorithm and its application to super-resolution microscopy[END_REF]Chapter 4,Alg. 3]. It consists of three steps repeated until convergence. First, identify the best normalized atom by maximizing correlation with the residual. Second, compute the optimal coefficients with fixed selected atoms. Finally, optimize both coefficients and atom parameters for a fixed sparsity level s. In the tensor framework, this means alternately solving problems of the following form:

arg max u (i) ∈S n i A * r, u (1) ⊗ . . . ⊗ u (t) (7)
arg min

c∈R s 1 2 y -Dc 2 2 + λ c 1 (8)
arg min c∈R s ,u (i) ∈S n i 1 2 y -A s =1 c u (1) ⊗ . . . ⊗ u (t) 2 2 + λ c 1 (9)
where r ∈ R m is the residual vector after a given number of iterations, matrix D is computed straightforwardly from the set of identified atoms, and A * is the adjoint of A , often easy to compute in practice. Tensor rank of the output of the proposed Sliding Frank-Wolfe algorithm, with λ varying from 0 to λmax as defined in [START_REF] Denoyelle | The sliding frank-wolfe algorithm and its application to super-resolution microscopy[END_REF]. Red crosses are bad estimates, that might be improved by a better implementation of steps ( 7) and ( 9) of the FW algorithm.

These three steps have very different levels of difficulty. Problem ( 8) is a simple Lasso problem, for which efficient solvers already exist. Problem [START_REF] Lim | Blind multilinear identification[END_REF] is in principle as difficult as the original tensor factorization problem with low-rank constraint. Nevertheless, it can be shown that convergence of SFW is still ensured as soon as the output of step [START_REF] Lim | Blind multilinear identification[END_REF] does not increase the BLasso cost function. Hence, problem (9) can be substituted by a few iterations of some local optimization procedures, see, e.g., [START_REF] Uschmajew | Local convergence of the alternating least squares algorithm for canonical tensor approximation[END_REF].

Finally, solving [START_REF] Candès | Exact matrix completion via convex optimization[END_REF] means finding the best rank-one approximation of a tensor A * r, which is an NP-hard problem in general [START_REF] Friedland | Best rank one approximation of real symmetric tensors can be chosen symmetric[END_REF]. To the best of the author's knowledge, no method is even proved to produce an estimate positively correlated with the optimal solution in general [START_REF] Arous | The landscape of the spiked tensor model[END_REF]. On the other hand, practical algorithms exist that empirically perform extremely well [START_REF] Friedland | Nuclear norm of higher-order tensors[END_REF][START_REF] Da Silva | Rank-1 tensor approximation methods and application to deflation[END_REF]. Moreover the Higher-Order Singular Value Decomposition [START_REF] Lathauwer | A multilinear singular value decomposition[END_REF] provides an initialization which guarantees quasi-optimality of the fitting error in Frobenius norm. We are currently working on linking existing results on tensor best rank-one approximation with sufficient conditions for the FW algorithm to converge globally. Practically, we compute (7) using the Alternating Least Squares algorithm, initialized randomly ten times and picking the best result.

Experiments

Let us showcase the proposed SFW algorithm on a rank detection problem. Given a noised 3-dimensional data tensor T = X + σN with X of rank k = 5, we try to find the value of k by solving the tensor version of (3) for several values of λ. We set A as the vectorization operator. The noise tensor has entries drawn from i.i.d. Gaussian distributions. Ground truth tensor X is generated using factors drawn from i.i.d. Gaussian distributions with dimensions 20 × 21 × 22, and ground-truth c are drawn from the absolute value of i.i.d. Gaussian distributions with mean 0.5. The noise level σ is set to 0.005.

Figure 1 shows the results for various values of λ. We clearly observe proper rank detection, although there is a spurious error around λ = 0.25λ max . Moreover, we observed that the atoms selected with various λ values are very closely related, which would confirm some kind of global convergence behavior, despite our implementation behind largely improvable. Note that within the proposed framework, we may also, among others, tackle missing data imputation or directly low-rank approximation.

Figure 1 :

 1 Figure1: Tensor rank of the output of the proposed Sliding Frank-Wolfe algorithm, with λ varying from 0 to λmax as defined in[START_REF] Denoyelle | The sliding frank-wolfe algorithm and its application to super-resolution microscopy[END_REF]. Red crosses are bad estimates, that might be improved by a better implementation of steps[START_REF] Candès | Exact matrix completion via convex optimization[END_REF] and (9) of the FW algorithm.