Ahmet Iscen

Giorgos Tolias

Yannis Avrithis

Teddy Furon
email: teddy.furon@inria.frgiorgos.tolias

Ondřej Chum
email: chum@cmp.felk.cvut.cz

Efficient Diffusion on Region Manifolds: Recovering Small Objects with Compact CNN Representations

Query expansion is a popular method to improve the quality of image retrieval with both conventional and CNN representations. It has been so far limited to global image similarity. This work focuses on diffusion, a mechanism that captures the image manifold in the feature space. The diffusion is carried out on descriptors of overlapping image regions rather than on a global image descriptor like in previous approaches. An efficient off-line stage allows optional reduction in the number of stored regions. In the on-line stage, the proposed handling of unseen queries in the indexing stage removes additional computation to adjust the precomputed data. We perform diffusion through a sparse linear system solver, yielding practical query times well below one second.

Experimentally, we observe a significant boost in performance of image retrieval with compact CNN descriptors on standard benchmarks, especially when the query object covers only a small part of the image. Small objects have been a common failure case of CNN-based retrieval.

Introduction

Object search is a key tool behind a number of applications like content based image collection browsing [START_REF] Weyand | Discovering favorite views of popular places with iconoid shift[END_REF][START_REF] Mikulik | Image retrieval for online browsing in large image collections[END_REF], visual localization [START_REF] Sattler | Image retrieval for image-based localization revisited[END_REF][START_REF] Arandjelović | NetVLAD: CNN architecture for weakly supervised place recognition[END_REF], and 3D reconstruction [START_REF] Heinly | Reconstructing the world* in six days*(as captured by the yahoo 100 million image dataset)[END_REF][START_REF] Schonberger | From single image query to detailed 3d reconstruction[END_REF]. Many applications benefit from retrieving images taken from various viewing angles and under different illumination, e.g. more information for the user while browsing, localization in day and night, and complete 3D models. Each image is represented by one or more descriptors designed or learned to exhibit a certain degree of invariance to imaging conditions. Retrieval is formulated as a nearest neighbor search in the descriptor space, performed by approximate methods [START_REF] Muja | Scalable nearest neighbor algorithms for high dimensional data[END_REF][START_REF] Jégou | Product quantization for nearest neighbor search[END_REF]29,[START_REF] Babenko | Efficient indexing of billionscale datasets of deep descriptors[END_REF].

While collections of local descriptors provide good invariance, global descriptors like VLAD [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] have smaller memory footprint, but are more prone to locking onto the clutter. This mainly holds when the queried object covers only a small part of the image. In case of global CNN descriptors, the invariance is partially designed by global max [START_REF] Azizpour | From generic to specific deep representations for visual recognition[END_REF][START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF] or sum [START_REF] Kalantidis | Crossdimensional weighting for aggregated deep convolutional features[END_REF]4] pooling layers or multi-scale querying [START_REF] Gordo | End-to-end learning of deep visual representations for image retrieval[END_REF], and partially learned by the choice of the training data. Robustness to background clutter is improved by computing descriptors over object proposals [START_REF] Mopuri | Object level deep feature pooling for compact image representation[END_REF][START_REF] Gordo | Deep image retrieval: Learning global representations for image search[END_REF][START_REF] Xie | Image classification and retrieval are one[END_REF] or over a fixed grid of regions [START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF]. Better performance is observed at a cost of increased memory footprint [START_REF] Razavian | Visual instance retrieval with deep convolutional networks[END_REF].

In image collections, objects are depicted in various conditions. As a consequence, query and relevant images are often connected by a sequence of images, where consecutive images are similar. The descriptors of these images form a manifold in the descriptor space. Even though the images of the sequence contain the same object, the descriptors may be completely unrelated after a certain point.

This idea has been first exploited by Chum et al. [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF] who introduce query expansion. The average query expansion 1 (AQE) is now used as a standard tool in image retrieval, due to its efficiency and significant performance boost. However, AQE only explores the neighborhood of very similar images. Recursive and scale-band recursive methods [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF] further improve the results by explicitly crawling the image manifold. This is at a cost of increased query time.

Query expansion exploits the manifold of images at query time-starting from nearest neighbors of the query and using these neighbors to issue new queries. On the other hand, diffusion [START_REF] Page | The pagerank citation ranking: bringing order to the web[END_REF][START_REF] Zhou | Ranking on data manifolds[END_REF][START_REF] Donoser | Diffusion processes for retrieval revisited[END_REF] is based on a neighborhood graph of the dataset that is constructed off-line and efficiently uses this information at query time to search on the manifold in a principled way.

We make the following contributions:

• We introduce a regional diffusion mechanism, which handles one or more query vectors at the same cost.

There is one vector per region and a few regions per image so that constructing and storing the graph is tractable. This approach significantly improves retrieval of small objects and cluttered scenes.

• In diffusion mechanisms [START_REF] Page | The pagerank citation ranking: bringing order to the web[END_REF][START_REF] Zhou | Ranking on data manifolds[END_REF][START_REF] Donoser | Diffusion processes for retrieval revisited[END_REF], query vectors are usually part of the dataset and available at the indexing stage. A novel approach to unseen queries with no computational overhead is proposed.

• Though a closed form solution is known to exist, it has been explicitly avoided so far [START_REF] Donoser | Diffusion processes for retrieval revisited[END_REF]. We show that the commonly used alternative is in fact a well known iterative linear system solver. Since the relevant matrix is sparse and positive definite, the conjugate gradient method is more efficient resulting in practical query times well below one second.

• To study the dependence of performance on relative object size, we experiment on INSTRE dataset [55], which has not received much attention so far. We propose a new evaluation protocol that is in line with other well known datasets and provide a rich set of baselines to facilitate future comparisons.

Searching in parallel in more than one manifolds via diffusion and using the nearest neighbors of unseen queries are illustrated in Figure 1.

The remaining text is structured as follows. Sections 2 and 3 discuss related work and background respectively, focusing on diffusion mechanisms. Sections 4 and 5 present our contributions in detail and the experimental body.

Related work

This section discusses existing query expansion or reranking methods. We also review the concept of diffusion in computer vision and image retrieval in particular. Apart from AQE [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF], none of these methods has been applied to retrieval in the context of convolutional features. [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF]7,[START_REF] Tolias | Visual query expansion with or without geometry: refining local descriptors by feature aggregation[END_REF] employ local features and are well adapted to the Bag-of-Words model [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF]. Others are generic and applicable on any global image representation [27,[START_REF] Qin | Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors[END_REF][START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF][START_REF] Shen | Spatially-constrained similarity measure for large-scale object retrieval[END_REF][START_REF] Delvinioti | Image retrieval with reciprocal and shared nearest neighbors[END_REF]. In both cases, ranking is performed on the image level. Extension to regional level is not always straightforward. If even possible, such an extension would come at a significant cost, as each query region would need to be treated independently. This is unlike our regional diffusion mechanism, which has a fixed cost with respect to the number of query regions.

Query expansion. A variety of methods

Diffusion. We are focusing on diffusion mechanisms, which propagate similarities through a pairwise affinity matrix [START_REF] Donoser | Diffusion processes for retrieval revisited[END_REF][START_REF] Page | The pagerank citation ranking: bringing order to the web[END_REF]. They are applied to many computer vision problems, such as semi-supervised classification [START_REF] Zhou | Learning with local and global consistency[END_REF], seeded image segmentation [START_REF] Grady | Random walks for image segmentation[END_REF], saliency detection [33,[START_REF] Chen | Discriminative saliency propagation with sink points[END_REF], clustering [START_REF] Donoser | Replicator graph clustering[END_REF] and image retrieval [START_REF] Jing | Visualrank: Applying pagerank to large-scale image search[END_REF]14,[START_REF] Yang | Locally constrained diffusion process on locally densified distance spaces with applications to shape retrieval[END_REF][START_REF] Donoser | Diffusion processes for retrieval revisited[END_REF][START_REF] Xie | Fast and accurate near-duplicate image search with affinity propagation on the imageweb[END_REF].

The power of such methods lies in capturing the intrinsic manifold structure of the data [START_REF] Zhou | Learning with local and global consistency[END_REF]. The popular PageRank algorithm [START_REF] Page | The pagerank citation ranking: bringing order to the web[END_REF] was originally used to estimate the importance of web pages by exploiting their links in a graph structure. Our retrieval scenario comes closer to its so called personalized [START_REF] Page | The pagerank citation ranking: bringing order to the web[END_REF] or query dependent versions [START_REF] Richardson | The intelligent surfer: Probabilistic combination of link and content information in pagerank[END_REF], where the final ranking both respects the data manifold and the similarity to a number of query vectors.

Diffusion is used for retrieval of general scenes or shapes of particular objects [START_REF] Jing | Visualrank: Applying pagerank to large-scale image search[END_REF]14,[START_REF] Yang | Locally constrained diffusion process on locally densified distance spaces with applications to shape retrieval[END_REF][START_REF] Donoser | Diffusion processes for retrieval revisited[END_REF]. It can also fuse multiple feature modalities [61,[START_REF] Yang | Re-ranking by multifeature fusion with diffusion for image retrieval[END_REF] by jointly modeling them on the same graph. In these approaches, images are the nodes of the graph with edges established given a pairwise similarity measure. We differentiate by defining a graph of image regions linked based on region similarities while performing a single pseudo random walk for multiple query regions. Diffusion with regional similarity has been investigated before, but only to define image level affinity [START_REF] Zhang | Hyperlink-aware object retrieval[END_REF], to aggregate local features [15], or to handle bursts [START_REF] Gao | Democratic diffusion aggregation for image retrieval[END_REF].

Donoser and Bischof [START_REF] Donoser | Diffusion processes for retrieval revisited[END_REF] review a number of diffusion mechanisms for retrieval. They focus on iterative solutions arguing that closed form solutions, when existing, are impractical due to inversion of large matrices. We rather focus on a closed form solution computed approximatively with an iterative method that is particularly designed for this problem and show that this approach is faster.

Ranking with diffusion

Diffusion in the work of Donoser and Bischof [START_REF] Donoser | Diffusion processes for retrieval revisited[END_REF] denotes a mechanism spreading the query similarities over the manifolds composing the dataset. This is only weakly related to continuous time diffusion process or random walks on graph. We mainly follow Zhou et al. [START_REF] Zhou | Ranking on data manifolds[END_REF] below.

Affinity matrix. Given a dataset X := {x 1 , . . . , x n } ⊂ R d , we define the affinity matrix A = (a ij ) ∈ R n×n having as elements the pairwise similarities between points of X :

a ij := s(x i , x j ), ∀(i, j) ∈ [n] 2 , (1)
where [n] := {1, . . . , n} and s : R d × R d → R is a similarity measure assumed to be symmetric (A = A ), positive (A > 0), and with zero self-similarities (diag(A) = 0).

Matrix A is the adjacency matrix of a weighted undirected graph G with vertices X . The degree matrix of the graph is D := diag(A1 n ), i.e. a diagonal matrix with the row-wise sum of A. The Laplacian of the graph is defined as L := D -A. It is usual to symmetrically normalize these matrices, for instance,

S := D -1/2 AD -1/2 , (2)
for the affinity matrix and L := I n -S for the Laplacian, where I n denotes the identity matrix of size n. Matrices L, L are positive-semidefinite [START_REF] Chung | Spectral graph theory[END_REF]. Diffusion. In the work of Zhou et al. [START_REF] Zhou | Ranking on data manifolds[END_REF], a vector y = (y i ) ∈ R n specifies a set of query points in X , with y i = 1 if x i is a query and y i = 0 potherwise. The objective is to obtain a ranking score f i for each point

x i ∈ X , represented as vector f = (f i ) ∈ R n .
We focus on a particular diffusion mechanism that, given an initial vector f 0 , iterates according to

f t = αSf t-1 + (1 -α)y. (3)
If S is a transition matrix and y a1 unit vector, this defines the following 'random walk' on the graph: with probability α one jumps to an adjacent vertex according to distribution stated in S, and with 1 -α to a query point uniformly at random. In this fashion, points spread their ranking score to their neighbors in the graph. The benefit is the ability to capture the intrinsic manifold structure represented by the affinity matrix and to combine multiple query points. Assuming 0 < α < 1, Zhou et al. [START_REF] Zhou | Learning with local and global consistency[END_REF][START_REF] Zhou | Ranking on data manifolds[END_REF] show that sequence {f t } defined by (3) converges to

f = (1 -α)L -1 α y (4)
where L α := I n -αS is positive-definite. This follows since L α = αL + (1 -α)I n αL 0. In this work, we focus on the closed form solution (4) rather than its intuitive derivation from iterative process (3).

Relation to other approaches. A diffusion mechanism also appears in seeded image segmentation [START_REF] Grady | Random walks for image segmentation[END_REF], where query points correspond to labeled pixels (seeds) and database points to the remaining unlabeled pixels. This problem is equivalent to semi-supervised classification [START_REF] Zhou | Learning with local and global consistency[END_REF].

In our context, the approach of Grady [START_REF] Grady | Random walks for image segmentation[END_REF] decomposes f = (f d , f q ) for the scores of the query (fixed f q ) and database (unknown f d ) points. Diffusion interpolates f d from f q by minimizing, w.r.t. f d , the quadratic cost i,j a ij (f i -f j ) 2 = f Lf to enforce that neighboring points should have similar scores. By decomposing L = [L d , -S qd ; -S qd , L q ], it is shown [START_REF] Grady | Random walks for image segmentation[END_REF] that the solution fulfills L d f d = y with y = S qd f q . In our setup, L d would be singular, preventing us to single out a solution f d . Yet, it is easy to show that the minimizer of the cost αf Lf + (1 -α) f 2 has a similar expression to (4). The regularization term singles out a solution by forcing f to be zero in subgraphs not connected to any query point. The details are omitted for brevity.

Local constraints. Donoser and Bischof have extensively investigated various constructions of affinity matrices in the context of image retrieval [START_REF] Donoser | Diffusion processes for retrieval revisited[END_REF]. Our work uses matrix (2), which is found to be the most effective in their work, and is also used by Zhou et al. [START_REF] Zhou | Learning with local and global consistency[END_REF]. Further, to handle noise and outliers, we adopt a locally constrained random walk [START_REF] Kontschieder | Beyond pairwise shape similarity analysis[END_REF] where only pairs of points that are reciprocal (mutual) nearest neighbors are kept as edges in the graph. In particular, given z ∈ R d , let

s k (x|z) = s(x, z), if x ∈ NN k (z) 0, otherwise (5)
be the similarity of x ∈ X given z, that is, restricted to the k nearest neighbors NN k (z) of z in X . Then,

s k (x, z) = min{s k (x|z), s k (z|x)} (6)
equals s(x, z) if x, z are the k-nearest neighbors of each other in X , and zero otherwise. We use similarity function s k to construct affinity matrix A like in (1).

Method

This section describes our contributions on image retrieval: handling new query points not in the dataset, searching for multiple regions with a single diffusion mechanism, and efficiently computing the solution.

Handling new queries

In prior work on diffusion, a query point q is considered to be contained in the dataset X [START_REF] Zhou | Learning with local and global consistency[END_REF][START_REF] Donoser | Diffusion processes for retrieval revisited[END_REF]. This does not hold in a retrieval scenario, but a query can be included in the dataset graph at query time [61] as follows. The k nearest neighbors NN k (q) of q in X are found and reciprocity is checked. The rows and columns of the affinity matrix A corresponding to NN k (q) are updated to maintain [START_REF] Chen | Discriminative saliency propagation with sink points[END_REF] in the presence of q, and A is augmented by appending an extra row and column for q. Matrix S is computed by normalizing A (2). Finally, vector y indicates that q is a query. Generalizing to multiple query points is straightforward.

Even if we ignore the time needed for the above computation, we argue that locking, modifying and augmenting the entire affinity matrix for each query is not acceptable in terms of space requirements 1 . We introduce here an alternative method which defines vector y in a new way rather than modifying A. Qualitatively, instead of searching for q, we are searching for its neighbors NN k (q), appropriately weighted. In particular, we define y as

y i = s k (x i |q), ∀i ∈ [n]. (7)
Our motivation for this choice is detailed in Section 4.2 including the more general case of multiple query points.

Figure 1 shows a toy 2-dimensional example of diffusion, where the k-nearest neighbors to each query point taken into account in (7) are depicted. It is evident that multiple manifolds are captured when multiple queries are issued. Section 5 experimentally shows improved performance compared to the conventional approach.

Regional diffusion

The diffusion mechanism described so far is applicable to image retrieval when database and query images are globally represented by single vectors. We call this global diffusion in the rest of the paper. Unlike the traditional representation with local descriptors [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF][START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], global diffusion fits perfectly with the early CNN-based global features [4, [START_REF] Kalantidis | Crossdimensional weighting for aggregated deep convolutional features[END_REF][START_REF] Radenović | CNN image retrieval learns from BoW: Unsupervised fine-tuning with hard examples[END_REF].

Global features still fail under severe occlusion or when the object of interest is small. Local CNN features from multiple image regions have been investigated for this purpose, either aggregated [17,[START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF] or represented as a set [START_REF] Razavian | Visual instance retrieval with deep convolutional networks[END_REF]. Given a query image, the latter means that one searches for each query feature individually.

Fortunately, diffusion as defined in section 3 can already handle multiple queries. In the following, an image is represented by a set X i ⊂ R d of m points, one for each region. Dataset X is the union of such sets over all images; n still denotes its size. The query image is also represented by a set Q of m points. Each region feature is a point possibly lying on a different manifold. We discuss below the new definition of vector y and the combination of individual region ranking scores into a single score per image. We call this mechanism regional diffusion. Specifying queries. In the conventional approach where query points are in the dataset, one directly applies (3) with y ∈ {0, 1} n+m with m non-zero elements indicating the query points. This situation resembles the personalized PageRank [START_REF] Page | The pagerank citation ranking: bringing order to the web[END_REF]. However, it is simpler to keep A as an n×n affinity matrix and to set y ∈ R n as

y i := q∈Q s k (x i |q), ∀i ∈ [n]. (8)
Each dataset point x i is assigned a scalar that is the sum of similarities over all query points q for which x i appears in the corresponding k-nearest neighbor set NN k (q), and zero if it appears in no such set.

Derivation. Our work is inspired by the analysis in the work of Grady [START_REF] Grady | Random walks for image segmentation[END_REF] that we apply to the diffusion mechanism of Zhou et al. [START_REF] Zhou | Ranking on data manifolds[END_REF], where query points Q are in the dataset. We decompose the quantities in (3

) as f = (f d , f q ) , with f d ∈ R n and f q ∈ R m , S = S d B dq B qd S q , (9)
and y = (0 n , 1 m ) . Subscripts d, q denote data and query respectively. Then, (3) is written as

f t d = αS d f t-1 d + αB dq f t-1 q ( 10
)
f t q = αB qd f t-1 d + αS q f t-1 q + (1 -α)1 m . (11)
Provided this system converges, the data part satisfies

f d ∝ L -1 α B dq 1 m (12)
if f q ∝ 1 m , S q = 0 m×m and B qd = 0 m×n . In words, the query points are perfectly retrieved, they are dissimilar to each other, and the graph is indeed directed with query regions pointing to dataset regions, but the reverse is not allowed. Comparing ( 12) with (4), it follows that B dq 1 m is a good choice for y. Since B dq stores the similarities between the dataset and the query points, this analysis justifies the single query (7) and the multiple queries (8) cases.

Diffusion. Given this definition of y, diffusion is now performed on dataset X , jointly for all query points in Q.

Affinities of multiple query points are propagated in the graph in a single process at no additional cost compared to the case of a single query point. Here we are excluding the additional cost of computing y itself in (8) compared to (7). This search takes place in all related work. We also do not discuss how to make this search more efficient in space and time [START_REF] Babenko | Efficient indexing of billionscale datasets of deep descriptors[END_REF], which is beyond the scope of this work.

Figure 1 illustrates the diffusion on single and multiple query points. The contour lines show the ranking score any point on the plane would be assigned given the query point(s). It is evident that multiple manifolds are captured when multiple queries are issued.

Pooling. After diffusion, each image is associated with several elements of the ranking score vector f , one for each point x in X ⊂ X . A simple way to combine these scores is to define the score of image X as

f (X) = j∈[m] w j f i X (j) , (13)
where i X (j) is the index of the j-th point of X in the dataset X and w = (w j ) a weighting vector. The latter is defined as w = 1 m for sum pooling and, assuming m < d,

w = (ΦΦ + λI m ) -1 1 m (14)
for generalized max pooling (GMP) [START_REF] Murray | Generalized max-pooling[END_REF][START_REF] Iscen | Memory vectors for similarity search in high-dimensional spaces[END_REF], where Φ = (x i X (1) , . . . , x i X (m) ) and λ ∈ R + is a regularization parameter. Our experiments show that GMP always outperforms sum pooling.

Efficient solution

Iteration (3) works well in practice but is slow at large scale. Taking the closed-form solution (4) literally, one may be tempted to compute the inverse L -1 α offline, but this matrix is not sparse like L α . We propose a more efficient solution by making the connection to linear system solvers.

Diffusion is an iterative solver. Eq. ( 3) can be seen as an iteration of the Jacobi solver [START_REF] Hackbusch | Iterative solution of large sparse systems of equations[END_REF]. Given a linear system Ax = b2 , Jacobi decomposes A as A = ∆ + R where ∆ = diag(A). It then iterates according to

x t = ∆ -1 (b -Rx t-1 ). (15)
In our case, x = f , b = (1 -α)y, and A = L α = I -αS.

It follows that ∆ = I n and R = -αS, so that

f t = αSf t-1 + (1 -α)y. (16)
We have just re-derived (3). Note that a sufficient condition for Jacobi's convergence is that matrix A is strictly diagonally dominant, i.e.

|a ii | > j =i a ij for i ∈ [n].
It is easily checked that L α does satisfy this condition by construction, given that 0 < α < 1. This provides an alternative proof of the main result of Zhou et al. [START_REF] Zhou | Learning with local and global consistency[END_REF].

Conjugate gradient (CG) [START_REF] Nocedal | Numerical optimization[END_REF] is the method of choice for solving linear systems like ours

L α f = (1 -α)y, (17)
where L α is positive-definite, and in particular for graphrelated problems [START_REF] Vishnoi | Laplacian solvers and their algorithmic applications[END_REF]. It has been used for random walk problems [START_REF] Grady | Random walks for image segmentation[END_REF], but not diffusion-based retrieval according to our knowledge. In fact, the linear system formulation has been explicitly avoided in this context [START_REF] Donoser | Diffusion processes for retrieval revisited[END_REF].

Here we argue, as in [START_REF] Langville | Deeper inside pagerank[END_REF], that it is the solution of (17) that we seek, rather than the path followed by iteration (3). However, we use CG to approximate this solution, since matrix L α is indeed positive-definite. At each iteration, CG minimizes the quadratic function φ(x) = 1 2 x Ax -x b in a particular direction by analytically computing the optimal step length. More importantly, the direction chosen at each iteration is conjugate to previous ones. Thus, any update of x along this direction does not destroy the optimality reached in the entire subspace considered thus far.

Contrary to other iterative methods including [START_REF] Gao | Democratic diffusion aggregation for image retrieval[END_REF], CG is guaranteed to terminate in n steps. Remarkably, it provides good approximations in very few steps.

Normalization is preconditioning. Finally, a standard improvement is preconditioning, i.e. , solving a related system with A replaced by C -1 AC -, a matrix satisfying a weak condition like its eigenvalues being clustered. Unfortunately, finding an appropriate matrix C can be quite complex [START_REF] Vishnoi | Laplacian solvers and their algorithmic applications[END_REF]. We observe that normalization (2) is preconditioning.Indeed, we could equally consider matrix L α = D -αA = αL + (1 -α)I 0 and solve the linear system

L α (D -1/2 f ) = (1 -α)(D 1/2 y) (18)
instead, which is equivalent to (17). By normalizing L α into L α , we are actually performing preconditioning with C = diag(L α ) 1/2 . This is a simple form of symmetric preconditioning, known as diagonal scaling or Jacobi [START_REF] Trefethen | Numerical linear algebra[END_REF].

It improves convergence, be it for CG or diffusion (3).

Scaling up

Despite the efficient solution described in the previous section, there are still issues concerning space and offline pre-processing at large scale. We address these issues here.

Compact representation. At large scale, the number of region features per database image should be kept as low as possible. For this reason, we learn a Gaussian Mixture Model (GMM) on the original features of each database image and represent the image by the unit normalized means. This is an even more natural choice when dealing with overlapping regions (see Section 5). As a result, it decreases the number of region features and their redundancy.

The off-line construction of the affinity matrix is quadratic in the number of vectors in the database and might not be tractable at large scale. We employ the efficient and approximate k-NN graph construction method by Dong et al. [START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF]. Section 5 shows that it is orders of magnitude faster than exhaustive search and has almost no effect on performance.

Truncating the affinity matrix. Instead of ranking the full dataset, diffusion re-ranks an initial search. This baseline in our experiments is done with global descriptors and kNN search. Then we apply diffusion only on the top ranked images. We truncate the affinity matrix keeping only the rows and columns related to the regions of the top ranked images and re-normalize it according to [START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF]. The cost of this step is not significant compared to the actual diffusion.

Experiments

This section presents the experimental setup and investigates the accuracy of our methods for image retrieval compared with the state-of-the-art approaches.

Experimental Setup

Datasets. We use three datasets. Two are well-known image retrieval benchmarks: Oxford Buildings [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] and Paris [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF]. We refer to them as Oxford5k and Paris6k. We experiment at large-scale by adding 100k distractor images from Flickr [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] Table 1. Retrieval performance (mAP) of regional diffusion with sum and generalized max pooling (GMP), with λ = 1 in (14).

with many variations such as different scales, rotations, and occlusions. Some objects cover a small part of the image, making it a challenging dataset. It consists of 28,543 images from 250 different object classes. In particular, 100 classes with images retrieved from on-line sources, 100 classes with images taken by the dataset creators, and 50 classes consisting of pairs from the second category. We differentiate from the original protocol [55], which uses all database images as queries. We randomly split the dataset into 1250 queries, 5 per class, and 27293 database images, while a bounding box defines the query region 3 . The query and the database sets have no overlap. We use mean average precision (mAP) as a performance measure in all datasets.

Representation. We employ a CNN that is fine-tuned for image retrieval [START_REF] Radenović | CNN image retrieval learns from BoW: Unsupervised fine-tuning with hard examples[END_REF] to extract global and regional representation. In particular, this fine-tuned VGG produces 512 dimensional descriptors. We extract regions at 3 different scales as in R-MAC [START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF], while we additionally include the full image as a region. In this fashion, each image has on average 21 regions. The regional descriptors are aggregated and re-normalized to unit norm in order to construct the global descriptors, which is exactly as in R-MAC. We apply supervised whitening [START_REF] Radenović | CNN image retrieval learns from BoW: Unsupervised fine-tuning with hard examples[END_REF] to both global and regional descriptors. We use this network to perform all our initial experiments. In Section 5.4, we also report scores with higher dimensional descriptors derived from the fine-tuned ResNet101 [START_REF] Gordo | End-to-end learning of deep visual representations for image retrieval[END_REF] using the same fixed grid.

Implementation details. We define the affinity function using a monomial kernel [START_REF] Tolias | To aggregate or not to aggregate: Selective match kernels for image search[END_REF] as s(x, z) = max(x z, 0) 3 . The diffusion parameter α is always 0.99, as in the work of Zhou et al. [START_REF] Zhou | Learning with local and global consistency[END_REF]. The k-NN search required by ( 8) is assumed to access all database vectors exhaustively. Our work does not investigate how approximate search methods [START_REF] Muja | Scalable nearest neighbor algorithms for high dimensional data[END_REF][START_REF] Jégou | Product quantization for nearest neighbor search[END_REF]29,[START_REF] Babenko | Efficient indexing of billionscale datasets of deep descriptors[END_REF][START_REF] Iscen | Efficient large-scale similarity search using matrix factorization[END_REF] could improve time and space consumed by this process. After computing (8), we only keep the largest k values of y and set the rest to zero.

Impact of different components

Neighbors. We vary the number of nearest neighbors k for constructing the affinity matrix and evaluate performance for both global and regional diffusion. The global baseline method is k-NN search with R-MAC, while the regional one is the method by Razavian et al. [START_REF] Razavian | Visual instance retrieval with deep convolutional networks[END_REF], where image regions are indexed and cross-matched. We refer to the latter as R-match in the rest of our experiments.

Results for Oxford5k are presented in Figure 2, and are consistent in other datasets. The performance stays stable over a wide range of k. The drop for low k is due to very few neighbors being retrieved (where regional diffusion is more sensitive), whereas for high k, it is due to capturing more than the local manifold structure (where regional diffusion is superior). This behavior is consistent with the fact that small patterns appear more frequently than entire images.

We set k = 200 for regional diffusion, and k = 50 for global diffusion for the rest of our paper. Since only mutual neighbors are linked, the actual number of edges per element is less: The average number of edges per image (resp. region) is 25 (resp. 75) for global (resp. regional) diffusion, measured on INSTRE. We set k = 200 for the query as well in the case of the regional diffusion, while for the global one k = 10 is needed to achieve good performance.

Pooling. We evaluate the two pooling strategies after regional diffusion in Table 1. Generalized max pooling has a small but consistent benefit in all datasets. We use this strategy for the rest of our experiments. Weights ( 14) are computed off-line and only one scalar per region is stored.

Efficient diffusion with conjugate gradient. We compare the iterative diffusion (3) to our conjugate gradient solution. We iterate each method until convergence. Performance is presented in Figure 3 with timings measured on a machine with a 4-core Intel Xeon 2.00GHz CPU. CG converges in as few as 20 iterations, which are also faster, while (3) reaches the same performance as CG only after 110 iterations.

The average query time on Oxford5k including all stages for global baseline, regional baseline, global diffusion and regional diffusion without truncation is 0.001s, 0.321s, 0.02s, and 0.664s, respectively.

Handling new queries. We compare our new way of handling new queries to the conventional approach that assumes queries to be part of the dataset. Our method achieves 80.0 mAP on INSTRE compared to 77.7 achieved by the conventional approach. We therefore not only offer space Figure 3. mAP performance of regional diffusion vs. number of iterations for conjugate gradient (CG) and iterative diffusion [START_REF] Azizpour | From generic to specific deep representations for visual recognition[END_REF]. Labels denote diffusion time. improvements but also better performance,mainly in the case of regional diffusion. The main difference is that k nonzero elements are kept both per query region (8) and for the entire vector y. This, due to the overlapping nature of the CNN regions, may filter out incorrect neighbors.

Large scale diffusion

We now focus on the large scale solutions of Section 4.4.

Reduced number of regions. Figure 4 shows the impact of reducing the number of regions with Gaussian mixture models. Having as few as 5 descriptors per image already achieves competitive performance, while reducing the online search complexity. We decrease the number of neighbors k to 50 when GMM reduction is used, as there are now less positive neighbors. Affinity matrix with Dong's algorithm [START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF]. We compare the exhaustive construction of matrix A to Dong's efficient k-NN graph algorithm [START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF] Truncation is a means to handle large scale datasets, i.e. more than 100k images. Regional diffusion on the full dataset takes 13.9s for Oxford105k, which is not practical. We therefore rank images according to the aggregated regional descriptors, which is equivalent to the R-MAC representation [START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF], and then perform diffusion on a short-list. (AP: 43.1→84.9) 0.5→100 0.6→100 1.8→100 0.6→98.7 2.6→100 2.6→100 0.4→97.7 1.6→98.8 3.3→100 0.4→96.7 4.5→100 3.7→98.8

(AP: 24.0→89.9) 3.1→100 4.2→100 4.3→100 4.7→100 5.9→100 5.9→100 6.4→100 7.0→100 7.0→100 7.0→100 7.1→100 7.3→100 between global and regional diffusion. We measure precision at the position where each image is retrieved and report this under each image for global and regional diffusion. Average Precision (AP) is reported per query for the two methods.

Figure 5 reports results with truncation. The performance of the full database diffusion is nearly attained by re-ranking less than 10% of the database. The entire truncation and diffusion process on Oxford105k takes 1s, with truncation and re-normalization taking only a small part of it. In the following, search on Oxford105k and Paris105k is performed by truncating the top 10k images. This choice results in an affinity matrix A of around 200k regions. When GMM reduction is used, our short-list size is chosen so that A has 2M regions too, keeping re-ranking complexity fixed.

Our approach is scalable thanks to truncation: the shortlist length is fixed and so is the re-ranking time, regardless of the database size and the dimensionality of the descriptors. Although this shortlist contains a small fraction of the database, its significantly outperforms the baseline.

Small objects. We present quantitative and qualitative results revealing that images benefit from our method mainly when the depicted object is small and the scene is cluttered.

7 shows that the retrieved images with the highest increase of precision of regional compared to global diffusion contain small objects that the latter cannot see. Since the bounding boxes are available for all images of INSTRE, we quantitatively measure precision for all positive images: Figure 6 shows that the highest improvement indeed comes for objects with small relative size.

Comparison to other methods

We compare with the state-of-the-art approaches with global or regional representation, with or without query expansion. Table 2 summarizes the results. We implement three methods typically combined with BoW, namely Average Query Expansion (AQE) [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF], Spatially Constrained Similarity Measure (SCSM) [START_REF] Shen | Spatially-constrained similarity measure for large-scale object retrieval[END_REF] and Hello Neighbor (HN) [START_REF] Qin | Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors[END_REF]. AQE is also effective with CNN global representation [START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF][START_REF] Kalantidis | Crossdimensional weighting for aggregated deep convolutional features[END_REF][START_REF] Gordo | Deep image retrieval: Learning global representations for image search[END_REF]. A baseline for the regional scenario is R-match [START_REF] Razavian | Visual instance retrieval with deep convolutional networks[END_REF]. We additionally extend AQE to re-gional representation4 combined with the similarity used in R-match. Hamming Query Expansion5 (HQE) [START_REF] Tolias | Visual query expansion with or without geometry: refining local descriptors by feature aggregation[END_REF] is the only method not using CNNs, but local descriptors.

Regional diffusion significantly outperforms all other methods in all datasets. Global diffusion performs well on Paris because query objects almost fully cover the image in most of the database entries. This does not hold on IN-STRE, which contains a lot of small objects. The improvements of regional diffusion are in this case much larger.

Conclusion

We propose a retrieval approach capturing distinct manifolds in the description space at no additional cost compared to a single query. We experimentally show that it significantly improves retrieval of small objects and cluttered scenes. The conclusion is that as few as 5-10 regional CNN descriptors can convey important information on small objects while thousands of conventional local descriptors are typically needed. Thus, a regional affinity matrix becomes possible. Regional diffusion was not possible before. In contrast to prior work, we use the closed form solution of the diffusion iteration, obtained by the conjugate gradient method. Combined with our contributions on space efficiency, this achieves large scale search at reasonable query times. Using recent CNN architectures, we achieve state-ofthe-art and near optimal performance on two popular benchmarks and a recent more challenging dataset.

Figure 1 .

 1 Figure 1. Diffusion on a synthetic dataset in R 2 . Dataset points, query points and their k-nearest neighbors are shown in blue, red, and green respectively. Contour lines correspond to ranking scores after diffusion. In this work, points are region descriptors.

3Figure 2 .

 2 Figure2. Impact of the number of nearest neighbors k in the affinity matrix. mAP performance for global and regional diffusion on Oxford5k; baselines are R-MAC and R-match respectively.

Figure 4 .

 4 Figure 4. mAP performance for varying number of regional descriptors after learning a GMM per image. Symbol denotes global diffusion, and to the default number of regions (21) per image. Average diffusion time in seconds is shown in text labels.

Figure 5 .

 5 Figure 5. Retrieval performance (mAP) versus the shortlist size used for affinity matrix truncation.

Figure 6 .

 6 Figure 6. Precision of each positive image measured at the position where it was retrieved, averaged over positive images according relative object size. Statistics computed on INSTRE over all queries for global and regional diffusion.

(Figure 7 .

 7 Figure7. Query examples from INSTRE, Oxford, and Paris datasets and retrieved images ranked by decreasing order of ranking difference between global and regional diffusion. We measure precision at the position where each image is retrieved and report this under each image for global and regional diffusion. Average Precision (AP) is reported per query for the two methods.

  , forming Oxford105k and Paris106k datasets. The third corpus is the recently introduced instance search dataset called INSTRE [55]. It contains various everyday 3D or planar objects from buildings to logos

	Pooling INSTRE Oxf5k Oxf105k Par6k Par106k
	sum GMP	79.1 80.0	92.2 93.2	90.6 91.6	96.1 96.5	94.4 94.6

Table 2 .

 2 Performance comparison to the state of the art. Results from original publications are marked with † , otherwise they are based on our implementation. Our methods are marked with . Points at 512D are extracted with VGG[START_REF] Radenović | CNN image retrieval learns from BoW: Unsupervised fine-tuning with hard examples[END_REF] and at 2048D with ResNet101[START_REF] Gordo | End-to-end learning of deep visual representations for image retrieval[END_REF]. Regional diffusion with 5 regions uses GMM.

	Method	m × d INSTRE Oxf5k Oxf105k Par6k Par106k
	Global descriptors -nearest neighbor search
	CroW [30] † R-MAC [43] R-MAC [19] NetVLAD [1] †	512 512 47.7 -2,048 62.6 4,096 -	68.2 77.7 83.9 71.6	63.2 70.1 80.8 -	79.8 71.0 84.1 76.8 93.8 89.9 79.7 -
	Global descriptors -query expansion
	R-MAC [43]+AQE [8] R-MAC [43]+SCSM [48] R-MAC [43]+HN [42] Global diffusion R-MAC [19]+AQE [8] R-MAC [19]+SCSM [48] Global diffusion	512 57.3 512 60.1 512 64.7 512 70.3 2,048 70.5 2,048 71.4 2,048 80.5	85.4 85.3 79.9 85.7 89.6 89.1 87.1	79.7 80.5 -82.7 88.3 87.3 87.4	88.4 83.5 89.4 84.5 92.0 -94.1 92.5 95.3 92.7 95.4 92.5 96.5 95.4
	Regional descriptors -nearest neighbor search
	R-match [44] R-match [44]	21×512 55.5 21×2,048 71.0	81.5 88.1	76.5 85.7	86.1 79.9 94.9 91.3
	Regional descriptors -query expansion
	HQE [51] R-match [44]+AQE [8] Regional diffusion Regional diffusion R-match [44]+AQE [8] 21×2,048 77.1 2.4k×128 74.7 89.4 † 84.0 † 82.8 † 21×512 60.4 83.6 78.6 87.0 81.0 -5×512 77.5 91.5 84.7 95.6 93.0 21×512 80.0 93.2 90.3 96.5 92.6 91.0 89.6 95.5 92.5 Regional diffusion 5×2,048 88.4 95.0 90.0 96.4 95.8 Regional diffusion 21×2,048 89.6 95.8 94.2 96.9 95.3

Imagine the case of multiple users querying at the same time; a different matrix per query is required. Also, updating mutual neighbors requires k-NN lists which are not available any longer.

We adopt the standard linear system notation in this section; matrix A is not to be confused with our affinity matrix defined in[START_REF] Arandjelović | NetVLAD: CNN architecture for weakly supervised place recognition[END_REF].

AQE has not been proposed in a regional scenario. We extend it as competitive baseline derived from prior work.

We evaluated HQE on INSTRE for the purposes of this work.

Acknowledgments The authors were supported by the MSMT LL1303 ERC-CZ grant. The Tesla K40 used for this research was donated by the NVIDIA Corporation.


Andrey Polyakov
email: andrey.polyakov@inria.fr

Jean-Michel Coron
email: coron@ann.jussieu.fr

Lionel Rosier
email: lionel.rosier@mines-paristech.fr

On Boundary Finite-Time Feedback Control for Heat Equation

The paper deals with boundary finite-time control for heat system. A linear switching control with state dependent switchings is designed based on backstepping procedure. It steers any solution of the heat system to zero in a finite time. The theoretical results are supported by numerical simulations.

INTRODUCTION

Finite-time control and estimation problems for plants described by ordinary differential equations are well-known in the literature (see, for example, [START_REF] Haimo | Finite time controllers[END_REF], [START_REF] Coron | Adding an integrator for the stabilization problem[END_REF], [START_REF] Bhat | Finite time stability of continuous autonomous systems[END_REF], [START_REF] Levant | Homogeneity approach to high-order sliding mode design[END_REF], [START_REF] Polyakov | Finite-time and Fixed-time Stabilization: Implicit Lyapunov Function Approach[END_REF]). The interest to such control problems is caused by different reasons. On the one hand, finite-time convergence of observer state to the real state of the plant is the simplest way to realize the separation principle for nonlinear control systems. On the other hand, time constraints appear in many control problems and finite-time algorithms is the simplest way to fulfil them. The finite-time control of partial differential equations is a topic of intensive research in the last years (see, e.g. [START_REF] Perrollaz | Finite-time stabilization of 2x2 hyperbolic systems on tree-shaped networks[END_REF]; Coron et al. (2015); [START_REF] Coron | Null controllability and finite time stabilization for the heat equa-tions with variable coefficients in space in one dimension via backstepping approach[END_REF]; [START_REF] Hu | Finite-time backstepping boundary stabilization of 3x3 hyperbolic systems[END_REF]; [START_REF] Alabau-Boussouira | Finite-time stabilization of a network of strings[END_REF]). It is worth stressing that this problem is also related with analysis of exact controllability and exact null controllability of plants described by partial differential equations.

The present paper treats the problem of boundary feedback control design, which steers any solution of the heat system to zero in a finite time. We consider the heat system on the segment [0, 1] with boundary conditions of Dirichlet type. The right boundary condition is controlled while the left one is homogeneous (zero). The similar problem has been studied in [START_REF] Coron | Null controllability and finite time stabilization for the heat equa-tions with variable coefficients in space in one dimension via backstepping approach[END_REF], where a linear boundary control with a time varying and piecewise constant "feedback gain" has been designed. The "feedback gain" in this context is a linear continuous functional K : L 2 ((0, 1), R)) → R, which maps the current state of the heat system to R in order to define the control signal (the right boundary condition to the system). This paper develops a novel piecewise linear boundary control with a state dependent switching law for the "feedback gain". Analogously to [START_REF] Coron | Null controllability and finite time stabilization for the heat equa-tions with variable coefficients in space in one dimension via backstepping approach[END_REF] the backstepping transformation is utilized for feedback design and finite-time convergence analysis of the closed-loop system. We the reader to [START_REF] Boskovic | Boundary control of an unstable heat equation via measurement of domain-averaged temperature[END_REF], [START_REF] Krstic | Boundary Control of PDEs: A Course on Backstepping Designs[END_REF] for more details about backstepping approach to boundary control design of PDEs.

The paper is organized as follows. The next section presents problem statement and basic assumptions. In the section 3 the main idea of finite-time stabilization by means of piecewise linear feedback control as well as some related problems are discussed. After that the boundary linear switching feedback control with state dependent switchings is designed, settling time of the closed-loop system is estimated and some modifications of the control allowing global fixed-time stabilization as well as tuning of the settling time are proposed. The numerical simulation results are presented in the end of the section 4. The paper is finished with concluding remarks and a list of bibliographic references.

Notation. The mainly paper uses the standard notations. For instance,

• R is the field of real numbers and

R + = [0, +∞); • Z is the set of integers; • • denotes the canonical norm in L 2 ([0, 1], R).

PROBLEM STATEMENT

Let us consider the heat system

∂v ∂t = ∂ 2 v ∂x 2 , v(0) = v 0 (1) with boundary control ζ (v(t))(0) = 0 (v(t))(1) = ζ(t), t > 0 (2) where v(t) ∈ L 2 ((0, 1), R).
The control aim is to steer the state v(t) of the system (1), (2) to zero in a finite time by means of a linear switching feedback control

ζ(t) = K σ(t) v(t), (3)
where K i : L 2 ((0, 1), R) → R, i ∈ Z is a family of linear bounded functionals and σ : R + → Z is a state dependent switching function governed by the discrete equation

σ(t) = G(σ(t -), v(t -)), (4) with G : Z × L 2 ((0, 1), R) → Z, t -= t + 0 -and σ(0) ∈ Z.
The hybrid (switched) linear system (1) -( 4) has two components: v(t) -continuous state and σ(t) -discrete state. Therefore, its solution is a tuple (v, σ) : v ∈ C 0 ([0, T ), L 2 ((0, 1), R)) and σ : (0, T ) → Z such that σ(t) satisfies the discrete equation ( 4) for all t ∈ (0, T ) and v is a solution to the heat system (1) -(3) understood in the weak sense:

- 1 0 v 0 (x)ξ(0, x)dx - T 0 1 0 v(t, x)ξ t (t, x)dxdt + T 0 K σ(t) v(t, •)ξ x (t, 1)dt - T 0 1 0 v(t, x)ξ xx (t, x)dxdt = 0 for all ξ ∈ C 2 ([0, T ) × [0, 1]) with compact support in [0, T ) × [0, 1] such that ξ vanishes at [0, T ) × {0, 1}.
We refer reader, for example, to [START_REF] Coron | Null controllability and finite time stabilization for the heat equa-tions with variable coefficients in space in one dimension via backstepping approach[END_REF] for more details about existence of solutions to (1) -(3) in the case of state independent switchings. All required information about hybrid and switched systems can be found in [START_REF] Goebel | Hybrid Dynamical Systems: modeling, stability, and robustness[END_REF], [START_REF] Liberzon | Switching in Systems and Control[END_REF].

ON FINITE-TIME STABILIZATION BY MEANS

OF SWITCHED LINEAR FEEDBACK

The basic idea

Let us consider the simplest scalar control system ẋ(t) = u(t), t > 0, (5) where x(t) ∈ R is the system state and u(t) ∈ R is the control. To stabilize the origin of this system in a finite time the discontinuous feedback control

u(t) = u d (x(t)) := -x(t) |x(t)|
can be utilized. Indeed, the Filippov solution (see [START_REF] Filippov | Differential Equations with Discontinuous Righthand Sides[END_REF]) to the closed-loop system is given by

|x(t)| = |x(0)|-t if t∈[0,x(0)], 0 if t>|x(0)|.
The problem of finite-time stabilizing control design is well-studied for finite-dimensional plants. For example, in [START_REF] Coron | Adding an integrator for the stabilization problem[END_REF], [START_REF] Bhat | Geometric homogeneity with applications to finite-time stability[END_REF], [START_REF] Andrieu | Homogeneous Approximation, Recursive Observer Design, and Output Feedback[END_REF], [START_REF] Levant | Homogeneity approach to high-order sliding mode design[END_REF], [START_REF] Polyakov | Finite-time and Fixed-time Stabilization: Implicit Lyapunov Function Approach[END_REF] non-linear continuous and discontinuous control algorithm are developed for linear systems. The problem of finitetime stabilization of infinite dimensional systems (see [START_REF] Efimov | Comments on finite-time stability of time-delay systems[END_REF], [START_REF] Perrollaz | Finite-time stabilization of 2x2 hyperbolic systems on tree-shaped networks[END_REF], Coron 2015)) is more complicated, since usually an analysis of non-linear infinite dimensional systems is nontrivial. In order to overcome this difficulty a linear time-varying piecewise linear boundary control has been presented [START_REF] Coron | Null controllability and finite time stabilization for the heat equa-tions with variable coefficients in space in one dimension via backstepping approach[END_REF] for parabolic PDEs. Linear static feedback usually provides exponential convergence rate to the closed-loop system. In order to provide finite-time (hyper-exponential) stability to the closed-loop system linear system the gains must vary in time [START_REF] Coron | Null controllability and finite time stabilization for the heat equa-tions with variable coefficients in space in one dimension via backstepping approach[END_REF]).

Let us consider a piecewise linear approximation of u d :

u pl (x(t)) = - x(t) r i if |x(t)| ∈ (r i+1 , r i ], i ∈ Z, (6)
where r i > 0 are some parameters. The presented approximation is a bounded function (see, Fig. 1). The origin of the closed-loop system with control u pl is asymptotically stable. Indeed, since its solution satisfies the identity

|x(t i+1 )| = e - t i+1 -t i r i |x(t i )|, where t i : |x(t i )| = r i and i ∈ Z, then, obviously, |x(t i )| → 0.
To guarantee finite-time stability the parameters r i , i ∈ Z should be properly selected such that t i+1 -t i < +∞.

For example, if

r i = 2 -i then t i+1 -t i = ln 2 2 i and ∞ i=i0 t i+1 -t i = ln 2 2 i0-1 < +∞.
In order to stabilize the origin of a control system in a finite time by means of switching linear feedback its gain must tends to infinity as the norm of state tends to zero.

The results of the numerical simulations for the considered switched system with x(0) = 0 are given at Fig. 2. The simulation has been done using implicit Euler method.

The solution is plotted in a logarithmic scale in order to show that it decreases exponentially in-between switching instances.

Overshooting problem

Note that feasibility of the finite-time control design scheme presented above is not straightforward for multidimensional case. Indeed, let us consider the controlled double integrator where x(t) = (x 1 (t), x 2 (t)) ∈ R 2 is the state vector and u is the scalar control input. Following the basic idea given above we apply the piecewise linear switching control

ẋ1 (t) = x 2 (t), ẋ2 (t) = u(t) (7)
u sw (t) = 1 r i (k 1 x 1 (t) + k 2 x 2 (t)) if x R 2 ∈ (r i+1 , r i ]. ( 8
)
where the gains k 1 < 0 and k 2 < 0 and {r i } is a monotone decreasing sequence such that r i → 0 as i → +∞.

For any fixed r i > 0 the closed-loop system ( 7)-( 8) is asymptotically stable. However, in contrast to the scalar case, we cannot guarantee anymore that the norm of the state will monotonically decrease in time. Moreover, linear control system with high gains may have large deviations from initial conditions.

The results of numerical simulations are depicted at Fig. 3 for the considered planar system with k 1 = 100, k 2 = 1, r i = 2 -i , i ∈ Z. They confirm our suspicion showing that the norm x(t) of the solution to the closed-loop system (7)-( 8) oscillates and the switchings of control result sequential decreasing and increasing of the gains. The rigorous stability analysis of such system is complicated, since, for example, it is necessary to prove that the presented switching law does not invokes sliding modes (or Zeno behaviour) or their appearance does not prevent finite-time convergence.

The problem of large deviations of high gain linear control systems is well known in the literature (see e.g. [START_REF] Izmailov | The "peak" effect in stationary linear systems with scalar inputs and outputs[END_REF], [START_REF] Polyak | Large deviations in linear control systems with nonzero initial conditions[END_REF] and references therein). It has similar nature to the well-known phenomenon called overshoot, which may provoke, for example, instability to linear switched systems even if each subsystem is stable (Liberzon, 2003, Chapter 2).

To simplify an analysis and design of finite-time stabilizing control the switching logic should be properly modified for the multidimensional (as well as for infinite dimensional) case. The simplest way is to use time dependent switchings. Such algorithms has been developed, for example, in [START_REF] Coron | Null controllability and finite time stabilization for the heat equa-tions with variable coefficients in space in one dimension via backstepping approach[END_REF], [START_REF] Efimov | On acceleration of a class of asymptotically stable homogeneous systems[END_REF]. The main drawback of time dependent approach is insufficient robustness. Since feedback gain increases independently of the state, then small computational errors or measurement noises may induce huge stabilization error at the terminal instant of time.

An alternative solution is presented for planar system in Anan'evskii (2003), where the Lyapunov function has been utilized in (8) instead of Euclidian norm x(t) R 2 .

In [START_REF] Polyakov | Finite-time and Fixed-time Stabilization: Implicit Lyapunov Function Approach[END_REF], [START_REF] Polyakov | Robust stabilization of mimo systems in finite/fixed time[END_REF] the similar scheme has been developed for multidimensional linear systems using a so-called canonical homogeneous norm (being implicit Lyapunov function to the system).

The switching law is designed in such a way that the homogeneous norm of the closed-loop system decreases monotonically all the time (in disturbance-free case) independently of the switching instances. In [START_REF] Polyakov | On Homogeneous Finite-Time Control For Evaluation Equation in Hilbert Space[END_REF] this scheme has been adapted to abstract linear evolution equations in Hilbert spaces, where the particular switching law guaranteeing the finite-time convergence of the closed-loop system to zero is given. Unfortunately, the homogeneous norm mentioned above is frequently defined in an implicit way [START_REF] Polyakov | Finite-time and Fixed-time Stabilization: Implicit Lyapunov Function Approach[END_REF], Polyakov et al. (2016a)). Difficulty of its on-line computation is the main drawback of the control scheme based on the canonical homogeneous norm.

In this paper we design a hybrid finite-time boundary control for heat system. In order to avoid problems mentioned above we introduce a novel state dependent switching law that excludes sliding mode or Zeno behavior (see, e.g. [START_REF] Liberzon | Switching in Systems and Control[END_REF], Chapter 1)) outside the origin and restricts the overshoot as follows :

x(t) < r i-1 for all t > t i , where t i > 0 is a state dependent switching instant such that x(t i ) = r i . It is worth stressing that the switching law uses the conventional L 2 -norm of the state simplifying the practical realization of the control scheme.

BOUNDARY FINITE-TIME CONTROL FOR HEAT SYSTEM

Backstepping transformation

Given positive number λ > 0 the backstepping approach (see, [START_REF] Boskovic | Boundary control of an unstable heat equation via measurement of domain-averaged temperature[END_REF], [START_REF] Coron | Null controllability and finite time stabilization for the heat equa-tions with variable coefficients in space in one dimension via backstepping approach[END_REF] for the details) introduces the boundary control

ζ(t) = 1 0 k(1, y, λ)v(t, y)dy (9)
where k(x, y, λ) = -λy

I1( √ λ(x 2 -y 2 )) √ λ(x 2 -y 2 ))
and I m with m ∈ Z is the modified Bessel function of the first kind (see e.g. [START_REF] Watson | A Treatise on the Theory of Bessel Functions[END_REF]). If we denote

(F (λ)u)(x) = - x 0 k(x, y, λ)u(y)dy (10)
then the state transformation u = v + F (λ)v applied to the system (1), (2) yields

∂u ∂t = ∂ 2 u ∂x 2 -λu, u(t, 0) = 0, u(t, 1) = 0. ( 11
)
The inverse transformation is defined as v = (I + F (-λ))u, where u, v ∈ L 2 ((0, 1), R). We refer reader to [START_REF] Boskovic | Boundary control of an unstable heat equation via measurement of domain-averaged temperature[END_REF] and [START_REF] Coron | Null controllability and finite time stabilization for the heat equa-tions with variable coefficients in space in one dimension via backstepping approach[END_REF] for more details about backstepping transformation.

It is easy to see (using the Lyapunov function defined as V (u) = u 2 ) that the system ( 11) is asymptotically stable and u(t) ≤ u(0) e -λt .

Following [START_REF] Coron | Null controllability and finite time stabilization for the heat equa-tions with variable coefficients in space in one dimension via backstepping approach[END_REF] we also use the backstepping transformation in order to design a finite-time control of the form (9) with switching parameter λ. The system (11) will be utilized as a sort of comparison system in order to prove stability and finite-time convergence of solution to zero as well as to estimate the settling time.

Proposition 1. If z ∈ L 2 ((0, 1), R) then z + F (λ)z ≤ Ψ 1 (λ) z and z + F (-λ)z ≤ Ψ -1 (λ) z , Ψ 1 (λ) = 1 + λ 1 0 x 0 y 2 I0 √ λ(x 2 -y 2 ) -I2 √ λ(x 2 -y 2 ) 2 dydx 2 , Ψ -1 (λ) = 1 + λ 1 0 x 0 y 2 J0 √ λ(x 2 -y 2 ) +J2 √ λ(x 2 -y 2 ) 2 dydx 2
, where J k is the Bessel function of the first kind.

Proof. The proof of this proposition immediately follows from the identities (Temme, 1966, pages 229, 233 and 234)

I k (p) = p 2 (I k-1 (p) -I k+1 (p), J k (p) = p 2 (J k-1 (p) + J k+1 (p) and I k (p) = i -k J k (ip), where p ∈ R, i = √ -1 and k ∈ Z.

The main result

Now let us consider the heat system (1), ( 2) with the hybrid boundary feedback control

ξ(t) = 1 0 k 1, y, 2 σ(t) v(t, y)dy, ( 12
)
where the switching function σ is governed by the equation ( 4) with (13) where r 0 = 1, r i = e -qi r i-1 , i ∈ Z and the numbers q i are defined by formula ( 14). Proposition 2. If q i = ln Ψ 1 2 i + ln Ψ -1 2 i , (14) then q i > 0 for all i ∈ Z, r i → 0 as i → +∞ and

G(σ, v) = i+1 if σ = i and v ≤ r i+1 , i if σ = i and r i+1 < v < r i-1 , i-1 if σ = i and v ≥ r i-1 ,
lim i→+∞ q i+1 q i = √ 2.
Proof. Using the representations (see, (Watson, 1996, page 181), (Temme, 1966, page 230)) [START_REF] Coron | Null controllability and finite time stabilization for the heat equa-tions with variable coefficients in space in one dimension via backstepping approach[END_REF]). Hence, q i > 0 for all i ∈ Z, q i → +∞ as i → +∞, r i → 0 as i → +∞ and

I k (p) = 1 π π 0 e p cos(θ) cos(kθ)dθ, J k (p) = 1 π π 0 cos(kθ -p sin(θ))dθ, it can be shown 1 + Cλe √ Cλ ≤ Ψ 1 (λ) ≤ 1 + λe √ λ for some C > 0 and 1 ≤ Ψ -1 (λ) ≤ 1 + λ (see, also
qi+1 qi = ln Ψ1(2 i+1 )+ln Ψ-1(2 i+1 ) ln Ψ1(2 i )+2 ln Ψ-1(2 i ) = √ 2 i+1 +ln Ψ 1 (2 i+1 ) exp ( √ 2 i+1 ) +ln Ψ-1(2 i+1 ) √ 2 i +ln Ψ 1 (2 i ) exp ( √ 2 i ) +ln Ψ-1(2 i ) → √ 2 as i → +∞.
Theorem 1. (On finite-time stability). For any initial condition v(0) = v 0 ∈ L 2 ((0, 1), R) (15) and σ(0

) = i 0 ∈ Z with v(0) ∈ (r i0+1 , r i0 ] , (16)
the system (1), ( 2), ( 12), ( 4), ( 13) has a unique solution

(v, σ) : v ∈ C 0 ([0, T ), L 2 ((0, 1), R)) and σ : (0, T ) → Z such that v(t) → 0 as t → T -, where T ≤ +∞ i=i0 q i + q i+1 2 i < +∞. (17)
Proof. I. First of all, let us note that if σ(t) = i, ∀t > 0 then for any initial condition v 0 ∈ L 2 ((0, 1), R) the system (1), ( 2), ( 12) has a unique solution v i ∈ C 0 ([0, +∞), L 2 ((0, 1), R)) which vanishes at zero as time tends to infinity (see, e.g. [START_REF] Coron | Null controllability and finite time stabilization for the heat equa-tions with variable coefficients in space in one dimension via backstepping approach[END_REF]). Hence, if v i (t i ) ∈ (r i+1 , r i ] and σ(t) = i then there always exists an instance of time t * > 0 separated from

t i such that v i (t * ) = r i+1 or v i (t * ) = r i-1
. This means that the discrete state σ will be switched to i + 1 or to i -1 according to law (4), ( 13) and switching instant t * will always be isolated. Therefore, similarly to (Coron and Nguyen, 2015, Lemma 6) it can be shown that for any initial conditions ( 15), (16) the hybrid system (1), ( 2), ( 12), ( 4), ( 13) has a unique solution (v, σ) such that v ∈ C 0 ([0, T ), L 2 ((0, 1), R)), T = sup t j where t j > 0 :

v(t j ) = r ij , i j ∈ Z, j = 1, 2, ... are isolated instances of time and σ(t) = i j for t ∈ [t ij , t ij+1 ) satisfies the discrete equation ( 4) with the switching law (13).

II. Let us show that v(t) < r ij -1 for t > t j if v(t j ) ≤ r ij and σ(t) = i j . Since due to backstepping transformation the function u ij = (I + F (2 ij ))v is the solution to (11) with λ = 2 ij then it is easy to see that u ij (t) ≤ e -2 i j (t-tj ) u ij (t j ) , i.e. u ij (t) < u ij (t j ) for t > t j . On the other hand, since

u ij (t) ≤ Ψ 1 (2 ij ) v(t) and v(t) ≤ Ψ -1 (2 ij ) u ij (t) then v(t) < Ψ 1 (2 ij )Ψ -1 (2 ij ) v(t j ) = e qi j v(t j )
≤ e qi j r ij = r ij -1 for t > t j . This immediately implies that i j+1 = i j +1 and v(t) → 0 as t → T -. III. Let us show that T < +∞. It has been noted above that u ij (t) ≤ e -2 i j (t-ti j ) u ij (t ij ) . Hence, we derive

t j+1 -t j ≤ 1 2 i j ln ui j (tj ) ui j (tj+1) ≤ 1 2 i j ln Ψ1(2 i j )Ψ-1(2 i j ) v(tj ) v(tj+1)
.

Taking into account v(t j ) = r ij , v(t j+1 ) = r ij+1 = e -qi j+1 r ij , i j+1 = i j + 1 and the formula ( 14) we obtain

T ≤ +∞ j=0 t j+1 -t j ≤ +∞ j=0 1 2 ij ln e qi j r ij r ij +1 = +∞ i=i0 q i + q i+1 2 i = 3 +∞ i=i0 q i 2 i -2 q i0 2 i0 .
Due to Proposition 2 we have

lim i+∞ 2 -(i+1) q i+1 2 -i q i = 1 2 lim i+∞ q i+1 q i = 1 √ 2 < 1.
and 2 -i q i → 0 as i → ∞ since q i = O( √ 2 i ) for i → +∞. Hence, the ratio test for convergent series guarantees T < +∞.

Small modification of the presented control law allows us to stabilize the heat system in a fixed time independently of the initial conditions. Corollary 1. (On fixed-time stability). If the parameters q i are redefined for i < 0 as follows q -k := q k , k = 1, 2, 3, ... and

ξ(t) = 1 0 k 1, y, 2 |σ(t)| v(t, y)dy, (18)
then Theorem 1 remains true but the settling time T becomes globally bounded

T ≤ +∞ i=-∞ q i + q i+1 2 i < +∞.
independently of the initial condition v 0 ∈ L 2 ((0, 1), R).

Note also that the settling time T can be tuned by means of minor change of the control law

ξ(t) = 1 0 k 1, y, ρ2 σ(t) v(t, y)dy,
and the parameters q i = ln Ψ 1 ρ2 i + ln Ψ -1 ρ2 i where ρ > 0 is a tuning parameter. In this case the estimate (17) becomes

T ≤ 1 ρ +∞ i=i0 q i + q i+1 2 i < +∞.

Numerical example

The simulation result for boundary finite-time control application to heat system with the initial condition v(0, x) = 5.35x(1-x) is depicted at Fig. 4. For numerical simulations the state system has been discretized by divided differences on a uniform grid with the step h = 0.02 for the space variable. The discretization with respect to time has been done using implicit Euler scheme with the step size τ = h 2 . All integrals are approximated by means of trapezoidal rule. It can bee seen from the Fig. 4 that the switching of the "feedback gain" implies the jump in the right boundary condition, but the solution to the controlled heat system remains continuous in L 2 -norm.

The Fig. 5 presents the evolution of the norm v(t) in time with a logarithmic scale in order to confirm on simulations that the convergence to zero is faster than exponential one. Note that the numerical simulations also demonstrates "overshooting" (fast transition) after each switching instance and confirms the fact rigorously proven in Theorem 1 : an overshooting after each switching instant t j > 0 : v(t j ) = r ij is always less than the precedent switching level r ij -1 .

CONCLUSIONS

In the paper the boundary linear switching feedback control with state dependent switchings is designed for heat system on the segment [0, 1]. It steers any solution of the closed-loop system to zero in a finite-time. Switching nature of the feedback invokes a sort of overshooting phenomenon: fast relatively large deviations of the solution from the state at switching instant of time during transient process. This phenomenon is well known even for finitetime dimensional control systems. In our case the switching law is designed in such a way that the overshooting is sufficiently small to avoid unnecessary switchings and to This theoretical result is supported by numerical simulations where the overshooting has been visually observed when evolution of the norm of the solution is plotted in the logarithmic scale (Fig. 5). Finite-time feedback control with state dependent switchings is expected to be robust (in ISS sense) with respect to different types of uncertainties/disturbances. A rigorous study of this issue can be considered as a possible direction for future research.

ACKNOWLEDGMENTS

This research was supported by ANR 15 CE23 0007 (Project Finite4SoS). The first author also acknowledges the Government of Russian Federation (Grant 074-U01) and the Ministry of Education and Science of Russian Federation (Project 14.Z50.31.0031).

Fig. 1 .

 1 Fig. 1. Relay feedback and its piecewise linear approximation (r i = 2 -i ) and Nguyen (2015), Alabau-Boussouira et al. (2015)) is more complicated, since usually an analysis of non-linear infinite dimensional systems is nontrivial. In order to overcome this difficulty a linear time-varying piecewise linear boundary control has been presented[START_REF] Coron | Null controllability and finite time stabilization for the heat equa-tions with variable coefficients in space in one dimension via backstepping approach[END_REF] for parabolic PDEs. Linear static feedback usually provides exponential convergence rate to the closed-loop system. In order to provide finite-time (hyper-exponential) stability to the closed-loop system linear system the gains must vary in time[START_REF] Coron | Null controllability and finite time stabilization for the heat equa-tions with variable coefficients in space in one dimension via backstepping approach[END_REF]).

Fig. 2 .

 2 Fig. 2. Solution to scalar system (5) with piecewise linear control (6)

Fig. 3 .

 3 Fig. 3. Solution to scalar system (7) with piecewise linear control (8)

Fig. 4 .

 4 Fig. 4. Evolution of heat equation with boundary finitetime control

Fig. 5 .

 5 Fig. 5. Evolution of L 2 -norms with finite-time and linear control laws guarantee finite-time convergence of the solution to zero.This theoretical result is supported by numerical simulations where the overshooting has been visually observed when evolution of the norm of the solution is plotted in the logarithmic scale (Fig.5). Finite-time feedback control with state dependent switchings is expected to be robust (in ISS sense) with respect to different types of uncertainties/disturbances. A rigorous study of this issue can be considered as a possible direction for future research.


Sergiy Zhuk
email: sergiy.zhuk@ie.ibm.com

Andrey Polyakov
email: andrey.polyakov@inria.fr

Olexander Nakonechnyi

Sliding Mode Control Design for Linear Evolution Equations with Uncertain Measurements and Exogenous Perturbations

Keywords: Robust Control, Sliding Mode Control, Distributed Parameter System

The paper studies the problem of sliding mode control design for linear evolution equations with incomplete and noisy measurements of the output and additive exogenous disturbances. The key result of the paper is an algorithm, generating an output-based feedback, which steers the state as close as possible to a given sliding hyperplane in a finite time. The optimality of the designed feedbacks is proven. The efficacy of the proposed algorithm is illustrated by a numerical example.

INTRODUCTION

Robust output-based feedback control algorithms are required for many practical applications. The output-based sliding mode control design methodology is well-developed for finite dimensional systems (see, for example, [START_REF] Edwards | Sliding-mode output feedback controller design using linear matrix inequalities[END_REF], [START_REF] Edwards | Sliding Mode Control: Theory And Applications[END_REF], [START_REF] Utkin | Sliding Mode Control in Electro-Mechanical Systems[END_REF], [START_REF] Shtessel | Sliding Mode Control and Observation[END_REF] and references therein). Infinite dimensional (distributed parameter) systems are widely used in practise, e.g., to model flexible robots, controlled turbulent flows, combustion and other chemical processes. The sliding mode methodology can also be used to design controllers for such complicated systems [START_REF] Orlov | Use of sliding modes in distributed system control problems[END_REF], [START_REF] Orlov | Application of lyapunov method in distributed systems[END_REF]. We refer the reader to Levaggi (2002a, 0, 1), [START_REF] Orlov | Discontinuous systems: Lyapunov analysis and robust synthesis under uncertainty conditions[END_REF], [START_REF] Pisano | Boundary second-order sliding-mode control of an uncertain heat process with unbounded matched perturbation[END_REF], [START_REF] Orlov | Boundary control and observer design for an uncertain wave process by second-order sliding-mode technique[END_REF] for an extensive overview of the recent achievements in this field.

We stress that, in practice, it is quite difficult to apply the state of the art sliding mode methods in the case of noisy measurements (see, [START_REF] Poznyak | Variable Structure Systems: from Principles to Implementation[END_REF]; [START_REF] Utkin | Sliding Modes in Control and Optimization[END_REF]) and/or mismatched disturbances (see, [START_REF] Castanos | Analysis and design of integral sliding manifolds for systems with unmatched perturbations[END_REF]; [START_REF] Edwards | Sliding mode stabilization of uncertain systems using only output information[END_REF]; [START_REF] Polyakov | Invariant ellipsoid method for minimization of unmatched disturbance effects in sliding mode control[END_REF]). The aim of this paper is to propose a mathematically sound extension of the sliding mode control methodology allowing one to deal with the aforementioned cases efficiently. Specifically, we consider conventional (first order) sliding mode control principles and study the problem of observer-based sliding mode control design for a plant described by a linear evolution equation in a Hilbert space with additive exogenous disturbances and L 2 -bounded deterministic measurement noises. Note that, in this case, the solution of the classical sliding model control problem does not exists, i.e., it is impossible to ensure the ideal/exact sliding mode (even in the finite dimensional case) due to the noise in the measurements. Following Zhuk and Polyakov (2014, 1, 1); [START_REF] Zhuk | Note on minimax sliding mode control design for linear systems[END_REF] we propose to generalize the notion of the solution of the classical sliding model control problem for linear evolution equations, i.e., to construct a control law u providing the state's motion as close as possible (in the minimax sense) to the selected sliding surface. To design such u we first provide a dual description of the reachability set for a linear evolution equation, and then solve the following minimax control problem: find a feedback control u steering the minimax center of the reachability set towards the sliding surface. The dual description of the reachability set relies upon the minimax framework [START_REF] Chernousko | State Estimation for Dynamic Systems[END_REF]; [START_REF] Kurzhanski | Ellipsoidal calculus for estimation and control[END_REF]; [START_REF] Milanese | Optimal algorithms theory for robust estimation and prediction[END_REF]; [START_REF] Poznyak | Minimax integral sliding-mode control for multimodel linear uncertain systems[END_REF] and duality argument Zhuk (2009, 1).

The paper is organized as follows. The next section presents the problem statement and basic assumptions. The minimax observer for linear systems is discussed in Section III. The problem of control design is studied in Section IV. Next the numerical simulation results and conclusions are provided. The proofs of the propositions are given in the appendix.

Throughout the paper the following notations are used: H, H u , H d , H y are abstract Hilbert spaces, x, y H denotes the canonical inner product of H, x 2 H := x, x H , L (H, H) denotes the space of linear continuous operators from H to H, A denotes the adjoint of a linear operator A, D(A) denotes the domain of A, I denotes the identity operator of the corresponding space, L 2 (0, T, H) denotes the space of squared integrable functions on (0, T ) with values in H.

PROBLEM STATEMENT

Assume that A : H → H generates a strongly continuous semigroup and t → x(t) ∈ H is the mild solution of the following linear evolution equation:

dx dt = Ax(t) + Bu(t) + Dd(t) , x(0) = x 0 , (1)
where

x 0 ∈ H -initial condition, u ∈ L 2 (0, T, H u ) - control function, d ∈ L 2 (0, T, H d ) -uncertain disturbance, and B ∈ L (H u , H), D ∈ L (H d , H) are given operators.
For the convenience of the reader we recall the concepts of strongly continous semigroups of linear operators and mild solutions at the beginning of appendix.

The output of (1), y(t) ∈ H y is measured in the following form:

y(t) = Cx(t) + w(t) , t ∈ [0, T ) , (2)
where C ∈ L (H, H y ) is an observation operator, which represents a mathematical model of a gauge, and w ∈ L 2 (0, T, H y ) is unknown deterministic measurement noise.

We further assume that x 0 , d, w are uncertain and belong to the following bounding set:

E (T ) := {(x 0 , d, w) : ρ T (x 0 , d, w; S, Q, R) ≤ 1} ⊂ H× L 2 (0, T, H d ) × L 2 (0, T, H y ) , (3)
where

ρ t (x, d, w; S, Q, R) := Sx, x H + t 0 Qd(s), d(s) H d ds + t 0 Rw(s),
(x0,d,w)∈E (T ) F x(T ) Hu → min u s.t. (1) -(2) (4)
We recall that the classical sliding mode control problem is (see, [START_REF] Orlov | Discontinuous systems: Lyapunov analysis and robust synthesis under uncertainty conditions[END_REF]; [START_REF] Utkin | Sliding Mode Control in Electro-Mechanical Systems[END_REF]) to find a feedback control law u which (i) steers the state of (1) towards a given linear hyperplane F x = 0, and (ii) guarantees that the state does not leave this plane, provided F B is a linear bounded invertible operator. It is worth noting [START_REF] Edwards | Sliding Mode Control: Theory And Applications[END_REF]; [START_REF] Utkin | Sliding Mode Control in Electro-Mechanical Systems[END_REF] that the latter condition (in finite dimensional case) is necessary for existence of a control law, which ensures sliding mode on the surface F x = 0. The problem of selection of the operator F is considered in [START_REF] Orlov | Discontinuous systems: Lyapunov analysis and robust synthesis under uncertainty conditions[END_REF]. Here we assume that a proper F has been selected.

DUAL DESCRIPTION OF THE REACHABILITY SET

According to the classical methodology of the sliding mode control design, the precise knowledge of the socalled sliding variable σ(t) := F x(t) is required in order to ensure the motion of the system (1) on the surface F x = 0. In the considered case this information is not available as the output y(t) is incomplete and noisy and state equation is subject to uncertain disturbances. In the following proposition we construct the a priori reachability set of the evolution equation (1), i.e., the set of all the states of (1) which are compatible with all possible outputs y and uncertainty description E (T ). This representation is then used to solve (4). Proposition 1. Assume that x is a mild solution of (1) for some (x 0 , d, w) ∈ E (T ). Then, for any t * ∈ [0, T ] the following estimate holds true:

sup (x0,d,w)∈E (t * ) | l, x(t * ) -x(t * ) H | = l, P (t * )l 1 2 H , ∀l ∈ H , (5) where
• the linear bounded self adjoint positive definite operator P is the unique solution of the following infinitedimensional differential Riccati equation:

d dt P (t)v, q H = P (t)A v, q H + P (t)v, A q H + DQ -1 D v, q H -P (t)C RCP (t)v, q H , P (0) = S -1 , (6)
• x is the unique mild solution of the following evolution equation:

dx(t) dt = Ax(t) + P (t)C R(y(t)-C x(t)) + Bu(t), x(0) = 0 , (7)
The proofs of the propositions are omitted for shortness. Using (Balakrishnan, 1981, p.339, Th.6.8.3) the next corollary can also be proven.

Corollary 1. Assume that A, D and A , C are exponentially stabilizable. Then

lim t→+∞ | l, x(t) -x(t) H | ≤ l, P ∞ l 1 2 H , ∀l ∈ H , ( 8
)
where P ∞ is the unique self adjoint solution of the algebraic Riccati equation:

P ∞ v, A v H + A v, P ∞ v H + Q -1 D v, D v H -RCP ∞ v, CP ∞ v H . (9)
In addition, A -P ∞ C RC generates an exponentially stable semigroup.

It is worth noting that (5) is describing an ellipsoid, which is centered at vector x(T ) with axes defined by eigenfunctions of P (T ). This ellipsoid is, in fact, the worstcase realisation of the reachability set of (1), i.e., it takes into account all (x 0 , d, w) ∈ E (T ). The estimate (8) describes an ellipsoid which contains all the states of (1) in the limit t → ∞. Finally, we stress that P does not depend on the control parameter u. This suggests to design the controller u as a function of the center of the ellipsoid, x.

CONTROL DESIGN

Denoting the sliding variable by σ = F x we derive

σ(T ) = F x(T ) = σ(T ) + F e(T ), | l, e(T ) H | ≤ l, P (T )l 1 2
H , ∀l ∈ H, where σ(T ) = F x(T ), and x satisfies (7). Proposition 2. If the control u verifies the following equality: σ(T ) = 0 (10) then it solves the minimax control problem (4).

Usually (see, e.g. [START_REF] Orlov | Discontinuous systems: Lyapunov analysis and robust synthesis under uncertainty conditions[END_REF], [START_REF] Levaggi | Existence of sliding motions for nonlinear evolution equations in banach space[END_REF]), additional technical considerations are required in order to apply a discontinuous sliding mode control and prove the existence of solutions in this case. The latter proposition allows us to construct a continuous feedback control which verifies the condition (10): indeed, define

u eq (t)=-(F B) -1 F [Ax(t)+P (t)C R(y(t)-C x(t))] , (11)
We claim that u eq solves the problem (4). Indeed, ∀v ∈ H u this feedback provides

F x(t), v Hu = t 0 F Ax(s)+F P (s)C R(y(s)-C x(s))+F Bu(s), v Hu ds = t 0 (F-F B(F B) -1 F )[Ax(s)+P (s)C R(y(s)-C x(s))],
v Hu ds = 0. In fact, this feedback is an analog of "equivalent control" in a sliding mode control system, which can be found explicitly: indeed, u eq depends on P and x which, in the case of observer-based control design, can be computed (numerically or even analytically in some cases considered in the following section). Moreover, x starts at the linear sliding hypersurface F x = 0 as x(0) = 0 so the minimax center of the reachability set stays on the hyperplane F x = 0 and the actual state x(t) fluctuates in the ellipsoid centered at x, i.e.,

| F x(t), v Hu | ≤ F v, P (t)F v 1 2 H , ∀v ∈ H u .
The speed at which x(t) approaches the sliding hyperplane is proportional to the speed of the decay of the corresponding eigen-values of P . In the infinite-horizon case, the actual state of the plant reaches the sliding surface exactly, provided F v, P ∞ F v 1 2 H = 0 for any v ∈ H u (see ( 8)).

EXAMPLE

In the numerical example we will present the analytical solutions of ( 6)-( 7) and derive the corresponding formula for the sliding mode control. To this end we assume that H = H and A is a linear symmetric operator such that -Aψ, ψ H ≥ c ψ 2 H for a given c > 0 and A has a complete orthogonal system of eigenvectors {e k }, i.e., e k is the unique solution of the following equation: We suppose that the observation operator, C is of finite rank, i.e., y i (t) = e i , x(t) H + w i , i = 1 . . . N and set R := I so that H y = R N and C RCx = N k=1 e k , x H e k . For simplicity we assume that N < M . In this setting, the Riccati equation reads as follows: = e i , e j H , for all e i and e j . The above equation is the scalar Riccati differential equation, and since e i , e j H = 0 if i = j, it follows that P (t)e i , e j H ≡ 0 if i = j and so we get that the Riccati operator P is diagonal, i.e., P (t)x = ∞ j=1 P i (t) e j , x H e j where P j solves an ODE of the following form: Ṗj = -2λ j P j + e j , e j H -P 2 j , P j (0) = 1 , j ≤ N , Ṗj = -2λ j P j + e j , e j H , P j (0) = 1 , j > N , As a result, the equation ( 7) reads as follows:

-Ae k , ψ H = λ k e k ,
d dt P (
d x(t), e i H dt = -λ i x(t
(t)(y i -e i , x H ) , i ≤ N , ûi (t) := λ i x(t), e i , N < i ≤ M , then û = M i=1 ûi ei 2
H e i realizes the desired sliding mode control which steers x to F x = 0 and keeps it there. Note that in this case the control becomes û = -

N i=1 Pi(t)yi ei 2 H e i .
For simulation we select

A = -∂ 2 ∂z 2 , D(A) = v ∈ L 2 (0, 1, R) : v(0) = v(1) = 0 . In this case, λ k = (πk) 2 , e k = √ 2 sin(kπz), z ∈ [0, 1]. Let N = 1 and M = 2 then Ṗ1 (t) = -2π 2 P 1 (t) + 1 -P 2 1 , P 1 (0) = 1, and u(t, z) = - √ 2P
1 (t)y 1 (t) sin(πz). The simulation has been done in MATLAB using pdepe command and grid method for 0 ≤ t ≤ 0.5 and 0 ≤ z ≤ 1. The perturbations have been selected as follows w 1 (t) = sign(sin(5t))/ √ 3 and (d(t))(z) = z(1-z)/ (3). The initial condition is selected as x(0) = z(1 -z). The result of simulation is presented at Fig. 1. The simulation has also been done for the uncontrolled case u = 0 showing that the designed control reduces the effect of perturbations almost twice: x(0.5) L2 = 0.0045 provided u eq has been applied, and x(0.5) L2 = 0.0083 without control application. The minimax sliding mode control which solves (4) generalizes the conventional sliding mode control: it steers the state of (1) towards the hyperplane F x(T ) = 0 as close as possible (in the minimax sense) as the exact reaching F x(T ) = 0, required in the definition of the conventional sliding mode control, cannot be guaranteed due to unknown measurement noises and uncertain model disturbances. We conjecture that the exact reaching may be guaranteed provided the model disturbance and measurement noise "disappear" after a given time instant T * . This latter question will require a modification of the differential Riccati equation and is left for the future research. We stress that the exact "numerical" reaching, i.e., the distance between the actual state x and the sliding hyperplane is negligible, is possible, provided the eigen-values of the Riccati operator P (t) rapidly decay to zero (see ( 5)), and the null-space of the algebraic Riccati operator P ∞ contains the sliding hyperplane.

  ∀ψ ∈ D(A). We further assume that B = I, D = I, S = I, Q = I where I denotes the identity operator in the corresponding space and F : H → R M is defined as follows F x(T ) = [ e 1 , x(T ) H . . . e M , x(T ) H ] .

Fig. 1 .

 1 Fig. 1. The simulation results for controlled heat equation

  t)e i , e j H = -λ i P (t)e i , e j H -λ j P (t)e i , e j H + e i , e j H -, e i H P (t)e k , e j H , P (0)e i , e j H

	N
	P (t)e k
	k=1

  ), e i -

N k=1 e k , x H P (t)e k , e i H + k y k (t) P (t)e k , e i H + u(t), e i H = -λ i x(t), e i + P i (t)(y i -e i , x H ) + u(t), e i H , x(0), e i H = 0 , i ≤ N ,

d x(t),ei H dt = -λ i x(t), e i H + u(t), e i H ,

x(0), e i H = 0 , i > N . Now, if we set ûi (t) := λ i x(t), e i -P i

ACKNOWLEDGMENTS

This research was partially supported by ANR Finite4SoS Project (ANR 15 CE23 0007).