How good is my GAN?

Generative adversarial networks (GANs) are one of the most popular methods for generating images today. While impressive results have been validated by visual inspection, a number of quantitative criteria have emerged only recently. We argue here that the existing ones are insufficient and need to be in adequation with the task at hand. In this paper we introduce two measures based on image classification---GAN-train and GAN-test, which approximate the recall (diversity) and precision (quality of the image) of GANs respectively. We evaluate a number of recent GAN approaches based on these two measures and demonstrate a clear difference in performance. Furthermore, we observe that the increasing difficulty of the dataset, from CIFAR10 over CIFAR100 to ImageNet, shows an inverse correlation with the quality of the GANs, as clearly evident from our measures.

Introduction
Generative Adversarial Networks (GANs) [19] are deep neural net architectures composed of a pair of competing neural networks: a generator and a discriminator. This model is trained by alternately optimizing two objective functions so that the generator G learns to produce samples resembling real images, and the discriminator D learns to better discriminate between real and fake data. Such a paradigm has huge potential, as it can learn to generate any data distribution. This has been exploited with some success in several computer vision problems, such as text-to-image [56] and image-to-image [24,59] translation, super-resolution [31], and realistic natural image generation [25].
Since the original GAN model [19] was proposed, many variants have appeared in the past few years, for example, to improve the quality of the generated images [12,15,25,36], or to stabilize the training procedure [7,9,20,34,36,40,57]. GANs have also been modified to generate images of a given class by conditioning on additional information, such as the class label [16,35,37,41]. There are a number of ways to do this: ranging from concatenation of label y to the generator input z or intermediate feature maps [16,35], to using conditional batch normalization [37], and augmenting the discriminator with an auxiliary classifier [41].
Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France. This work was supported in part by the ERC advanced grant ALLEGRO, gifts from Amazon, Facebook and Intel, and the Indo-French project EVEREST (no. 5302-1) funded by CEFIPRA. Fig. 1: State-of-the-art GANs, e.g., SNGAN [36], generate realistic images, which are difficult to evaluate subjectively in comparison to real images. Our new image classification accuracy-based measure (GAN-train is shown here) overcomes this issue, showing a clear difference between real and generated images.
With several such variants being regularly proposed in the literature, a critical question is how these models can be evaluated and compared to each other.
Evaluation and comparison of GANs, or equivalently, the images generated by GANs, is challenging. This is in part due to the lack of an explicit likelihood measure [51], which is commonplace in comparable probabilistic models [27,47]. Thus, much of the previous work has resorted to a mere subjective visual evaluation in the case of images synthesized by GANs. As seen from the sample images generated by a state-of-the-art GAN [36] in Figure 1, it is impossible to judge their quality precisely with a subjective evaluation. Recent work in the past two years has begun to target this challenge through quantitative measures for evaluating GANs [22,25,32,46].
Inception score (IS) [46] and Fréchet Inception distance (FID) [22] were suggested as ad-hoc measures correlated with the visual quality of generated images. Inception score measures the quality of a generated image by computing the KLdivergence between the (logit) response produced by this image and the marginal distribution, i.e., the average response of all the generated images, using an Inception network [50] trained on ImageNet. In other words, Inception score does not compare samples with a target distribution, and is limited to quantifying the diversity of generated samples. Fréchet Inception distance compares Inception activations (responses of the penultimate layer of the Inception network) between real and generated images. This comparison however approximates the activations of real and generated images as Gaussian distributions (cf. equation (2)), computing their means and covariances, which are too crude to capture subtle details. Both these measures rely on an ImageNet-pretrained Inception network, which is far from ideal for other datasets, such as faces and biomedical imaging. Overall, IS and FID are useful measures to evaluate how training advances, but they guarantee no correlation with performance on real-world tasks. As we discuss in Section 5, these measures are insufficient to finely separate state-of-the-art GAN models, unlike our measures (see SNGAN vs WPGAN-GP (10M) in Table 2 for example).
An alternative evaluation is to compute the distance of the generated samples to the real data manifold in terms of precision and recall [32]. Here, high precision implies that the generated samples are close to the data manifold, and high recall shows that the generator outputs samples that cover the manifold well. These measures remain idealistic as they are impossible to compute on natural image data, whose manifold is unknown. Indeed, the evaluation in [32] is limited to using synthetic data composed of gray-scale triangles. Another distance suggested for comparing GAN models is sliced Wasserstein distance (SWD) [25]. SWD is an approximation of Wasserstein-1 distance between real and generated images, and is computed as the statistical similarity between local image patches extracted from Laplacian pyramid representations of these images. As shown in Section 5, SWD is less-informative than our evaluation measures.
In this paper, we propose new evaluation measures to compare class-conditional GAN architectures with GAN-train and GAN-test scores. We rely on a neural net architecture for image classification for both these measures. To compute GAN-train, we train a classification network with images generated by a GAN, and then evaluate its performance on a test set composed of real-world images. Intuitively, this measures the difference between the learned (i.e., generated image) and the target (i.e., real image) distributions. We can conclude that generated images are similar to real ones if the classification network, which learns features for discriminating images generated for different classes, can correctly classify real images. In other words, GAN-train is akin to a recall measure, as a good GAN-train performance shows that the generated samples are diverse enough. However, GAN-train also requires a sufficient precision, as otherwise the classifier will be impacted by the sample quality.
Our second measure, GAN-test, is the accuracy of a network trained on real images and evaluated on the generated images. This measure is similar to precision, with a high value denoting that the generated samples are a realistic approximation of the (unknown) distribution of natural images. In addition to these two measures, we study the utility of images generated by GANs for augmenting training data. This can be interpreted as a measure of the diversity of the generated images. The utility of our evaluation approach, in particular, when a subjective inspection is insufficient, is illustrated with the GAN-train measure in Figure 1. We will discuss these measures in detail in Section 3.
As shown in our extensive experimental results in Section 5 and the appendix in the supplementary material and technical report [5], these measures are much more informative to evaluate GANs, compared to all the previous measures discussed, including cases where human studies are inconclusive. In particular, we evaluate two state-of-the-art GAN models: WGAN-GP [20] and SNGAN [36], along with other generative models [45,47] to provide baseline comparisons. Image classification performance is evaluated on MNIST [30], CI-FAR10, CIFAR100 [28], and the ImageNet [14] datasets. Experimental results show that the quality of GAN images decreases significantly as the complexity of the dataset increases.

Related work
We present existing quantitative measures to evaluate GANs: scores based on an Inception network, i.e., IS and FID, a Wasserstein-based distance metric, precision and recall scores, and a technique built with data augmentation.

Inception score
One of the most common ways to evaluate GANs is the Inception score [46]. It uses an Inception network [50] pre-trained on ImageNet to compute logits of generated images. The score is given by: where x is a generated image sampled from the learned generator distribution p g , E is the expectation over the set of generated images, D KL is the KL-divergence between the conditional class distribution p(y|x) (for label y, according to the Inception network) and the marginal class distribution p(y) = E x pg [p(y|x)]. By definition, Inception score does not consider real images at all, and so cannot measure how well the generator approximates the real distribution. This score is limited to measuring only the diversity of generated images. Some of its other limitations, as noted in [8], are: high sensitivity to small changes in weights of the Inception network, and large variance of scores.

Fréchet Inception distance
The recently proposed Fréchet Inception distance (FID) [22] compares the distributions of Inception embeddings (activations from the penultimate layer of the Inception network) of real (p r (x)) and generated (p g (x)) images. Both these distributions as modeled as multi-dimensional Gaussians parameterized by their respective mean and covariance. The distance measure is defined between the two Gaussian distributions as: where (m r , C r ), (m g , C g ) denote the mean and covariance of the real and generated image distributions respectively. FID is inversely correlated with Inception score, and suffers from the same issues discussed earlier.
The two Inception-based measures cannot separate image quality from image diversity. For example, low IS or FID values can be due to the generated images being either not realistic (low image quality) or too similar to each other (low diversity), with no way to analyze the cause. In contrast, our measures can distinguish when generated images become less diverse from worse image quality.

Other evaluation measures
Sliced Wasserstein distance (SWD) [25] was used to evaluate high-resolution GANs. It is a multi-scale statistical similarity computed on local image patches extracted from the Laplacian pyramid representation of real and generated images. A total of 128 7×7 local patches for each level of the Laplacian pyramid are extracted per image. While SWD is an efficient approximation, using randomized projections [44], of the Wasserstein-1 distance between the real and generated images, its utility is limited when comparing a variety of GAN models, with not all of them producing high-resolution images (see our evaluation in Section 5).
Precision and recall measures were introduced [32] in the context of GANs, by constructing a synthetic data manifold. This makes it possible to compute the distance of an image sample (generated or real) to the manifold, by finding its distance to the closest point from the manifold. In this synthetic setup, precision is defined as the fraction of the generated samples whose distance to the manifold is below a certain threshold. Recall, on the other hand, is computed by considering a set of test samples. First, the latent representationz of each test sample x is estimated, through gradient descent, by inverting the generator G. Recall is then given by the fraction of test samples whose L2-distance to G(z) is below the threshold. High recall is equivalent to the GAN capturing most of the manifold, and high precision implies that the generated samples are close to the manifold. Although these measures bring the flavor of techniques used widely to evaluate discriminative models to GANs, they are impractical for real images as the data manifold is unknown, and their use is limited to evaluations on synthetic data [32].

Data augmentation
Augmenting training data is an important component of learning neural networks. This can be achieved by increasing the size of the training set [29] or incorporating augmentation directly in the latent space [54]. A popular technique is to increase the size of the training set with minor transformations of data, which has resulted in a performance boost, e.g., for image classification [29]. GANs provide a natural way to augment training data with the generated samples. Indeed, GANs have been used to train classification networks in a semi-supervised fashion [13,52] or to facilitate domain adaptation [10]. Modern GANs generate images realistic enough to improve performance in applications, such as, biomedical imaging [11,18], person re-identification [58] and image enhancement [55]. They can also be used to refine training sets composed of synthetic images for applications such as eye gaze and hand pose estimation [49]. GANs are also used to learn complex 3D distributions and replace computationally intensive simulations in physics [39,42] and neuroscience [38]. Ideally, GANs should be able to recreate the training set with different variations. This can be used to compress datasets for learning incrementally, without suffering from catastrophic forgetting as new classes are added [48]. We will study the utility of GANs for training image classification networks with data augmentation (see Section 5.4), and analyze it as an evaluation measure.
In summary, evaluation of generative models is not a easy task [51], especially for models like GANs. We bring a new dimension to this problem with our GAN-train and GAN-test performance-based measures, and show through our extensive analysis that they are complementary to all the above schemes.

GAN-train and GAN-test
An important characteristic of a conditional GAN model is that generated images should not only be realistic, but also recognizable as coming from a given class. An optimal GAN that perfectly captures the target distribution can generate a new set of images S g , which are indistinguishable from the original training set S t . Assuming both these sets have the same size, a classifier trained on either of them should produce roughly the same validation accuracy. This is indeed true when the dataset is simple enough, for example, MNIST [48] (see also Section 5.2). Motivated by this optimal GAN characteristic, we devise two scores to evaluate GANs, as illustrated in Figure 2.
GAN-train is the accuracy of a classifier trained on S g and tested on a validation set of real images S v . When a GAN is not perfect, GAN-train accuracy will be lower than the typical validation accuracy of the classifier trained on S t . It can happen due to many reasons, e.g., (i) mode dropping reduces the diversity of S g in comparison to S t , (ii) generated samples are not realistic enough to make the classifier learn relevant features, (iii) GANs can mix-up classes and confuse the classifier. Unfortunately, GAN failures are difficult to diagnose. When GANtrain accuracy is close to validation accuracy, it means that GAN images are high quality and as diverse as the training set. As we will show in Section 5.3, diversity varies with the number of generated images. We will analyze this with the evaluation discussed at the end of this section.
GAN-test is the accuracy of a classifier trained on the original training set S t , but tested on S g . If a GAN learns well, this turns out be an easy task because both the sets have the same distribution. Ideally, GAN-test should be close to the validation accuracy. If it significantly higher, it means that the GAN overfits, and simply memorizes the training set. On the contrary, if it is significantly lower, the GAN does not capture the target distribution well and the image quality is poor. Note that this measure does not capture the diversity of samples because a model that memorizes exactly one training image perfectly will score very well. GAN-test accuracy is related to the precision score in [32], quantifying how close generated images are to a data manifold.
To provide an insight into the diversity of GAN-generated images, we measure GAN-train accuracy with generated sets of different sizes, and compare it with the validation accuracy of a classifier trained on real data of the corresponding size. If all the generated images were perfect, the size of S g where GAN-train is equal to validation accuracy with the reduced-size training set, would be a good estimation of the number of distinct images in S g . In practice, we observe that GAN-train accuracy saturates with a certain number of GAN-generated samples (see Figures 4(a) and 4(b) discussed in Section 5.3). This is a measure of the diversity of a GAN, similar to recall from [32], measuring the fraction of the data manifold covered by a GAN.

Datasets and Methods
Datasets. For comparing the different GAN methods and PixelCNN++, we use several image classification datasets with an increasing number of labels: MNIST [30], CIFAR10 [28], CIFAR100 [28] and ImageNet1k [14]. CIFAR10 and CIFAR100 both have 50k 32×32 RGB images in the training set, and 10k images in the validation set. CIFAR10 has 10 classes while CIFAR100 has 100 classes. ImageNet1k has 1000 classes with 1.3M training and 50k validation images. We downsample the original ImageNet images to two resolutions in our experiments, namely 64 × 64 and 128 × 128. MNIST has 10 classes of 28 × 28 grayscale images, with 60k samples for training and 10k for validation.
We exclude the CIFAR10/CIFAR100/ImageNet1k validation images from GAN training to enable the evaluation of test accuracy. This is not done in a number of GAN papers and may explain minor differences in IS and FID scores compared to the ones reported in these papers.

Evaluated methods
Among the plethora of GAN models in literature, it is difficult to choose the best one, especially since appropriate hyperparameter fine-tuning appears to bring all major GANs within a very close performance range, as noted in a study [32]. We choose to perform our analysis on Wasserstein GAN (WGAN-GP), one of the most widely-accepted models in literature at the moment, and SNGAN, a very recent model showing state-of-the-art image generation results on Ima-geNet. Additionally, we include two baseline generative models, DCGAN [45] and PixelCNN++ [47]. We summarize all the models included in our experimental analysis below, and present implementation details in the appendix [5]. Wasserstein GAN. WGAN [7] replaces the discriminator separating real and generated images with a critic estimating Wasserstein-1 (i.e., earth-mover's) dis-tance between their corresponding distributions. The success of WGANs in comparison to the classical GAN model [19] can be attributed to two reasons. Firstly, the optimization of the generator is easier because the gradient of the critic function is better behaved than its GAN equivalent. Secondly, empirical observations show that the WGAN value function better correlates with the quality of the samples than GANs [7].
In order to estimate the Wasserstein-1 distance between the real and generated image distributions, the critic must be a K-Lipschitz function. The original paper [7] proposed to constrain the critic through weight clipping to satisfy this Lipschitz requirement. This, however, can lead to unstable training or generate poor samples [20]. An alternative to clipping weights is the use of a gradient penalty as a regularizer to enforce the Lipschitz constraint. In particular, we penalize the norm of the gradient of the critic function with respect to its input. This has demonstrated stable training of several GAN architectures [20].
We use the gradient penalty variant of WGAN, conditioned on data in our experiments, and refer to it as WGAN-GP in the rest of the paper. Label conditioning is an effective way to use labels available in image classification training data [41]. Following ACGAN [41], we concatenate the noise input z with the class label in the generator, and modify the discriminator to produce probability distributions over the sources as well as the labels. SNGAN. Variants have also analyzed other issues related to training GANs, such as the impact of the performance control of the discriminator on training the generator. Generators often fail to learn the multimodal structure of the target distribution due to unstable training of the discriminator, particularly in highdimensional spaces [36]. More dramatically, generators cease to learn when the supports of the real and the generated image distributions are disjoint [6]. This occurs since the discriminator quickly learns to distinguish these distributions, resulting in the gradients of the discriminator function, with respect to the input, becoming zeros, and thus failing to update the generator model any further.
SNGAN [36] introduces spectral normalization to stabilize training the discriminator. This is achieved by normalizing each layer of the discriminator (i.e., the learnt weights) with the spectral norm of the weight matrix, which is its largest singular value. Miyato et al. [36] showed that this regularization outperforms other alternatives, including gradient penalty, and in particular, achieves state-of-the-art image synthesis results on ImageNet. We use the classconditioned version of SNGAN [37] in our evaluation. Here, SNGAN is conditioned with projection in the discriminator network, and conditional batch normalization [17] in the generator network. DCGAN. Deep convolutional GANs (DCGANs) is a class of architecture that was proposed to leverage the benefits of supervised learning with CNNs as well as the unsupervised learning of GAN models [45]. The main principles behind DC-GANs are using only convolutional layers and batch normalization for the generator and discriminator networks. Several instantiations of DCGAN are possible with these broad guidelines, and in fact, many do exist in literature [20,36,41]. We use the class-conditioned variant presented in [41] for our analysis.
PixelCNN++. The original PixelCNN [53] belongs to a class of generative models with tractable likelihood. It is a deep neural net which predicts pixels sequentially along both the spatial dimensions. The spatial dependencies among pixels are captured with a fully convolutional network using masked convolutions. PixelCNN++ proposes improvements to this model in terms of regularization, modified network connections and more efficient training [47].

Implementation details of evaluation measures
We compute Inception score with the WGAN-GP code [1] corrected for the 1008 classes problem [8]. The mean value of this score computed 10 times on 5k splits is reported in all our evaluations, following standard protocol.
We found that there are two variants for computing FID. The first one is the original implementation [2] from the authors [22], where all the real images and at least 10k generated images are used. The second one is from the SNGAN [36] implementation, where 5k generated images are compared to 5k real images. Estimation of the covariance matrix is also different in both these cases. Hence, we include these two versions of FID in the paper to facilitate comparison in the future. The original implementation is referred to as FID, while our implementation [4] of the 5k version is denoted as FID-5K. Implementation of SWD is taken from the official NVIDIA repository [3].

Generative model evaluation
MNIST. We validate our claim (from Section 3) that a GAN can perfectly reproduce a simple dataset on MNIST. A four-layer convnet classifier trained on real MNIST data achieves 99.3% accuracy on the test set. In contrast, images generated with SNGAN achieve a GAN-train accuracy of 99.0% and GAN-test accuracy of 99.2%, highlighting their high image quality as well as diversity. CIFAR10. Table 1 shows a comparison of state-of-the-art GAN models on CIFAR10. We observe that the relative ranking of models is consistent across different metrics: FID, GAN-train and GAN-test accuracies. Both GAN-train and GAN-test are quite high for SNGAN and WGAN-GP (10M). This implies that both the image quality and the diversity are good, but are still lower than that of real images (92.8 in the first row). Note that PixelCNN++ has low diversity because GAN-test is much higher than GAN-train in this case. This is in line with its relatively poor Inception score and FID (as shown in [32] FID is quite sensitive to mode dropping).
Note that SWD does not correlate well with other metrics: it is consistently smaller for WGAN-GP (especially SWD 32). We hypothesize that this is because SWD approximates the Wasserstein-1 distance between patches of real and generated images, which is related to the optimization objective of Wasserstein GANs, but not other models (e.g., SNGAN). This suggests that SWD is  unsuitable to compare WGAN and other GAN losses. It is also worth noting that WGAN-GP (10M) shows only a small improvement over WGAN-GP (2.5M) despite a four-fold increase in the number of parameters. In Figure 3 we show SNGAN-generated images on CIFAR10 and their nearest neighbors from the training set in the feature space of the classifier we use to compute the GANtest measure. Note that SNGAN consistently finds images of the same class as a generated image, which are close to an image from the training set.
To highlight the complementarity of GAN-train and GAN-test, we emulate a simple model by subsampling/corrupting the CIFAR10 training set, in the spirit of [22]. GAN-train/test now corresponds to training/testing the classifier on modified data. We observe that GAN-test is insensitive to subsampling unlike GAN-train (where it is equivalent to training a classifier on a smaller split). Salt and pepper noise, ranging from 1% to 20% of replaced pixels per image, barely affects GAN-train, but degrades GAN-test significantly (from 82% to 15%).
Through this experiment on modified data, we also observe that FID is insufficient to distinguish between the impact of image diversity and quality. For example, FID between CIFAR10 train set and train set with Gaussian noise (σ = 5) is 27.1, while FID between train set and its random 5k subset with the same noise is 29.6. This difference may be due to lack of diversity or quality or both. GAN-test, which measures the quality of images, is identical (95%) in both these cases. GAN-train, on the other hand, drops from 91% to 80%, showing that the 5k train set lacks diversity. Together, our measures, address one of the main drawbacks of FID. CIFAR100. Our results on CIFAR100 are summarized in Table 2. It is a more challenging dataset than CIFAR10, mainly due to the larger number of classes and fewer images per class; as evident from the accuracy of a convnet for clas-sification trained with real images: 92.8 vs 69.4 for CIFAR10 and CIFAR100 respectively. SNGAN and WGAN-GP (10M) produce similar IS and FID, but very different GAN-train and GAN-test accuracies. This makes it easier to conclude that SNGAN has better image quality and diversity than WGAN-GP (10M). It is also interesting to note that WGAN-GP (10M) is superior to WGAN-GP (2.5M) in all the metrics, except SWD. WGAN-GP (2.5M) achieves reasonable IS and FID, but the quality of the generated samples is very low, as evidenced by GAN-test accuracy. SWD follows the same pattern as in the CIFAR10 case: WGAN-GP shows a better performance than others in this measure, which is not consistent with its relatively poor image quality. PixelCNN++ exhibits an interesting behavior, with high GAN-test accuracy, but very low GAN-train accuracy, showing that it can generate images of acceptable quality, but they lack diversity. A high FID in this case also hints at significant mode dropping. We also analyze the quality of the generated images with t-SNE [33] in the appendix [5]. Random forests. We verify if our findings depend on the type of classifier by using random forests [23,43] instead of CNN for classification. This results in GANtrain, GAN-test scores of 15.2%, 19.5% for SNGAN, 10.9%, 16.6% for WGAN-GP (10M), 3.7%, 4.8% for WGAN-GP (2.5M), and 3.2%, 3.0% for DCGAN respectively. Note that the relative ranking of these GANs remains identical for random forests and CNNs. Human study. We designed a human study with the goal of finding which of the measures (if any) is better aligned with human judgement. The subjects were asked to choose the more realistic image from two samples generated for a particular class of CIFAR100. Five subjects evaluated SNGAN vs one of the following: DCGAN, WGAN-GP (2.5M), WGAN-GP (10M) in three separate tests. They made 100 comparisons of randomly generated image pairs for each test, i.e., 1500 trials in total. All of them found the task challenging, in particular for both WGAN-GP tests.
We use Student's t-test for statistical analysis of these results. In SNGAN vs DCGAN, subjects chose SNGAN 368 out of 500 trials, in SNGAN vs WGAN-GP (2.5M), subjects preferred SNGAN 274 out of 500 trials, and in SNGAN vs WGAN-GP (10M), SNGAN was preferred 230 out of 500. The preference of SNGAN over DCGAN is statistically significant (p < 10 −7 ), while the preference over WGAN-GP (2.5M) or WGAN-GP (10M) is insignificant (p = 0.28 and p = 0.37 correspondingly). We conclude that the quality of images generated needs to be significantly different, as in the case of SNGAN vs DCGAN, for human studies to be conclusive. They are insufficient to pick out the subtle, but performance-critical, differences, unlike our measures. ImageNet. On this dataset, which is one of the more challenging ones for image synthesis [36], we analyzed the performance of the two best GAN models based on our CIFAR experiments, i.e., SNGAN and WGAN-GP. As shown in Table 3, SNGAN achieves a reasonable GAN-train accuracy and a relatively high GANtest accuracy at 128 × 128 resolution. This suggests that SNGAN generated images have good quality, but their diversity is much lower than the original data. This may be partly due to the size of the generator (150Mb) being significantly   In the case of images generated at 64 × 64 resolution, GAN-train and GANtest accuracies with SNGAN are lower than their 128 × 128 counterparts. GANtest accuracy is over four times better than GAN-train, showing that the generated images lack in diversity. It is interesting to note that WGAN-GP produces Inception score and FID very similar to SNGAN, but its images are insufficient to train a reasonable classifier and to be recognized by an ImageNet classifier, as shown by the very low GAN-train and GAN-test scores.

GAN image diversity
We further analyze the diversity of the generated images by evaluating GANtrain accuracy with varying amounts of generated data. A model with low diversity generates redundant samples, and increasing the quantity of data generated in this case does not result in better GAN-train accuracy. In contrast, generating more samples from a model with high diversity produces a better GAN-train score. We show this analysis in Figure 4, where GAN-train accuracy is plotted with respect to the size of the generated training set on CIFAR10 and CIFAR100.
In the case of CIFAR10, we observe that GAN-train accuracy saturates around 15-20k generated images, even for the best model SNGAN (see  ure 4a). With DCGAN, which is weaker than SNGAN, GAN-train saturates around 5k images, due to its relatively poorer diversity. Figure 4b shows no increase in GAN-train accuracy on CIFAR100 beyond 25k images for all the models. The diversity of 5k SNGAN-generated images is comparable to the same quantity of real images; see blue and orange plots in Figure 4b. WGAN-GP (10M) has very low diversity beyond 5k generated images. WGAN-GP (2.5M) and DCGAN perform poorly on CIFAR100, and are not competitive with respect to the other methods.

GAN data augmentation
We analyze the utility of GANs for data augmentation, i.e., for generating additional training samples, with the best-performing GAN model (SNGAN) under two settings. First, in Figures 5a and 5b, we show the influence of training the classifier with a combination of real images from the training set and 50k  Table 4: Data augmentation when SNGAN is trained with reduced real image set. Classifier is trained either on this data (real) or a combination of real and SNGAN generated images (real+GAN). Performance is shown as % accuracy.
GAN-generated images on the CIFAR10 and CIFAR100 datasets respectively. In this case, SNGAN is trained with all the images from the original training set. From both the figures, we observe that adding 2.5k or 5k real images to the 50k GAN-generated images improves the accuracy over the corresponding real-only counterparts. However, adding 50k real images does not provide any noticeable improvement, and in fact, reduces the performance slightly in the case of CIFAR100 (Figure 5b). This is potentially due to the lack of image diversity. This experiment provides another perspective on the diversity of the generated set, given that the generated images are produced by a GAN learned from the entire CIFAR10 (or CIFAR100) training dataset. For example, augmenting 2.5k real images with 50k generated ones results in a better test accuracy than the model trained only on 5k real images. Thus, we can conclude that the GAN model generates images that have more diversity than the 2.5k real ones. This is however, assuming that the generated images are as realistic as the original data. In practice, the generated images tend to be lacking on the realistic front, and are more diverse than the real ones. These observations are in agreement with those from Section 5.3, i.e., SNGAN generates images that are at least as diverse as 5k randomly sampled real images.
In the second setting, SNGAN is trained in a low-data regime. In contrast to the previous experiment, we train SNGAN on a reduced training set, and then train the classifier on a combination of this reduced set, and the same number of generated images. Results in Table 4 show that on both CIFAR10 and CIFAR100 (C10 and C100 respectively in the table), the behaviour is consistent with the whole dataset setting (50k images), i.e., accuracy drops slightly.

Summary
This paper presents steps towards addressing the challenging problem of evaluating and comparing images generated by GANs. To this end, we present new quantitative measures, GAN-train and GAN-test, which are motivated by precision and recall scores popularly used in the evaluation of discriminative models. We evaluate several recent GAN approaches as well as other popular generative models with these measures. Our extensive experimental analysis demonstrates that GAN-train and GAN-test not only highlight the difference in performance of these methods, but are also complementary to existing scores.
To train SNGAN on MNIST we use the same GAN architecture as in the case of CIFAR10 (adjusted to a single input channel), and a simple convnet architecture (four convolutional layers with 32, 64, 128, 256 filters with batch normalization and max pooling in between, and global average pooling before the final output layer) as the baseline classifier. The GAN training schedule is also the same as in the case of CIFAR10. We train the baseline classifier for 64k iterations using a momentum optimizer with learning rate 0.1 dropped to 0.01, after 32k iterations, and 0.001, after 48k iterations (using a batch size of 128).


extfieldsofstudy:
Mathematics
Computer Science

s2fieldsofstudy:
Computer Science
Mathematics

text:
Observability and controllability analysis of linear systems subject to data losses

We provide algorithmically verifiable necessary and sufficient conditions for fundamental system theoretic properties of discrete time linear systems subject to data losses. More precisely, the systems in our modeling framework are subject to disruptions (data losses) in the feedback loop, where the set of possible data loss sequences is captured by an automaton. As such, the results are applicable in the context of shared (wireless) communication networks and/or embedded architectures where some information on the data loss behaviour is available a priori. We propose an algorithm for deciding observability (or the absence of it) for such systems, and show how this algorithm can be used also to decide other properties including constructibility, controllability, reachability, null-controllability, detectability and stabilizability by means of relations that we establish among these properties. The main apparatus for our analysis is the celebrated Skolem Theorem from linear algebra. Moreover, we study the relation between the model adopted in this paper and a previously introduced model where, instead of allowing dropouts in the feedback loop, one allows for time varying delays.

I. Introduction
The last decades have witnessed the introduction of many sensing, computing and wireless communication devices in a broad range of control applications leading to networked control and cyber-physical systems. In such systems it is observed that the phenomenon of data losses is rather common as a realtime feedback loop can be disrupted intermittently by packet losses in wireless communication, task deadlines can be missed in shared embedded processors, outliers can be discarded in sensor-harvested data, and so on. This has caused a vivid interest in the analysis and design of control systems, see, e.g., [3], [8], [10], [20], [22], [23], [25], [28] and the references therein.
As data losses lead to imperfect control updates, it can be expected that fundamental system theoretic properties such as observability, controllability, detectability, stabilizability, etc. are affected. These fundamental notions have played central roles throughout the history of modern control theory and have been studied extensively in the context of finite-dimensional linear systems, nonlinear systems, infinitedimensional systems, n-dimensional systems, hybrid systems, and behavioral systems. One may refer, for instance, to [26] for historical comments and references. Given the importance of these notions on the one hand and the relevance of cyber-physical and networked control systems on the other hand, we believe that observability (and related notions) under packet loss will be critical in forthcoming engineering applications.
Figures 1 and 2 illustrate two situations of intermittent data losses that are of interest and will be studied in the present paper. It is rather remarkable that these questions have not been answered despite the large literature on systems with packet loss. The above-mentioned references have introduced (analysis and design) methods that can guarantee stability of the closed-loop systems (up to some conservativeness), but to our knowledge the fundamental properties in dropout systems have not been studied from a theoretical and algorithmic point of view, as they have been for linear (and, later, for nonlinear) systems.
Motivated by these considerations, we will address in this paper the problem of studying observability, controllability, detectability, stabilizability and other fundamental properties for discrete-time linear timeinvariant (LTI) systems with packet losses represented in Figures 1 and 2. We will also study the relationships between these notions. We employ a constrained switched systems perspective for modelling the system under consideration. A constrained switched system is a switched system in which the September  admissible switches are constrained, e.g., it is allowed to switch from mode a to mode b, but it is not allowed to switch from mode b to mode a, etc. More precisely, the admissible switches are described by an automaton (see Definition 1 below for the details). These constrained switched linear systems have received considerable attention in recent years [7], [18], [21], [30], and many tools or results that were initially designed for general switched systems are now available for constrained switched systems.
In our setting the switching constraints arise from the consideration that the data loss signal has some known properties that prevent arbitrary switches. More precisely, the language generated by the automaton represents the admissible data loss signals. This setup encapsulates many natural constraints, including the case where there is an upper bound on the maximal number of consecutive dropouts and many others.
Although for certain classes of switched systems and hybrid systems, questions of controllability, observability and others have been addressed, see, e.g., [1], [2], [5], [6], [17], [27], [31], there are no general answers to these problems, certainly not in the context of constrained switched linear systems as considered here. Indeed, the complexity of characterizing controllability has been studied by [4] for some classes of hybrid systems, and these authors showed that even within quite limited classes of switched systems, there is no algorithm to decide the controllability properties of a given system. However, by exploiting the specific structure of the systems described above, and combining this with deep results September 20, 2016 DRAFT from linear algebra and arguments from automata theory, we will be able to answer the questions at hand.
We build hereby on our preliminary conference paper [13] where we tackle the single observability problem (under additional restrictions). The analogous problem of controllability was studied by us in [12]. In the present journal version, we extend these results to various other system theoretic properties, and provide a complete picture of the problem. In particular, we study observability, constructibility, detectability, controllability, reachability, null-controllability and stabilizability of discrete-time linear systems subject to data losses (and their practical variants). We show that all these properties can indeed be verified algorithmically and also reveal various duality relationships between the mentioned notions (and, interestingly, the absence of duality in some situations, contrary to the LTI case). In addition, we connect to the recent work in [14] in which the authors studied controllability algorithms for another class of systems, containing switching delays in the feedback loop. We will study extensively the link between that model and ours in Section VI below.
The remainder of this article is organized as follows. In Section II, we present our model in details.
Then, in Section III, we analyze the observability problem (and the similar constructibility problem) and in Section IV, we analyze the controllability counterpart: the reachability and 0-controllability problems.
In Section V, we further generalize the technique to the stabilizability and detectability problems. Our last theoretical contribution comes in Section VI, where we take a step back and analyze the connections between our problem and the recently studied controllability with switching delays. In Section VII, we give a numerical example, and then finish with a brief conclusion.

II. Problem formulation
In this paper we are primarily interested in studying the following systems and properties: • Observability of discrete-time linear systems subject to data losses of the form where x(t) ∈ R n , and y(t) ∈ R p are respectively the vectors of states and outputs at time t ∈ N, and σ : N → {0, 1} is the data loss signal in the sense that σ(t) = 1 corresponds to the case where the September 20, 2016 DRAFT 5 output is available at time t ∈ N, and σ(t) = 0 corresponds to the case where the output is lost at time t ∈ N.
• Controllability of discrete-time linear systems subject to data losses of the form where x(t) ∈ R n , and u(t) ∈ R m are respectively the vectors of states and inputs at time t ∈ N, and σ : N → {0, 1} is the data loss signal in the sense that σ(t) = 1 corresponds to the case where the input is effectively conveyed to the plant at time t ∈ N, and σ(t) = 0 corresponds to the case where the input is lost at time t ∈ N.
For any pair of matrices (A, C) (resp. (A, B)), the observability (resp. controllability) problem is relevant only if some additional assumptions are made on the possible dropout behaviour (it is obvious that if σ(t) = 0 for all t ∈ N, the system is not observable (resp. not controllable)). For this reason, our model comes with certain constraints on the classes of data loss signals σ. For example, a natural assumption is that there can be at most ∈ N consecutive data losses with given. Such constraints on the data loss signal are often encountered in practice, and arise from the characteristics of the shared (wireless) communication network and/or the embedded architecture. Another type of constraints could be that for every m consecutive time steps, we receive data in good order on at least k time steps (so-called (m, k)-firmness), where m, k ∈ N are given parameters [9], [11], [29].
All the above constraints (and many others) on the data loss signal can be captured by an automaton, which is part of the description of the dynamical system. We now formally describe this notion (which slightly deviates from the literature to satisfy our needs). it holds that M v(t),v(t+1) = 1 and σ(t) = s v(t) . The set of all admissible data loss signals for the automaton A is denoted by L(A).
In this paper we consider only automata that can produce at least one admissible data loss signal (and thus by definition defined for all t ∈ N), which implies that the automaton must contain at least one cycle. Example 1: Consider a control system where there can be at most ∈ N consecutive data losses. This can be captured by an automaton containing + 1 nodes, in which the node i ∈ {1, 2, · · · , } represents the situation where the data generated at the last i consecutive instants were lost, and the one before arrived safely. The node + 1 represents the situation where the last packet arrived safely. Let = 3. The Figure 3. Combining the description of the dynamics (1) (or (2)) and the automaton A, our systems can be modeled as so-called discrete-time constrained switched linear systems. These systems, where the switching signal is constrained by an automaton, have been the subject of much attention recently [7], [18], [21], [30], see also the introduction.
In the sequel we refer to the discrete-time switched systems (1) and (2)

constrained by an automaton
A with the tuples (A, C, A) and (A, B, A), respectively. Similarly, the notations x(t, x 0 , σ) and y(t, x 0 , σ) denote the state and output trajectories of the system (1) at time t ∈ N generated under a switching signal σ with initial state x 0 . The notation x(t, x 0 , u, σ) denotes the state and output trajectories of the system (2) at time t ∈ N generated under a switching signal σ and control input signal u : N → R m with initial state x 0 . However, when there is no ambiguity, we stick to x(t) and y(t) for brevity.
Definition 3: (i) The system (A, C, A) is said to be observable if for any σ ∈ L(A), any pair of initial states x 0 andx 0 ∈ R n , it holds that y(t, x 0 , σ) = y(t,x 0 , σ) for all t ∈ N implies that x 0 =x 0 . The system is called unobservable otherwise. September 20, 2016 DRAFT 7 (ii) The system (A, C, A) is said to be constructible if for any σ ∈ L(A), and any initial state x 0 , there exists a T ∈ N such that for anyx 0 ∈ R n that satisfies y(t, x 0 , σ) = y(t,x 0 , σ) for all t ∈ N [0,T ] it holds that x(T, x 0 , σ) = x(T,x 0 , σ). The system is called non-constructible otherwise.
(iii) The system (A, C, A) is said to be detectable if for any σ ∈ L(A) and any initial state x 0 ∈ R n with y(t, x 0 , σ) = 0 for all t ∈ N, it holds that x(t, x 0 , σ) → 0 as t → ∞. The system is called undetectable otherwise.
Definition 4: (i) The system (A, B, A) is said to be controllable if for any σ ∈ L(A), any initial state x 0 ∈ R n and any final state x f ∈ R n , there is an input signal u : N → R m such that x(T, x 0 , u, σ) = x f for some T ∈ N. The system is called uncontrollable otherwise.
(ii) The system (A, B, A) is said to be reachable if for any σ ∈ L(A), and for the initial state 0 ∈ R n and any final state x f ∈ R n , there is an input signal u : N → R m such that x(T, x 0 , u, σ) = x f for some T ∈ N. The system is called unreachable otherwise.
(iii) The system (A, B, A) is said to be 0-controllable if for any σ ∈ L(A) and any initial state x 0 ∈ R n , there is an input signal u : N → R m such that x(T, x 0 , u, σ) = 0 for some T ∈ N. The system is called non-0-controllable otherwise.
(iv) The system (A, B, A) is said to be stabilizable if for any σ ∈ L(A) and any initial state x 0 ∈ R n , there is an input signal u : N → R m such that lim t→∞ x(t, x 0 , u, σ) = 0. The system is called non-stabilizable otherwise.
To motivate the study of these properties, let us consider an example.
Example 2: Consider the system (1) with The observability matrix (1) (in the classical sense, that is, with σ(t) = 1 for all t ∈ N) is given by September 20, 2016 DRAFT Notice that the rank of O(A, C) is 2, and consequently, the pair (A, C) is observable in the classical sense.
Let us now suppose that the system is subject to dropout signals, as described by the automaton A in Figure 3. Under the periodic data loss signal σ = (1, 0, 1, 0, 1, 0, . . .), which is admissible with respect to A, it is easy to see that the system is no longer observable. Now, consider the situation where out of every four consecutive transmissions, at least three are received.
This situation is depicted in Figure 4, where we have an automaton . In this case, it is easy to see that the observability property would be conserved. Interestingly, we can characterize the observability and constructibility notions in simpler forms, which will be beneficial later. This can be accomplished by noting that for any σ ∈ L(A) fixed, it holds that the systems (1) and (2) are linear (though time-varying). Hence, due to linearity, it holds that for any x 0 ∈ R n that satisfies y(t, x 0 , σ) = 0 for all t ∈ N [0,T ] it holds that x(T, x 0 , σ) = 0.

Remark 1:
We now introduce a variant of our notions, which might be of practical importance, where the critical time T in the definitions does not depend on the particular packet loss signal, nor the initial state.
The system (A, C, A) is said to be practically observable if there exists a T ∈ N such that for any σ ∈ L(A), any pair of initial states x 0 andx 0 ∈ R n with y(t, x 0 , σ) = y(t,x 0 , σ) for all t ∈ N [0,T ] , it holds that x 0 =x 0 . Similarly, (A, C, A) is said to be practically constructible if there exists a T ∈ N such that for all σ ∈ L(A), and all initial states x 0 andx 0 ∈ R n with y(t, x 0 , σ) = y(t,x 0 , σ) for all t ∈ N [0,T ] it holds that x(T, x 0 , σ) = x(T,x 0 , σ). Hence, in the 'practical' version of the observability and constructibility notions, the time T can be taken independently of x 0 and σ, which is obviously more practical for reconstructing initial states from the output data and the data loss signal. In fact, we will show below that the observability (resp. constructibility) property formulated in Definition 3-(i) (resp. (ii)) is equivalent to practical observability (resp. practical constructibility) as defined here. Similar observations apply to the controllability, reachability and 0-controllability notions for which practical versions can be defined as follows. The system (A, B, A) is said to be practically controllable if there exists a time T ∈ N such that for any σ ∈ L(A), any initial state x 0 ∈ R n and any final state x f ∈ R n , there is an input signal It is said to be practically reachable if there exists a T ∈ N such that for any σ ∈ L(A), and for the initial state 0 ∈ R n and any final state there is an input signal u : N → R m such that x(t, x 0 , u, σ) = x f for some t ∈ N ≤T . Finally, the system (A, B, A) is said to be practically 0-controllable if there exists T ∈ N such that for any σ ∈ L(A) and any initial state x 0 ∈ R n , there is an input signal u : Note that all the given properties are invariant under similarity transformations. As such, we have, for

III. Observability results
In this section we tackle the following problem: Problem 1: Given a constrained discrete-time switched linear system (1) specified by the triple (A, C, A), determine whether the system is (un)observable and (non-)constructible.
We provide algorithmically verifiable necessary and sufficient conditions to the above problem thereby proving its decidability. In fact, the observability property can be formalized in a completely algebraic way, in terms of an observability matrix, just like in the classical case.
Definition 5: Given a data loss signal σ : N → {0, 1}, we define the observability matrix of the system Proof: (Necessity) We employ contradiction. Suppose that the system (A, C, A) is observable, but there exists a σ ∈ L(A) and a nonzero α ∈ R n such that for all t, O σ (t)α = 0 (note that the null space The observability of the system (A, C, A) follows.
Based on this proposition we sometimes call a σ : N → {0, 1} observable if the corresponding observability matrix has full rank for some t ∈ N. Otherwise, we say that the data loss signal σ is unobservable.
Note that this proposition shows that Note that the difference with respect to practical observability lies in the fact that for practical observability T is independent of σ ∈ L(A).
It is well known that for LTI systems, the difference between observability and constructibility lies in the (un)observability of the modes associated with zero eigenvalues. We now generalize this result to our framework in the next lemma.
Lemma 1: Consider the system (A, C, A) and let S ∈ R n×n be a real Jordan form basis-transformation matrix such that where A r is regular, and A s has only zero eigenvalues.
is (practically) observable/constructible. As such, we can directly work in the real Jordan basis and we as the output of the system described by (A r , C r ), with data loss signal σ ∈ L(A) and initial state x r (0), and y s (t, x r (0), σ) as the output of the system given by (A s , C s ), data loss signal σ ∈ L(A) and initial state x s (0). Observe that due to the diagonal structure of S AS −1 it holds that y(t, (Sufficiency) Suppose first that (A r , C r , A) is observable and thus according to property (i") we have that for all σ ∈ L(A) there is aT (σ) such that for any x r (0) with y r (t, x r (0), σ) = 0 for t ∈ N [0,T ] it holds that x r (0) = 0. To prove constructibility of (A, C, A) take now σ ∈ L(A) and define T =T (σ)+n. Suppose that y(t, x(0), σ) = 0 for all t ∈ N [0,T ] . Since for all t ≥ n, x s (t, x s (0), σ) = 0, and thus y s (t, x s (0), σ) = 0, we have that also y r (t, x r (0), σ) = 0, and by observability of this latter system, it implies that x r (T ) = 0.
Note that if (A r , C r , A) is practically observable, then theT above is independent of σ and thus also the defined T . Hence, we can conclude practical constructibility of (A, C, A).
(Necessity) Suppose (A, C, A) is constructible. Take any σ ∈ L(A) and take T as in the constructibility characterisation (ii') such that for any x 0 ∈ R n that satisfies y(t, x 0 , σ) = 0 for all t ∈ N [0,T ] it holds that Then, we have that y(t, x 0 , σ) = 0 for all t ∈ N [0,T ] as well (as x s (0) = 0) and thus according to the The implication practical constructibility of (A, C, A) ⇒ practical observability (A r , C r , A) follows similarly as in the sufficiency part by observing that T can be taken independent of σ. Proof: For the first part of the corollary, it follows directly from the observability characterisation (i") and the constructibility characterisation (ii') (as x(T, x 0 , σ) = A T x 0 ). The second part of the corollary is obvious from Lemma 1.
We now turn to the main result of this section, which will allow us to decide observability. As announced above, we will make use of the Skolem's Theorem [19], [24] of Linear Algebra, which is given next.
Theorem 1: Consider a matrix A ∈ R n×n and two vectors b, c ∈ R n . The set of values of t ∈ N such that c A t b = 0 is eventually periodic in the sense that there exist two numbers P, T ∈ N such that Moreover, the period P can be computed explicitly. In particular, if the entries in A, b, c are rational numbers, P can be chosen smaller or equal to r n 2 , where r is any prime number not dividing det(mA), and m is the least common multiple of the denominators of the entries in A.
The above theorem shows that if one is interested in the patterns of times such that the response of a linear system x(t + 1) = Ax(t) with x(0) = b is confined to a linear subspace ker c := {w ∈ R n | c w = 0}, then one can restrict the attention eventually to periodic patterns.
We now present our main result. In the course of its proof, we will need the following elementary result, which connects observability and the practical versions (see Remark 1).

Lemma 2:
The system (A, C, A) is practically observable (resp. practically constructible) if and only if it is observable (resp. constructible).
Proof: The 'only if'-part is obvious. For the 'if'-part, let us suppose that the system is observable.
We have to show that there exists a T * ∈ N such that for any σ ∈ L(A) and any initial state we conclude that the observability matrix O σ T * (T * ) does not have full rank. This implies the existence of an infinite signal σ such that O σ (t) has never full rank, which leads to a contradiction. (The existence of σ can be easily proved, e.g., by the convergence of the sequence {σ T * } T * ∈N w.r.t. the standard topology on words, see the proof of Lemma 4 below for more details.) The equivalence between constructibility and practical constructibility follows now from Lemma 1.
Theorem 2: Problem 1 is decidable in the sense that there is an algorithm that decides (un)observability and (non-)constructibility of a given system specified by (A, C, A) in finite time.
Proof: We first present an algorithm to decide (un)observability of (A, C, A), in the particular case where the matrix A is regular. We then show how it can be adapted for the singular case, and finally we show how to decide constructibility.
I. Observability algorithm when A is regular: Our algorithm consists of two routines that run in parallel. The first routine parses every admissible periodic data loss signal corresponding to cycles of length s, s = 1, 2, . . . in the automaton. It then decides whether each of these cyclic signals (based on periodically repeating the cycle) renders the system observable or not (i.e., makes the corresponding observability matrix full rank or not, which can be checked easily as we will see at the end of the proof).
If at some point a periodic signal is found, which violates the full rank condition of the corresponding observability matrix, this establishes unobservability.
In parallel, the second routine in our algorithm generates all admissible switching signals σ of increasing length and checks whether the corresponding observability matrix O σ (t) has full rank. Following Proposition 1, if this property is satisfied for all admissible signals of a given length, then the system (A, C, A) is observable.
The key is to prove that this algorithm is bound to stop after a finite time. In the case that the system is observable, the second subroutine will do so. This follows from Lemma 2 as observability and practical observability are equivalent. In the case the system is unobservable, we establish in claim 1 that there exists a cycle in the automaton, whose corresponding switching signal leads to a rank-deficient observability matrix. Thus, the first routine of our algorithm, which parses larger and larger cycles, will finally find the critical one, and the algorithm will stop.
Claim 1: proof of existence of an unobservable cyclic signal in the unobservable case. If the system (A, C, A) is unobservable, by definition, there is an admissible data loss signal σ for which the rank of the observability matrix O σ (t) is strictly less than n for all t ∈ N. Hence, the null spaces ker O σ (t), the subspace of states indistinguishable from zero). Fix linearly independent vectors v 1 , . . . , v r forming a basis of UO σ . We apply Skolem's Theorem to every pair v i , c j , where c j , j = 1, . . . , p, are the rows of . We obtain T i, j , P i, j ∈ N, where i = 1, 2 . . . , r and j = 1, . . . , p satisfying (4) with the corresponding vector b = v i and c = c j . From this, defining and taking P equal to a common multiple of the P i, j , we have that Consider again the unobservable signal σ and the corresponding path it generates in the automaton.
By the pigeonhole principle, there are two times t 1 , t 2 ∈ N >T , t 2 − t 1 ≤ PN (recall that N is the number of nodes in the automaton) such that t 1 = t 2 mod P, and p σ (t 1 ) = p σ (t 2 ), where p σ (t) denotes the node of the infinite path corresponding to σ in the automaton A at time t ∈ N.
Indeed, there are only PN different possible values for the couple (t mod P, p σ (t)).
Obviously, UO σ ⊂ ker Oσ(t 2 ) as σ andσ coincide for the first t 2 time steps. For t ∈ N [t 2 ,t 2 +P] terms σ(t)CA t are added to the observability matrices. However, we know that σ(t − P)CA t−P v i = 0 for all i and thus σ(t − P) = 0 or CA t−P v i = 0 for all i. In the former case it holds that σ(t) = 0 as well due to (almost) periodicity ofσ. In the latter case we can use (6) to conclude CA t v i = 0 for all i as well.
The same statement holds inductively for t ∈ N ≥t 2 +P . Hence, all added contributions to the observability matrix satisfy also that for all i, σ(t)CA t v i = 0 for t ∈ N ≥t 2 .
This shows that UO σ ⊂ ker Oσ(t) for all t ∈ N and thus thatσ makes the observability matrices rankdeficient. Moreover, also the purely periodic signalσ ∈ L(A) obtained by the periodic repetition of the cycle (σ(t 1 ), . . . , σ(t 2 − 1)) results in rank-deficient observability matrices (since its rows are a subset of the rows of the initial observability matrix, postmultiplied by the invertible matrix A −t 1 ). This proves claim 1.
Finally, in order to complete the algorithm we still have to provide a finite test for checking whether a periodic data loss signal of some period s is (un)observable.
For this purpose we now prove (claim 2) that any infinite cyclic signal σ with period s is unobservable if and only if the observability matrix O σ (t) is rank-deficient for t = sn. This allows to check the unobservability of the complete signal by only looking at a finite part of it.
Obviously, if the signal is unobservable, the finite matrix cannot be full rank.
Conversely, if the matrix O σ (sn) is rank-deficient, its rows span a subspace S of dimension smaller than Summarizing the proof, if the system is unobservable, by checking unobservability of each periodic signal corresponding to cycles of increasing length, the algorithm will come across the unobservable cycle after a finite time (as only cycles up to length PN need to be verified) and the algorithm will terminate.
On the other hand, the algorithm checks every admissible switching signal of increasing length. Thus, if the system is observable, one will come across a finite time t such that all the observability matrices O σ (t) have full rank (due to equivalence of observability and practical observability), and the algorithm will stop.

II. Non-invertible case:
If A is not regular, the proof is rather simple. Indeed, take x(0) 0 such that Ax ( Remark 2: Note that Skolem's theorem not only allows to design an algorithm to decide observability properties of a system (A, C, A), but it also allows to compute a priori the running time of (a slightly modified version) of the algorithm, when one has computed an effective bound on the quantity P in Skolem's theorem. Indeed, one can simply run the second routine of the algorithm in this case as it was shown in the proof above that the system is unobservable if and only if there is an 'unobservable' periodic signal based on a cycle (period) of length less than PN. Hence, one only has to check a finite number of cycles (of length less than PN) to conclude on the observability/constructability or the absence of it. This number is bounded a priori, and one can thus deduce an a priori bound on the computational burden of the algorithm. However, as in some cases the computation of P is not so easy (or P might be very large), the algorithm presented in the proof of the above theorem does not rely on the availability of P by exploiting the two routines.

IV. Controllability results
In this section we address the following problem: Problem 2: Given a constrained discrete-time switched linear system specified by the triple (A, B, A), determine whether the system is (un)controllable, (un)reachable and (non-)0-controllable.
We will see that when the matrix A is regular, the problem can be seen as exactly the 'dual' of the observability problem, and hence solved thanks to the technique described above. However, a bit surprisingly, the duality does not hold when A is singular, and we also describe an algorithm for that case in this section.
Lemma 3: Consider the system (A, C, A), and let S be a real Jordan form basis-transformation matrix such that where A r is regular, and A s has only zero eigenvalues.
Similarly, we also define the reachability matrix C w (t) at time t ∈ N for finite signals (words) w : Note that for all t ∈ N and T ∈ N it holds that which will turn out to be a useful identity.

Proposition 2: The system (A, B, A) is reachable if and only if for all σ ∈ L(A) there exists a T ∈ N
such that the reachability matrix C σ (T ) is of rank n.
Proof: (Necessity) We proceed by contradiction. Suppose that there is a σ such that, for all t ∈ N, the controllability matrix C σ (t) is of rank smaller than n. Let us take x 0 = 0 as in the definition of reachability (Definition 4-(ii)). From (2) we have that where u t−1 ∈ R mt = col(u(t − 1), u(t − 2), . . . , u(0)) := [u(t − 1) u(t − 2) . . . u(0) ] . Hence, the set of reachable vectors at time t ∈ N is a strict linear subspace of R n . Thus, the set of reachable points, which is a countable union of these strict linear subspaces, cannot be equal to R n .
(Sufficiency) Conversely, if for each σ there is a T ∈ N such that C σ (T ) has full rank, then the system is clearly reachable based on (11).

Proposition 3: The system (A, B, A) is controllable if and only if it is reachable. Moreover, reachability
implies 0-controllability and, in case A is invertible, the two notions are equivalent.
Proof: The 'only if' part is trivial. Let us prove the 'if' part of the first statement. Fix σ ∈ L(A), and x 0 , x f ∈ R n . By Proposition 2, since the system is reachable, there is a time t ∈ N such that rank(C σ (t)) = n. Equivalently, September 20, 2016 DRAFT has a solution u t−1 for any x 0 and x f . The input signal u : N → R m starting with (u(0), u(1), . . . , u(t − 1)) transfers the initial state x 0 to the final state x f at time t. Hence, the system (A, B, A) is controllable.
To prove the second statement, note first that since reachability implies controllability it also implies 0-controllability. To show the converse in case A invertible, note that given σ ∈ L(A) the set of all states that can be steered to the origin in finite time is given by t∈N −A −t ImC σ (t). From this identity it follows that if the system is not reachable then there exists a σ such that ImC σ (t) is always a strict subspace of R n . Hence, the indicated union can never be R n and the system is therefore not 0-controllable.
We will now prove various duality relationships to connect the observability and controllability concepts. The following lemma will be useful in proving the duality relationships. Also, consider the set W(A) of finite words generated by A. The following two statements are equivalent: I. There exists a signal σ ∈ L(A) such that for all t ∈ N the corresponding reachability matrix C σ (t) does not have full rank (i.e., the system is not reachable) II. There exists a sequence {w i } i∈N ≥1 of finite words w i ∈ W(A) of length i such that, for all i ∈ N ≥1 the corresponding reachability matrix C w i (i) does not have full rank (i.e., the system is not practically reachable).
The proof of the other direction essentially comes from compactness of the language generated by an automaton (with the standard topology on words), but we present here a self-contained proof for clarity. Therefore, suppose that there is a sequence {w i } i∈N ≥1 of finite words w i ∈ W(A) of length i such that C w i (i) does not have full rank. We now generate based on this sequence an infinite data loss signal σ ∈ L(A) as follows. Starting with k = 0 we iteratively perform the following steps. Define at step k ∈ N σ(k) such that there exists an infinite number of words in {w i } i∈N ≥1 with the first k + 1 letters equal to (σ(0), σ(1), . . . , σ(k)). This procedure can indefinitely be continued as at each step k ∈ N ≥1 (σ(0), σ(1), . . . , σ(k − 1)) are given (by induction) and there are an infinite number of words in {w i } i∈N ≥1 left with these first k letters (for k = 0 this holds trivially). This procedure generates an infinite word σ : N → {0, 1}. Due to (10) we obtain which holds for all w i (i ∈ N ≥k ) that have the same first k letters as the constructed σ. Combining this with C w i (i) not having full rank and the regularity of A, it follows that for all k ∈ N the corresponding observability matrix C σ (k) does not have full rank, which concludes the proof.
We are now in position to establish the duality relationships for which we need the concept of a reverse automaton.
and obviously rev(w) ∈ W(A). However, O rev(w) (T ) has full rank because of the practical observability of system (A, C, A) with bound T , which is a contradiction and thus (A , C , A r ) is controllable.
To prove the second statement assume A regular and (A , C , A r ) is controllable. Suppose now by contradiction that the system (A, C, A) is not observable. Then there exists a σ such that for all t ∈ N O σ (t) does not have full rank. By taking the successive prefixes of σ given w i = (σ(0), . . . , σ(i − 1)), we obtain an infinite sequence of words w i ∈ W(A) of length |w i | = i, i ∈ N, such that the corresponding observability matrix O w i (t) does not have full rank for all t ∈ N ≤i . Using (13) and reversing the automaton, we obtain rev(w i ) ∈ W(A r ) such that C rev(w i ) (i) does not have full rank. By Lemma 4, this implies the existence of a signal σ such that C σ (t) is rank-deficient for all t ∈ N and thus the system is not controllable.

Contradiction! Hence, (A, C, A) is observable.
From now on we call (A , C , A r ) the dual system of (A, C, A). However, the original system (A, B, A) is controllable. Hence, in contrast with the LTI case without data loss, in this case we do not have a complete duality result. Duality between controllability of a system and observability of the dual system only holds when A is regular (or no data loss is allowed).
This example shows that, surprisingly, the duality relation does not hold in the case where A is not regular. Hence, for deciding controllability in this case we must proceed differently than in the regular case. By Lemma 3 one can separate the system into the regular part and the nilpotent part. Let us now focus on a system where A is nilpotent and thus A n = 0. Recall that in the observability case with A nilpotent, the only case where observability can hold is the trivial case where no dropout is possible, see the end of the proof of Theorem 2.
Proposition 6: Suppose that the matrix A is nilpotent. The controllability of the system (A, B, A) can be checked algorithmically.
Proof: Let be the smallest k ∈ N ≤n such that A k = 0. Hence, by Proposition 2 we only have to check the rank of all reachability matrices C σ (t) with t ∈ N ≤ , which is a finite check over all finite words in W(A) with maximal length .
The main result of this section is given next.
Theorem 3: Problem 2 is decidable in the sense that given a system specified by (A, B, A), there is an algorithm that decides (un)controllability, (un)reachability and (non-)0-controllability of the system in finite time.
Proof: If A is regular, one can check reachability by using Proposition 4 above, by checking observability for the dual system. If A is singular, the system (A, B, A) is reachable if and only if both the "regular" part (A r , B r , A) and the "singular" part (A s , B s , A) are reachable (this can be seen most easily by inspecting the structure in the reachability matrices based on the block diagonal structure in the real Jordan form). The first system can be checked with Proposition 4 again, and the second one with Proposition 6. Hence, reachability is decidable and thus controllability as well (recall that controllability is equivalent to reachability (Proposition 3)).
Finally, 0-controllability (or the absence of it) can be checked by Proposition 5 (note that the dual of the dual system is the original system) as constructibility is decidable due to Theorem 2.
Corollary 2: The system (A, B, A) is practically reachable (resp. practically controllable and practically 0-controllable) if and only if it is reachable (resp. controllable and 0-controllable).
Proof: In the spirit of Proposition 2 it is obvious that practical reachability is equivalent to the existence of a finite T ∈ N such that for all σ ∈ L(A) it holds that for some t ∈ N ≤T C σ (t) has full rank. only if it is practically reachable. This shows that reachability and practical reachability are equivalent as reachability of a system is equivalent to reachability of its "regular" part (A r , B r , A) and its "singular" part (A s , B s , A).
Now, by the same arguments as in Proposition 3, practical controllability and practical reachability are equivalent (and we already knew that controllability and reachability are equivalent).
Finally, due to nilpotence of A s and the results in Lemma 3 it follows that (A, B, A) is practically The relationships among various properties presented so far are summarized in Figure 5.

V. Stabilizability and detectability results
The next problem that we consider in this paper is given as follows.
Problem 3: (a) Given a system (A, C, A), determine whether the system is (un)detectable.
(b) Given a system (A, B, A), determine whether the system is (un)stabilizable.
Lemma 5: Consider matrices A, B, C as in the systems (A, C, A) and (A, B, A). Let W be a similarity transformation matrix, so that in block representation where A 11 has all the eigenvalues with modulus larger or equal to one, and A 22 has all the eigenvalues with modulus smaller than one. Then the system (A, C, A) is detectable if and only if (A 11 , C 1 , A) is observable. The system (A, B, A) is stabilizable if and only if ( The lemma is an easy generalization of the LTI case without data losses, just like in Lemmas 1 and 3, and we skip the proof. An immediate consequence (as observability and reachability were proven to be decidable properties) is the following theorem.
Theorem 4: Problem 3(a) (resp. 3(b)) are decidable in the sense that given a system specified by (A, C, A) (resp. (A, B, A)), there is an algorithm that decides (un)detectability (resp. stabilizability) of the system in finite time.
We also have the following duality result.
Proposition 7: The system (A, C, A) is detectable if and only if the dual system (A , C , A r ) is stabilizable, where A r is the reverse automaton of A.
Proof: First, (A, C, A) is detectable if and only if (A 11 , C 1 , A) is observable with the matrices A 11 and C 1 as in Lemma 5 (and transformation matrix W). Obviously, A 11 is a regular matrix and thus observability of (A 11 , C 1 , A) is equivalent to reachability of its dual system (A 11 , C 1 , A r ). As the latter is equivalent to (A , C , A r ) being stabilizable based on Lemma 5 (with transformation matrix W −T ), the proof is complete.

VI. Connections with systems subject to varying delays
In this section we make two links between our problem and a similar one, where the non-idealities in the feedback loop incur time-varying delays, rather than pure packet losses. We mainly show that this other model is a particular case of ours, and provide an algorithm to encapsulate any given controllability problem with time varying delays as a controllability problem with packet losses as introduced in this paper (Subsection VI-B). Then, in Subsection VI-C, we study a particular class of systems from the model studied in this paper, namely, the systems with a bound on the maximal number of consecutive dropouts, and we show how to model these particular systems as systems with varying delays. The interest of this last result is that alternative algorithms, previously developed for systems with time-varying delays, can then be used for this particular family of systems with packet dropouts.

A. Controllability under switching delays
We first briefly recall the framework of [14], [15], where the problem is to control a linear plant, when the feedback loop is subject to time-varying delays. In [14], [15] the constraint on the combinatorial structure of the delays is not given in terms of an automaton, but simply in terms of a set of natural numbers, that represent delays, which can possibly be incurred on the feedback signal.
Definition 8: A system with varying delays is defined by a triple (A, B, D) with A ∈ R n×n , B ∈ R n×m and D = {d 1 , d 2 , . . . , d N } ⊂ N is the set of admissible delays. Its dynamics is described by the equations being any arbitrary delay signal.
The meaning of Equation (14) is that at each time t = 1, 2, . . . , the control packet is subject to a certain delay d(t ), which is determined by an exogenous switching signal d. The control packet u(t ) will impact the state of the system not at time t + 1 as in a classical LTI system, but at time t + d(t ) + 1. If several packets arrive at the actuator at the same time, it was arbitrated in [14], [15] that they are simply added.
The trajectory generated by the system (14) with initial state x(0) = x 0 , input sequence u : N → R m and delay signal d : N → D is denoted by x x 0 ,d,u .
In the spirit of Definition 4 the following definition was introduced in [15].
Definition 9: We say that a system with varying delays described by the triple (A, B, D) is controllable if for any delay signal d : N → D, any initial state x 0 ∈ R n and any final state x f ∈ R n , there is an input signal u : N → R m such that x x 0 ,d,u (T ) = x f for some T ∈ N. In case the system is not controllable it is said to be uncontrollable.
In this setting too, given a delay signal d : N → D one can introduce the controllability matrixC d (t) at time t ∈ N.
Definition 10: Consider a system with time-varying delays (14). Given d : N → N we define the controllability matrix at time t ∈ N asC d (t) ∈ R n×mt , whose i-th block-column (for all i ∈ N [1,t] ) is given by The state of a system with varying delays as in (14) can be expressed thanks to its controllability matrix as where u t−1 ∈ R mt is the column vector with all the inputs u(s), s = 0, . . . , t − 1. Again, controllability can be related to the rank of the matrixC d (t) as formalized next. In order to best represent the link between the varying delays model and our packet dropouts model, we introduce another useful concept: Given a delay signal d : N → N, we define the actuation signal 0, otherwise. (16) With this definition in place, the link between the two models is easy to express: it turns out that for all d : N → N and all t ∈ N, it holds that where C τ d (t) is the Reachability matrix as defined in 6.
Proposition 8 gives us a characterization of controllable systems, but again not an algorithmic one.
Indeed it is not clear how to generate the signal σ as in the proposition, and even less clear how to prove the inexistence of such an infinite-length signal. However, it is shown in [15] that this problem is decidable and even more, that one can bound the time needed by the algorithm to answer the question.

B. The switching delays problem expressed as a dropout problem
In this subsection, we prove that the setting studied in this paper (where an automaton describes the possible packet loss signals) is more general than the model with switching delays. Indeed, we take an arbitrary controllability problem with switching delays, and we convert it to a controllability problem with a dropout signal constrained by an automaton, as studied in this paper. Thus, the controllability test introduced in this paper can be applied to the previously studied problem of controllability with varying delays. However, the next example demonstrates that the proposed results in this paper apply to a much richer class of automata than the ones produced by varying delays.
Example 4: Consider the automaton described by M = We claim that there is no system with varying delays that generates a language of actuation signals equal to L(A). To see this, observe that if the delay signal is constant (i.e., the delay does not change with time), the actuation signal is asymptotically equal to (1, 1, 1, . . . ), which is obviously not in L(A). Due to this structure this automaton cannot be captured as a varying delay system. Proof: We have seen in Proposition 8 that the uncontrollability of system (14) boils down to the existence of a delay signal d : N → D such that the controllability matrixC d (t) has rank smaller than n for all t ∈ N. That is, we want to know whether for all t, ImC d (t), which is equal to is not equal to R n . This latter equation bears similarity with our definition (9) of reachability matrix, and suggests to build a dropout system (A, B, A), such that the possible controllability matrices have block-colums as in (18). More precisely, we will build an automaton A such that L(A) is almost equal to the set of possible actuation signals τ d (they only differ at a few initial letters, but we show below that nevertheless, one system is controllable if and only if the other is).
We now build this automaton. It corresponds to the so-called De Bruijn graph of the sequences on the alphabet D, which can be constructed as follows (we note d max for the largest delay in D). The nodes correspond to the vectors in D d max +1 , and for each node v = (v 0 , . . . , v d max ), and each delay d ∈ D, there is an edge labeled with d pointing from v to the node v = (d, v 0 , . . . ,v d max −1 ). Each node represents the last values of the delay signal at a certain time and from this information one can easily compute if the actuation signal at this node is equal to zero or one. More precisely: It remains to prove that the constructed system (A, B, A) − 1), . . . , d(t)), and for any t ≥ 0, the corresponding packet loss signal is given by σ(t) = τ d (t + d max ) with τ d the actuation signal corresponding to d (see (16)). Thus (see (19)), and from (9), the image of the reachability matrix C σ (t) at an arbitrary time t ∈ N is included in This set is exactly A d max Im(C d (t)) withC d (t) is the controllability matrix determining the controllability of our system with varying delays (see (18)), which is never of rank n by hypothesis. Hence, we have found a packet loss signal σ : N → {0, 1} in L(A) such that the reachability matrix has never full rank and thus the system is not controllable.
Only if: Conversely, if there is a data loss signal σ ∈ L(A) such that the corresponding reachability matrix C σ (t) is never of rank n, the corresponding delay signal d obtained by the successive labels d i 1 , . . . , d i t on the edges of σ leads to a controllability matrix (see (18) again) with All these colums in this expression are colums of the reachability matrix (9) corresponding to the path σ (see our definition of the labeling of the nodes of the automaton as in (19)), and so the matrix cannot be of rank n.
We conclude this subsection by noting that this result gives an algorithm for deciding controllability of systems with varying delays: Simply construct the automaton A described in the above proof, and decide controllability of the system (A, B, A) with the techniques presented in this paper. We note, however, that the alternative technique presented in [16] seems more advantageous, since: 1. It does not require to build an auxiliary automaton, whose size can be exponential in the size of the initial problem and 2. in [16], the total computational time of the algorithm is bounded w.r.t. the size of the initial problem, as a function that does not depend on the numerical values of the entries of A. Thus, the algorithm developed here might not be competitive in terms of computational time with the one previously introduced.
C. The particular case of maximal consecutive dropouts As we have just seen in the previous subsection, the framework of this paper (where nonidealities are represented by an automaton) is more general than systems with switching delays as in (14). However, in this subsection we study the particular case where the automaton represents the constraint that the actuation signal cannot contain more than N consecutive dropouts (like in Example 1). We show that in this particular case, the controllability problem can be restated as a controllability problem with switching delays. That is, the switching delays model encapsulates the constraint of maximal consecutive dropouts.
As a consequence, controllability with a maximum number of dropouts in a row can be solved with the methodology developed there, for which a better bound on the running time of the algorithm is available.
However, we attract the attention of the reader on the fact that the techniques developed in [15] can only be applied for the very particular case where the automaton is of the form in Fig. 3 (i.e., when the constraint on the data loss signal is a bound on the number of consecutive losses). The case with an arbitrary automaton is much more general and powerful (in terms of modeling of a data losses signal). To show that the languages are indeed equal, first take any signal σ : N → {0, 1} satisfying the max-N-consecutive-dropouts constraint, that is The signal σ is the same as τ d corresponding to the delay signal d : N → N given for t ∈ N by Second, take a signal d : N → {0, 1, . . . , N}. It obviously incurs an actuation signal τ d with at most N zeros in a row, which is clearly contained in the set of admissible signals σ for the max-N-consecutivedropout case.

VII. Numerical example
Consider a discrete-time linear system subject to data losses (1) with −5 −10 9 −10 −11 12 The observability matrix in the standard sense (with σ(t) = 1 for all t ∈ N) of the discrete-time linear system is the rank of which is 3. Consequently, the pair (A, C) is observable in the standard sense.
Now consider a data loss signal σ such that maximum two consecutive data losses are allowed. The is shown in Figure 7. The problem under consideration is to decide whether the system (A, C, A) is (un)observable. To this end, our algorithm checks unobservability of periodic signals corresponding to cycles of increasing length. September 20, 2016 DRAFT It is easy to verify (once the signal has been found) that the system (A, C, A) is unobservable under the periodic data loss signal σ = (1, 0, 0, 1, 0, 0, 1, 0, 0, 1, . . .). Now let us modify the constraint on the data loss signal. Consider the case where the control and communication system is constructed so as to protect itself against disruptions, for example, such that at most one packet can be lost in a period of m consecutive steps (or stated otherwise, at least m − 1 successful transmissions take place in every m steps, which is (m, m − 1)-firmness [29]. It turns out that in this case the system is observable (as soon as m ≥ 2). Indeed, for m = 2, the automaton A = (M, s) capturing the above constraint is given below [29].
It is easy to see that the system is observable, because every finite signal of length 6 leads to a full rank s 1 = 0 s 2 = 1 observability matrix. Clearly, if the system is observable with m = 2, it is observable for any m ∈ N >2 .
This leads to the question of how fast our algorithm can decide (un)observability for a given (A, C, A).
Recall that the proposed algorithm checks (un)observability of each periodic signal corresponding to cycles of length s, s = 1, . . . , PN. If all these cycles lead to observable signals, then the system is observable. However, in practice, it may be possible to conclude that a system is observable much earlier than checking all cycles up to length PN . In particular, it may be possible to conclude about (un)observability of a cycle from the properties of other cycles, which reduces the total number of signals for which the (un)observability is checked. For example, in the case presented above, the observability of the signal σ = (1, 0, 1, 0, 1, . . .) leads to observability of the signal σ = (0, 1, 0, 1, 0, 1

VIII. Conclusion
In this paper, our goal was to provide a theoretical analysis of how classical control-theoretic notions are modified by typical non-idealities that are more and more present in modern control, as for instance in wireless control networks. From a formal point of view, the problems we are trying to solve are extremely hard, and even undecidable for arbitrary switched systems. However, our systems, while formally falling in the class of switched systems, are not arbitrary, and their algebraic structure actually allows to retrieve (part of) the powerful properties that are so useful for classical LTI systems. We have shown that packet dropouts (under constraints represented by an automaton), while formally transforming the systems into switched systems, keep enough algebraic structure so that fundamental questions like controllability or observability can still be answered. As we have seen, the non-idealities under study in this paper are quite general, and they even encapsulate previously studied models, like switching delays.
In further work, we plan to study models where observability and controllability interact in the same feedback loop. Also, concerning the controllability problem, our work leaves natural open questions; for instance, how to choose the control signal in real time? Indeed, remark that, in cases where our algorithm returns a positive answer, we know that there exists a control signal that allows to stabilize the plant, but nothing is said about how to chose the optimal signal. It is clear from our results how to chose this signal a posteriori, i.e., once we know the dropout signal that effectively happened. However, in several practical situations, it does not make sense to assume that the disruptions in the feedback loop are known beforehand, and thus the controller has to 'guess' the optimal control value independently of the dropout signal. From this point of view, our results can be viewed as necessary conditions for controllability (or stabilizability, or...), which are not sufficient in the case of real-time control (note that the observability problem does not suffer this limitation, since the essence of observability is that one recovers the state a posteriori).