Intrinsic dimensionality estimation using Normalizing Flows
Authors: Christian Horvat
Jean-Pascal Pfister
Venue: NeurIPS 2022 Accept (2022)
Keywords: Intrinsic Dimensionality
Normalizing Flows

Abstract: How many degrees of freedom are there in a dataset consisting of $M$ samples embedded in $\mathbb{R}^D$? This number, formally known as \textsl{intrinsic dimensionality}, can be estimated using nearest neighbor statistics. However, nearest neighbor statistics do not scale to large datasets as their complexity scales quadratically in $M$, $\mathcal{O}(M^2)$. Additionally, methods based on nearest neighbor statistics perform poorly on datasets embedded in high dimensions where $D\gg 1$. In this paper, we propose a novel method to estimate the intrinsic dimensionality using Normalizing Flows that scale to large datasets and high dimensions. The method is based on some simple back-of-the-envelope calculations predicting how the singular values of the flow's Jacobian change when inflating the dataset with different noise magnitudes. Singular values associated with directions normal to the manifold evolve differently than singular values associated with directions tangent to the manifold. We test our method on various datasets, including 64x64 RGB images, where we achieve state-of-the-art results.

Estimating the intrinsic dimensionality using Normalizing Flows
Christian Horvat
Jean-Pascal Pfister Department of Physiology Bern, Switzerland
Department of Physiology University of Bern christian www.aaaotrttttnbe..ooo
Abstract
How many degrees of freedom are there in dataset consisting of M samples embedded in R This number, formally known as intrinsic dimensionality, can be estimated using nearest neighbor statistics. However, nearest neighbor statistics do not scale large datasets as their complexity scales quadratically in M, (M Additionally, methods based on nearest neighbor statistics perform poorly on datasets embedded in high dimensions where D >> In this paper, we propose novel method to estimate the intrinsic dimensionality using Normalizing Flows that scale to large datasets and high dimensions. The method is based on some simple thcc--o-the-enecllp calculations predicting how the singular values of the flow's ' Jacobian change when inflating the dataset with different noise magnitudes. Singular values associated with directions normal to the manifold evolve differently than singular values associated with directions tangent to the manifold. We test our method various datasets, including 64x64 RGB images, where achieve state-of- the-thhtrtt art results.
Introduction
Learning wiw-dimnsional representations of high- nigh-dimensional data is becoming increasingly im- portant in the era of big data. Therefore, representation learning very active area of research 33 with wide range of applications ranging from neuroscience [27]. molecular biology (28). bioinformatics [12 or image analysis (11. But how many low-dimensional variables are exactly needed to accurately describe the original data? Unfortunetly, this number is typically not known and needs to be estimated task formally known as intrinsic dimensionality (ID) estimation.
Moreover, estimating the ID turned out to be an usefull tool for understanding the functioning of Neural Networks and generative models 23 3T. In recent study, 22 verified that the ID plays a large role in deep learning on natural images and hence motivated the necessity to better estimate the ID in this setting. In the context of generative models, the ID corresponds to the number of latent variables generating the data. Some of these generative models do even rely on knowing the exact number latent variables generating the data which limits their applicability to real- wollworldd problems where this number is unknown [6].
ID estimation is mathematically challenging. Most approaches rely on the assumption that, locally, the samples are uniformly distributed, and therefore the ID can be estimated using nearest neighbor statisties [4). However, such nearest neighbor methods do not scale large datasets consisting of M > samples as the complexity scales with O(DM²) where D is the dimensionality of the embedding space and accounts for calculating the (Euclidean) distance [. Thus, this scaling issue is amplified whenever the embedding space D is of the order of the sample size M, D = O(M).
Therefore, some line of research tries to reduce the complexity of finding the nearest neighbor, e.g. 25
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Additionally, nearest neighbor methods suffer from the curse of dimensionality in the sense that they perform badly in high dimensions D > 5 32.. In this paper, we propose to overeome these scalability issues by estimating the IDD using standard NFs which do scale to large datasets and dimensions.
Our high-level idea is very simple and based on some back-of-theeenvelope calculations which predict how the flow's eigenvalues change depending on the amount of noise injected into the data prior to training. For directions of small variability (i.e. off-manifold directions), the corresponding eigenvalues should decrease at rate predicted by our theory. However, for directions of great variability (i.e. manifold directions), the corresponding eigenvalues will behave differently which allows us to estimate d. We show the soundness of our approach on various datasets, including RGB images of resolution 64 x 64.
2 Problem statement, background and notations
Here we briefly discuss the problem of estimating the ID, introduce the concept of an NF and additional notations which will be used throughout the paper.
An d- dimensional manifold M is of points that are locally diffeomorphic subsets of R see e.g. [22) for a formal definition of manifolds. Given M samples Ti....,. TMM from such a dimdinnniional manifold embedded in R.,, d < D, the task is estimate d. More generally, if the dataset is living on unions of manifolds with different IDs, the task is to estimate d locally for a given point x For real-world datasets, however, samples are corrupted by noise making the dataset full-dimensional, i.e. d = D. In this case, estimating the ID corresponds to estimating how many main degrees of freedom there are in the observed dataset. We refer to those degrees of freedom to directions of large variability in the following.
Estimating ID:
Standard Normalizing Flows: In the simplest case, an NF So is a change of variable trans- forming a sample from the unknown distribution p(æ) to a sample from a standard Normal ((00, [D) If M is full-dimennsinal,, i.e. d D, then the resulting density is given by (a) det J (u)) (N( Ip) where fx), and the parameters 0 are updated to
minimize
(kz(p<))lpooz)) = -px [log po (xx) + const.
(1)
For the general case where d < D, the general change variable formula needs to be considered, omit the NF's dependence the parameter 0 and write
e.g. [17 & TO 3) From
instead of fo-
Notations: We denote the data density with support on MM as p(r). Given a sample x ~ p(x), if we add some Gaussian noise to it, the resulting random variable ā = x + has the following density
/ N(
2 (T)
where Tn is the D x D unit matrix. The Jacobian a flow f RRD + R has D eigenvalues and singular values, which we both denote by ( A(),
Related work
Estimating the ID is well-studied problem with a vast literature, see 5 for exhaustive overviews.
Historically, two main branches have developed: global and local methods 4 Global methods estimate the dimensionality of the dataset globally with methods based on PCA is the most famous representative of this class, while local methods do estimate locally. Consistent local estimators are based nearest neighbor statistics. Intuitively, the volume of d- dimeensiional ball scales as od with its radius r, and, therefore, the number of nearest neighbors within the r- ball of a point should scale similarly. This intuition was formalized by [13) and generalized in [4]. Recently, [9] derived the distribution of the distance to the second nearest neighbor- power law with the ID as the exponent. We choose this method, coined twoNN, as
Nearest Neighbor methods:
Note, that local estimator can be used global ID estimator by simply averaging over different samples.

---

representative for nearest neighbor methods and compare its performance with our method in Section
5
Methods based on NN: Neural Networks (NN) scale to large datasets. Surprisingly, to the best of method, there exists only one method which attempts to directly estimate
knowledge, next the ID using an NN based method [32]. coined LIDL (see below for a detailed description). However, there exist different indirect methods which use performance metrics to estimate the ID. The general idea is to train different models with different latent dimensionalities and compare their performance on chosen metrie, see e.g. corresponds to the right latent dimensionality. However, the estimate will be relative to the chosen performance metric and therefore might not reflect the true ID. As an example of this relativity, we refer to Figure 14 in [ which use their basba method to estimate the ID of the CelebA dataset 24]. They get different results when using the FID-score 15] or reconstruction error as performance metric. In [30] it was argued that the Jacobian of the encoder f: RRD + R of an Autoencoder can give information of directions of contraction. Intuitively, manifold directions correspond to directions of low contraction while off- off-manifold directions correspond to directions of high contraction. The gist of this idea is very similar to our intuition which we will present Section 4 as directions of contraction can be directly related to the singular values of the encoder's ' Jacobian. However, the number of contractive directions will only give a lower bound on the ID.
3] Arguably, the model yielding the best result on this metric
propose to use NFs to estimate the ID. LIDL stands for locally intrinsic dimensionality likelihood and is based on the assumption that the inflated log- likelihood log 9 (x)) scales linearly in o² with the normal space dimension as slope. More precisely, they argue that the inflated distribution (x) can be written as the product of p(ar) and the noise distribution restricted on the normal space, i.e. (2) = p(x))N(x:
LIDL: 32
TD-a) where N(x; x. TD-a) is a (D d) dimensional Gaussian in the normal space of x. This intuition is mathematically confirmed in 11 under certain conditions on the manifold and generating latent distribution. Thus, [32] estimate the rate at which the log-likelihoods change depending on the noise magnitude o², and therefore train different models with different
noise magnitudes of <.... < σ% to estimate that change.
LIDL heavily relies on the assumption that (x) = p(x) ID-d). which is generally only true for sufficiently smooth manifolds and latent distributions. see [17] for details. Even if these conditions are fulfilled, the outcome of LIDI. depends on the noise magnitudes of < ... < d used to estimate the log-likelihood rate. However, the optimal range again depends on both the manifold and generating latent distribution which is hard to estimate a priori [7
We will revisit these issues
in the experiments, Section 5
4 Method
How can we estimate the intrinsic dimensionality of data sampled from a manifold using an NF?
Simplest scenario: Assume the simple case where the target distribution p(x) is a normal distribution, i.c. p(x)= N(,, Σ) with μ E RD and
Σ =
of > 0.
(3)
Thus, we assume that the data manifold is given by the entire embedding space, M = RD_ Note,
however, that if o? - O, 1,....I - d, this corresponds to samples from d diddinnnsiona manifold embedded in R2D Then, the true NF f transforming x NN Σ) into f (a)
distributed according to (O (D) is given by f (x) = (x+ -1)/o,, 1,...:.. D, with Jacobian
1
J (x) = diag
(4)
OD
Therefore, an eigenvector of J (z) corresponding to a large eigenvalue 1 (i.e. small o; ) is in direction of small variability in the data. It is easy see that the same holds for more general covariance matrices Σ. The true NF f transforming æ NN,,, Σ) into u = (x) distributed according to (0, given by
-((x)=> (x-
(5)
with Jacobian
(z-((x) = A ST
(6)
3

---

where == DTD D = . and S is orthonormal and consists of the eigenvectors of Σ. Thus, the eigenvalues of , (x) are given by o ...... as for the simplest scenario.
From simple to the generic scenario: In general, the NF f-1 non-linearly transforms sample a p(a)) such that u = (ar) is distributed according to (0, Ip). Hence, Equation ( does not hold anymore. However, Equation (5) is good first-order approximation as locally the flow acts linearly.
f R (z") +J 1 (z")(x=x")
What follows is that a flow f not only transforms globally samples from p(r) to samples from a Gaussian, but also locally. This already observed in (7] (Lemma 1) for f, i.e. for the direction from latent to data space. The same holds true for f-1 which immediately follows from the delta method 226
Lemma Let x² be a sample from p(x), and let f-1 be the flow such that x' ~ ID) where f (I*). Let ~ NN0 Ip) and O) be scalar. Consider samples generated by == f + SE). Then, for - 0 we have that (3 =²) - NN (x-)))))("""))-11(())))))) where the convergence is in distribution.
J)-i(x")
Lemma states that a small ball around x* will be mapped into a ellipsoid where the principal axes of the ellipsoid are given by the eigenvectors of the Gram matrix J, 1 (x*)² Jy (x*). Those cigenvectors are the singular directions of , (x*) and correspond to direction small and large varaibility if the corresponding singular value is small or large, respectively. For Jy (x*) symmetric,
the singular and eigenvalues coincide F]
Thus, the flow of arguments from the simplest scenario takes on and we observe:
Observation 1: Large singular values of the NF's Jacobian evaluated at æ correspond to directions of small variability in the data. Directions of large variability, however, correspond to small singular values.
How make of this observation to estimate the ID of data manifold? When training an NF on clean manifold data (i.e. samples from a manifold without intrinsic noise), Observation 1 predicts clear change in magnitude between singular values corresponding off-manifold and on-manifold directions [4 Indeed, we can observe such a change in magnitude in various toy examples, see Section 4.1 However, to estimate d based on this observation only would require setting arbitrary threshold on the magnitude of those singular values. On the other hand, in a more realistic scenario, real world data have some intrinsic noise.
Data with intrinsic noise: With the same setting as the simplest scenario, we now additionally assume that the intrinsic noise is coming from standard Gaussian with magnitude do. i.e. p(z) N(,, E + I).. Then, Equation 4 turns into
(x) = diag
+
+
Now, what happens if we inflate the data-manifold with Gaussian noise of variance a²? For directions of small variability in the data, of is small. Thus, only if o² exceeds the intrinsic noise magnitude oß expect see change in ( For directions of large variability, however, we expect to change in ()) only if 0² is greater than of + of in this case of is not small. To account for the more general case where the intrinsic noise is not isotropic, we denote the intrinsic noise in the direction of the singular vector corresponding to singular value (+) as (i) in the following.
Observation 2: If we were to inflate the noisy data-maninn manifold with a Gaussian of variance o² in direction of
(i) small variability, we expect the corresponding singular value (0) to change significantly only if o² >> (i).
NNote, that the singular values are always positive and real, and therefore more convenient to analyze than the eigenvalues.
'Theoretically, eigenvalues/ singular values corresponding to off manifold directions need to become infinity for d dimimensionna manifolds. Indeed, training an NF on clean manifold data creates numerical instabilities as observed in 17 20 6

---

i large variability, we the corresponding singular value ( to change significantly only if o² >> (i) + o...
Indeed, we show in the supplementary that if the noise is only added in the manifold's normal space, then only those singular values will change while the singular values in direction of large variability will stay constant. Given this observation, we propose to train separate NF for different noise magnitudes of <... < Zy calculate for all of those models the flow's singular values on a sample from the manifold, and, according to Equation
(8). find parameters og and & such that 8: +o0 fits the set of pairs { X (z))) Note that Br/a; corresponds X if no noise was used to inflate the manifold and that až corresponds to the onset of strong decay.
X(o²)
D. I.....,, clear pattern separating singular values corresponding to directions of small and large variability, respectively. According to Observation 1, B:/a; must be much larger for large variability directions and according to Observation 2, the onsets of must he smaller compared to small variability directions. More concretely, the latter suggests that counting the number of singular values with onset S a,
Our method for estimating the ID: Given (a,, 3,) for all
we expect to see a
F(a) # {i E (1. .....,,,1 D) s.t. a S {a..
F(a) should have a plateau when varying from -oo to corresponding to the number of singular values in direction of small variability. Ideally, this plateau can be seen clearly when plotting F(a) and thus the number of off- directions can be directly read out.
Alternatiely, a sum of two sigmoidal functions can be fitted to approximate F,
(a)= 1 + ba 1 (aa
02
(10)
where < C2 and hence d1 corresponds to the number of small variability directions and 02 to the number of large variability directions, see Algorithm for an algorithmic overview of the method.
Algorithm 4: Estimating the intrinsic dimensionality given set of data points.
Require:
Dataset DD = {2;; LMM with E D. Samples {xt K C 'D to use for estimating the ID. (iml,
Noise magnitudes of < < NN-
for n = to N do
add noise to dataset: D (2; ei), where e; (N( + learn da3 using an NF fn
+ calculate and store singular values (A (at( (at) of J fn (It), I..... K
end for
- calculate mean singular values for all i and n, {10 1/4 Ik=1 2 (z+)
for i = 1 to D do
B store 3,) such that \(o2) Val
fits {(o ((1) I==I....N
end for
+ calculate F(a) = #(i s.t. a; S a for E (-oc,
fit F(a) given by Equation (10) and store parameter a2
- estimator given by d = a2
The averaging over the singular values does not have geometrical interpretation as such. We are only interested in the cut-off separating singular values corresponding to on- and off-manifold directions. Hence, the averaging reduces the noise introduced by limited sample size or unexact learning of qaa.
4.1 Pedagogical example
We illustrate our method on a pedagogical example a uniform distribution on the unit sphere corrupted by some intrinsic Gaussian noise with magnitude of = 10-6 6 In Figure [ left, we show how the three singular values change log-log-scale depending on various noise magnitudes. For the error bars, we use 200 clean training examples (i.e. not corrupted by noise). After the intrinsic noise magnitude is surpassed (first dashed line from the left), the large singular value changes with slope -0.5 whereas the two smallest singular value barely change. After the noise magnitude
5

---

exceeds the radius of the sphere (second dashed line from the left), the singular values approach each other. In the right figure, we show F(a) and its estimate F(a). The title of the right figure shows the output of Algorithm 4 the parameter d2 of F(a).
22
Intinsicc
radius
Fla) Fla)
tangent tangent
d=2
10+-
10a
10-4 10
10
10
107
-8
Inflation noise d²
log a²
Figure 1: Left: vs. o² plot as described the main text. The red curve corresponds to singular values associated direction of small variability (i.e. normal to the manifold). The blue and yellow curves correspond to singular values associated to directions of large variability (i.e. tangent to the manifold). Right: F(a) and ((a) as defined in Equations and 10
4.2 Special case:
Images
So far, our theory assumes unbounded data such that if the inflation noise o² tends infinity, a² + co, the eigenvalues of the flow's Jacobian tend to 0, À O. According theory, this decay happens much later for singular values corresponding to manifold directions than for off-manifold directions manifesting
plateau for the decay onsets According to Equation (8) those onsets reflect the amount of variability in the manifold directions.
However, some real world datasets are bounded. For example, RGB images consist of pixels which take values in [0, 255]. Thus, for o² + oc, inflated images will become noisy and all the information about the manifold is lost. Now, assume that o is the maximal amount of noise that can be tolerated before all the images become so noisy that they become meaningless. Then, all onsets greater or equal to of will correspond to manifold directions as the amount of variability in manifold directions must be greater than o
How can we set this max the least arbitrary way? the supplementary, Section A.4, we compute this maximal amount of noise from the following rationale. If o² is too large, then essentially all the pixels will saturate to either the lower or the upper bounds, so reasonable maximal amount of noise such that 50% the pixels saturated. the pixel values fall in the interval [0, Xmax] (and if assume that pixel values are uniformly distributed on this interval), then a max 0.68.r
Remark
(i) Note, for K = Algorithm estimates the ID locally at given point x;. In the supplemen- tary, we show that we can learn the locally on the lolipop dataset proposed (32). This manifold consists of I dimensional line (the stick of a lolipop) and dimensional disk.
(ii) There is no need to calculate F(a) for all a R since F(a) E (0,1,..., 19,1,...,1) D}. Given for all i = ,,...,,. D, we set E [Oiminy Ormav) where O'min argmin ( and O'max arg.ax ).

---

Distribution
D
ID
ID-NF
LIDL
twoNN
mixture on sphere correlated on sphere mixture on torus correlated on torus correlated on hyperboloid unimodal on hyperboloid exponential on thin spiral mixture on swiss roll correlated on swiss roll mixture stiefel
3
2.01
1.91
1.98
3
2.04
1.66
1.99
3
2
2.02
2.05
1.97
3
2.02
2.07
2.02
3
2.02
2.01
1.99
3
2
2.01
1.92
1.96
2
1.00
3
2.02
2.26
1.98
3
2.02
2.08
1.94
4
1.07
1.19
0.99
Table Performance of different ID estimation methods (ID-NF, LIDL, twoNN), on various datasets. Numbers highlighted in orange depict strong deviation from ground truth.
5 Experiments
We benchmark our method with twoNN and LIDL, see Section 3 The latter very similar to our method as we both inflate the manifold with different values of o² and then use an NF to learn 1a2. However, [32] estimate the rate at which the log-likelihoods change depending on the noise magnitude o², whereas study how the flow's Jacobian eigenvalues evolve. Hence, rely on the NF being able to transform a sample
p(æ) to a standard Gaussian a much easier task than learning the inflated distribution 9,² exactly. Also, don't the assumption that 4, (z) = p(x) (z; æ, Ip-a) and thus we don't need to fine-tune the different noise magnitudes of. ................................ N. see Section for more details.
As an abbreviation for our method, we use ID-NE, We refer to the supplementary for corresponding training details and additional figures. The code for using ID-NF or reproducing our experiments can be found here https: //github. com/ chntttttt/ID
5.1 Low-dimensional synthetic datasets
We test our method on various synthetic datasets with known ID: sphere, torus, hyperboloid, thin spiral, swiss roll, and Stiefel manifold, see Table We use different distributions on those manifolds to test the sensitivity on the sampling distribution p(r). We compare our method with the LIDL and twoNN estimator introduced Section 3 For those low-dimensional examples, all methods perform well. The twoNN and our method estimate all ID exactly. The LIDL method, however, shows some sensitivity towards the sampling distribution (see the highlighted estimate for the correlated on sphere distribution), and slightly overestimates the swiss roll dimensionality (see the highlighted estimate for the swiss roll). However, we did not try to find the optimal range for o² and use the same across all distributions. By this, we want to demonstrate the disadvantage of having to estimate the correct range for every distribution separately.
5.2 High-dimensional synthetic datasets
Next, study how the methods scale higher embedding dimensions. For that, sample uniformly from S(D/2) embedded in E for different even values D. For fair a comparison, only use training set of size 10 for all methods. In Figure left, display how the different methods estimate the dimensionality. ID-NF on par with LIDL and outperforms twoNN. The latter suffers from the curse of dimensionality as mentioned in the introduction, Section
In Figure right, we repeat experiment using only 10 samples. ID-NF still performs very well. LIDL,, however, has greater variability and significantly underestimates the ID for d = 200 (i.e. D 400). This indicates another benefit of our method: as opposed to LIDL, we do not need to learn the density exactly, task that requires samples for higher dimensions.

---

10" samples
10' samples
200
190
estimated intrinsic dimensionality
estimated Intrinsic dimensional
170
twoNN
twoNN
LIDL
160-
LIDL
120
90
100
70
50
60
30
40
10
30
70 90 110 130 150 170 190 true intrinsic dimensionality
40
60
80
100
120
140
160 180 200
true intrinsic dimensionality
Figure 2: Left: Performance of different ID-estimation methods on uniform samples from S(222) embedded in RR for D ranging from 20 to 400. Right: Corresponding plot using 10 instead of 10 samples for traning.
5.3 StyleGan image manifolds
In 3 a image manifold was created by using a recent variant generative adversarial network, StyleGan2 [19), trained high-quality image dataset, the FFHQ dataset (18). When generating new images, only d of total 512 latent variables were varied while keeping the others fixed. Note, that this does necessarily generates a d-dimensional image manifold. Indeed, [29] showed that whenever the generater is Lipschitz continuous, the ID is at most d. We downsample those images to resolution of 64 x 64 i.c. the embedding space has dimension D 12288.
We apply our method on the StyleGan
64 image manifold consisting of 10 and 2 10 images, respectively. Unfortunetly, training N flows these datasets is computationally expensive, so is calculating the eigenspectrum of the flows Jacobian for K samples. However, we are only interested whether the onset of the eigenvalue's decay happens after max 255 0.68 not, see Section 4.2 Therefore, it is sufficient to train only 3 NFs: one where the inflation noise a has very small magnitude, one where
2 and
255 0.68, and where is very large.
In Figure 3 we show the heights and onsets for all singular value curves of specific example for d 2 the left, and d 64 the right. We highlight the points corresponding the 2 smallest and 64 smallest singular values, respectively, in red. The dashed vertical line is located at mmax 255 0.68. For d 2. the smallest two singular values nicely separated, though count d 4 singular values which have onsets greater than ou for this particular example. For d 64, we count d 57. When averaging over K samples, our estimate for is d 4.06 and for 64 we have d 62.24
We also estimated the ID using LIDL, however, we did not get a consistent estimator. In fact, depending on the range one uses for the inflation noise o², the estimate varies greatly.
5.4 Proof-of-concept applications
We show that the ID can be used to improve latent variable models and observe that out-of-distribution (OOD) samples have a higher
Latent variable models: Recently, two latent variable models for manifold valued data based on
NFs were developed, the manifold flow (M-flow) [3] and denoising normalizing flow (DNF) (16). Both methods rely on knowing the exact number of latent variables (i.c. the ID) which limits their
applicability to real-world problems. For instance, the true ID (if exists) the CelebA-HQ [18] is
'We do not average over the singular values since we are not interested in the cut-off separating eigenvalues corresponding and off manifold directions. We estimate df for each sample individually. and then average.

---

StyleGan
StyleGan
helghts
-1
heights
-1
-2
-2
4
-2
2
onsets
onsets
Figure 3: Scatter plots of onsets and heights, (a, B/),, for all singular values in log-log scale, In red, the d smallest singular values are highlighted. The dashed line corresponds to the dmax 0.68 255.
unknown and the latent dimensionality was set arbitrarily to 512. We used our method to estimate the ID and obtained = 130. We then trained an DNF with the same architecture as in the original paper using a latent dimensionality of 130 instead of 512. After 300 epochs, we assess the quality of the generated images with the Frechet Inception distance (FID) where lower distances are better [15] We obtain an FID score of 36.92. The original DNF has an FID score of 34. 14, and the flwwow of 38.07 after 500 epochs of training. Thus, we obtain very similar results in terms of generative power (measured by the FID score) with only 130 latent dimensions instead of 512.
ID on OOD-samples: Having trained on a specific dataset, such as the StyleGan 2d image manifold, how does the ID changes for out-of-distribution (OOD) sample? In table we report the average ID estimated on K = 50 samples from different datasets when trained on the Stylegan2d image manifold. As we can see, the ID of OOD samples significantly higher than for in-distribution samples. Intuitively, OOD samples live on the manifolds normal space, and thus, in case d < D/2, have more directions of large variability. We conduct more OOD experiments the supplementary.
Datasets / OOD
StyleGan2d
StyleGan64d
CelebA
StyleGan2d
4.06 1.75 151.72 + 54.04 272.14 + 261.71
Table 2: Average ID estimates for 50 samples using method trained StyleGan2d.
6 Discussion
We have introduced new method to estimate the ID exploiting the ability of NFs to transform data into samples from a Gaussian random variable. Based on some simple teck-of-the-envelope calculations, we derived how the singular values of the flows Jacobian evolve when inflating the data with Gaussian noise before training. Crucially for our estimator, singular values corresponding to the directions of large variability (i.e. manifold directions) evolve significantly different compared to singular values corresponding to the directions of small variability (i.e. off-manifold directions).
We demonstrated that we can estimate the ID for different manifolds with different sampling dis- tribution. We compared our method to a state-of-the-art ID estimator based on nearest neighbor statistics, twoNN, and to related method which is also based on NFs, LIDL. We outperform twoNN for high dimensions (Table []. and LIDL for small data regimes (Figure 2 and images, Section As opposed to LIDL, we don't 't have to fine-tune the noise magnitudes of o. However, we need σi to be small and ō to be sufficiently large which may be computationally expensive.
We showed that our method scales to RGB images of resolution 64 x 64 populating a d 2 and d 64 dimensional manifold, where estimate d 4 and for d = 62, respectively. However,

---

this estimate is sensitive to the number K of images used to estimate d (we used K 50), the number of NFs trained on (we argued that N 3 is sufficient), and the maximum amount of noise to be tolerated before the images become too blurry (Ømax = 0.68 255 see Secetion 4.2). Neverthelesse, to the best of our knowledge, this is the first method which estimates the IID on such high-resolution image manifolds consistently. Additionally, we demonstrated that estimating the II) can help to improve recently developed latent variable models based on NFs where knowing this exact number is crucial. Also, observed that for out-of-distribttion (OOD) data, the ID is higher than for on- on-manifold examples motivating further research on the relation between OOD samples and ID.
Finally, our theoretical derivations rely on the assumption that data is unbounded, although we adapted our methiod for bounded data too. However, for this case more research is needed to understand the exact behaviour the flow's s Jacobian singular values when approaching the boundary. An interesting direction to pursue is to adapt the target distribution and inflation noise to the data topology. For images, this amounts to changing the NF's target distribution to be uniform instead of Gaussian, and using uniform instead of Gaussian noise.
Broader Impact: As theoretical paper, we don't foresee any direct negative social impacts of our work.
Acknowledgments and Disclosure of F Funding
This study has been supported by the Swiss National Science Foundation grant [0003A_175644
References
[1] Alessio Ansuini, Alessandro Laio, Jakob H Macke, and Davide Zoccolan. Intrinsic dimension of data representations in deep neural networks. Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[2] Nitish Bahadur and Randy Paffenroth. Dimension estimation using autoencoders, arXiv preprint arXiv:1909.10702, 2019.
[3] Johann Brehmer and Kyle Cranmer. Flows for simultaneous manifold learning and density estimation. Advances in Neural Information Processing Systems, 33, 2020.
[4] Francesco Camastra and Antonino Staiano. Intrinsic dimension estimation: Advances and open problems. Inf. Sci., 328:26 01,6441,22 2016.
[5] Paola Campadelli, Elena Casiraghi, Claudio Ceruti, and Alessandro Rozza. Intrinsic dimension estimation: Relevant techniques and a benchmark framework. Mathematical Problems in Engineering, 2015, 2015.
[6] Eike Cramer, Felix Rauh, Alexander Mitsos, Raál Tempone, and Manuel Dahmen. Nonlinear isometric manifold learning for injective normalizing flows. arXiv preprint arXiv:2203.0388 039334, 2022.
[7] Edmond Cunningham, Adam Cobb, and Susmit Jha. Principal manifold flows. arXiv preprint drXiv:2202.07037, 2022.
[8] Edmond Cunningham, Renos Zabounidis, Abhinav Agrawal, Ina Fiterau, and Daniel Sheldon. Normalizing flows across dimensions. arXiv preprint arXiv:2006.13070, 2020.
[9] Elena Facco, Maria d' Errico, Alex Rodriguez, and Alessandro Laio. Estimating the intrinsic dimension of datasets by a minimal neighborhood information. Scientific reports, 7(1):1-8, 2017.
[10] Mevlana Gemici, Danilo Rezende, and Shakir Mohamed. Normalizing flows on riemannian manifolds. arXiv preprint arXiv:1611.02304 2016.
[11] Sixue Gong, Vishnu Naresh Boddeti, and Anil K. Jain. On the intrinsic dimensionality of image representations. In Proceedings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
10

---

[12] Daniele Granata and Vincenzo Carnevale. Accurate estimation of the intrinsic dimension using graph distances: Unraveling the geometric complexity of datasets. Scientific reports, 6(1):1-12. 2016.
[13] Peter Grassberger and Itamar Procaccia. Measuring the strangeness of strange attractors. Physica D: Nonlinear Phenomena, 9:189-208, 1983.
[14] Matthias Hein and Yves Audibert. Intrinsic dimensionality estimation of submanifolds in rd. In Proceedings of the 22nd international conference on Machine learning, pages 289-296, 2005.
[15] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by two time-scale update rule converge to local nash equilibrium. In Proceedings of the 31st International Conference on Neural Information Processing Systems. pages 6629-
6640, 2017.
[16] Christian Horvat and Jean-Pascal Pfister. Denoising Normalizing Flow. In Advances Neural Information Processing Systems, volume 34, pages 9119-9111. Curran Associates, Inc., 2021.
[17] Christian Horvat and lean-Pascal Pfister. Density estimation on liw-dimensional manifolds: an inflation-deflation approach.
[cs, staf], February 2022. arXiv: 2205..
[18] T Karras, S Laine, and Aila. A style-based generator architecture for generative adversarial networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
[19] Tero Karras, Samuli Laine, Miika Aittala, Janne Hellsten, Jaakko Lehtinen, and Timo Aila. Analyzing and improving the image quality of stylegan. In 2020 IEEE/CVE Conference on Computer Vision and Puttern Recognition (CVPR), pages 8107-81 16. IEEE, 2020.
[20] Hyeongju Kim, Hyeonseung Lee, Woo Hyun Kang, Joun Yeop Lee, and Nam Soo Kim. Softflow: Probabilistic framework for normalizing flow manifolds. Advances in Neural Information Processing Systems, 33, 2020.
[21] N. Krueger and M. Felsberg. A continuous formulation of intrinsic dimension. In Proc. BMVC, pages 27.1-27.10, 2003. doi: 10510.24/4CC.7.27.
[22] J.M. Lee. Introduction to Riemannian Manifolds. Graduate Texts in Mathematics. Springer International Publishing. 2019.
[23] Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. arXiv preprint arXiv: 1009:080090031115 2018
[24] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference Computer Vision (ICCV), December 2015.
[25] Marius Muja and David G. Lowe. Scalable nearest neighbor algorithms for high dimensional data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(1 36(11):2227-2240 2014.
[26] Gary W. Oehlert. A note on the delta method. The American Statistician, 46(1):27-29, 1992.
[27] Rich Pang, Benjamin Lansdell, and Adrienne L Fairhall. Dimensionality reduction in neuro- science. Current Biology, 26( ())::666- 2016.
[28] Stefano Piana and Alessandro Laio. Advillin folding takes place on hypersurface of small dimensionality. Phys. Rev. Lett., 101:208101 Nov 2008
[29] Phillip Pope. Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein. The intrinsic dimension of images and its impact on learning. arXiv preprint arXiv:2104.08894 2021.
[30] Salah Rifai, Pascal Vincent, Xavier Muller, Xavier Glorot, and Yoshua Bengio. Contractive Auto-Encoders Explicit Invariance During Feature Extraction. page 8.

---

[31] Paul K Rubenstein, Bernhard Schoelkopf, and Ilya Tolstikhin. On the latent space of wasserstein auto-encoders. arXiv preprint arXiv: 1tt2. 037611, 2018.
[32] Piotr Tempezyk, Przemystaw Spurek, and Jacek Tabor. LIDL: LOCAL INTRINSIC DIMEN- SION ESTIMATION USING APPROXIMATE LIKELIHOOD, page 10, 2021.
[33] S Velliangiri, S Alagumuthukrishnan, al. A review of dimensionality reduction techniques for efficient computation. Procedia Computer Science, 165:104-11 101-111, 2019.
[34] Yasi Wang, Hongxun Yao, and Sicheng Zhao. Auto-encoder based dimensionality reduction. Neurocomput, 184(C))232-242, apr 2016.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Section
(b) Did you describe the limitations of your work? [Yes] See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Section 6
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof's of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material URL)? [Yes] See https://github. http:///giihuu..coo/ch...
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] In the supplemental material.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Table
(d) Did you include the total amount of comute and the type of resources used (c.g.. type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (c.g., code, data, models) or curating/rellasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're
using/curating? [No]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [No]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
x
12


Reviews:
[{"review_id": "fKQFo5lyDPZ", "reviewer": "Reviewer_Vtze", "summary": "This paper focuses on an interesting and important problem in machine learning: For a given set of data around a low-dimensional manifold embedded in a high-dimensional R^D, how can we estimate the intrinsic dimension (ID) of the manifold. The traditional estimator based on the nearest neighbor statistics cannot be applied to large datasets due to the complexity and suffers from the curse of dimension. In this paper, a normalizing flow (NF) based method is proposed, which solves the problem by using the following steps: 1) Add Gaussian noise with different variances to the dataset. 2) Estimate the density functions for noisy data with different variances by a set of NFs. 3) Estimate the ID from the eigenvalues of Jacobian matrices of tranformations defined by NFs.", "questions": "On the justification:\n\n1) The main \"theoretical\" basis of the method is Observation 1, but it is just an \"observation\" instead of a theorem (even an \"informal\" theorem). So there's a lot of ambiguity here. What are definitions of variability and direction of variability? What does small/large variability mean? How can we quantify the variability? As an example, does the variability of a standard Gaussian distribution have the same magnitude for all directions? If so, how about the uniform distribution or other isotropic probability distributions?\n\n2) In addition, does Eq. (8) mean that the \"variability\" is a constant for any position for a standard Gaussian distribution? Can we choose the target distribution of f^{-1}(x) as uniform distribution or other isotropic probability distributions?\n\n3) The similar question for Observation 2: Why can the conclusion on the Gaussian distribution be extended to a general noisy data-manifold?\n\nAs a summary, I believe the observations are reasonable, and the method developed based on the observations really works. But more thorough analysis and explanations are required. I hope to see two theorems (even informal theorems based on some specific assumptions) in the revision.\n\nSome other comments:\n\n4) In Lines 43-50, a very interesting problem is proposed: The dataset may be on a union of manifolds, and the local ID is more useful than the global one in this case. But all experiments in this paper are on estimation of global ID. Can the NF method be applied to estimation of local ID? Is there any difficulty?\n\n5) It seems that the intrinsic noise is assumed to be Gaussian and spatial homogeneous. Will the performance of the algorithm be greatly affected if the assumption does not hold?\n\n6) Besides the \"dimension number\", people are also interested in the component related to each dimension. Can we get, for example, the projection of data on the dimensions, from eigenvectors of Jacobian matrices of NFs?\n\n7) The paper is highly related to the SoftFlow proposed in [22]. In SoftFlow, one NF is trained for different noise magnitudes with the noise magnitude being a parameter of the NF. This technique may be also helpful for this paper since SoftFlow can easily obtain the structure of the data independent of noise.", "limitations": "Authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nAuthors use the structure and property of NFs in a very clever way and show that we can obtain the information on ID from eigenvalues of Jacobian matrices of NFs. As far as I know, the eigenvalues of the Jacobian matrices of are rarely noticed in the research on NFs. In addition, the method is technically sound, and experiments also demonstrate the effectiveness of the proposed method.\n\nWeaknesses:\n\nThe main weakness of the paper comes from that the justification of the proposed method is not well formulated. See below for details.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UlfAKmyZYJt", "reviewer": "Reviewer_aewG", "summary": "This paper proposes a new approach termed ID-NF to estimating intrinsic dimensionality based on normalizing flows which can scale to large datasets and high dimensions ($64\\times64\\times 3$).  \nID-NF first specifies a dataset $\\mathcal{D}=x_i, x_i\\in \\mathbb{R}^D$, $K$ samples $x_1^*, \\dots, x_K^* \\in \\mathcal{D}$, and $N$ noise levels $\\bar \\sigma_1^2 <\\dots <\\bar\\sigma_N^2$. \nFor each noise level, ID-NF injects noise $\\epsilon_n\\sim \\mathcal{N}(0, \\bar\\sigma_n^2 I)$ to the data and use an NF $f_n$ to learn the distribution $q_{\\bar\\sigma_n^2}$. Then ID_NF calculate the eigenvalues ${\\lambda_n^{(i)}(x_k^*)}$ of $J_{f^{-1}_n}(x_k^*)$ for each $k=1,\\dots,K$ and compute $\\hat\\lambda_n^{(i)} = \\frac1K \\sum_1^K \\lambda_n^{(i)}(x_k^*)$.\nBy fitting $\\hat\\lambda_n (\\sigma^2) = \\frac{\\beta_i}{\\sqrt{\\alpha^2_i + \\sigma^2}}$ with $\\alpha_i, \\beta_i$, ID-NF use {$\\alpha_i$} to estimate intrinsic dimension.  ", "questions": "* I think Table1 is not a fair comparison, since the dimensionality estimated by ID-NF is naturally around an integer, but LIDL seems not. ", "limitations": "Limitations seen above. Societal impact: none", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n* To the best of my knowledge, the intrinsic dimensionality estimation method based on NFs is novel. \n* Detailed experiments on pedagogical examples, low-dimensional synthetic examples, and high dimensional images generated by StyleGAN show the effects of this method. \n\n**Weakness**:\n* The paper approximate the NFs with $f^{-1}(x) \\approx f^{-1}(x^*) + J_{f^{-1}}(x^*)(x-x^*)$, thus the distribution of $x$ should be approximately Gaussian. Then the Observation1 and 2 holds. This is valid locally, but not globally. I think this gap is not well addressed in the paper. \n* Training NFs is expensive.  For $N$ noise levels, ID-NF should train $N$ NFs to approximate $q_{\\sigma_n}$, which is quite expensive. Computing eigenvalues of $J_{f^{-1}}$ for many high-dimensional samples ($10^4$ for 2d-styleGAN  and $2\\times 10^4$ for 64d-styleGAN) is also expensive.\n* Algorithm4 computes mean eigenvalues of $J_{f^{-1}}$. I think for different samples $x_k^*$, eigenvalues of $J_{f^{-1}}(x^*_k)$ correspond to the variability along the directions indicated by eigenvectors, so how is the averaging operation performed? \n\n**Minor**:\n* Line188: grea*ter.\n* Line159: As I understand, $\\beta_i/\\alpha_i$ should be larger for *small* variability directions? \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Q9Xd4vHOXYp", "reviewer": "Reviewer_WmkV", "summary": "This paper introduces a novel NF-based algorithm to estimate intrinsic dimension. The algorithm is based on the observation that large variability is connected to small eigenvalues of the Jacobian, and that the variance of intrinsic noise can affect where the eigenvalue changes significantly. To estimate intrinsic dimension, this paper fits the Jacobian, and further uses two sigmoidal functions to fit the thresholding function that should have a plateau. Empirically, this paper compares the algorithm with prior methods on several experiments where the true intrinsic dimension is known. ", "questions": "- What is the theoretical guarantee of the proposed algorithm? This question can include a lot of things, such as average-case guarantee or worst-case guarantee, bounds on errors or failure probabilities, etc. Do you have answers to at least one of these questions?\n\n- What is the complexity of the proposed algorithm? \n\n- Do you have some assumption on the NF model, as different NF models behave very differently? Are there differences if you test different NF models in your experiments?\n\n- How did you choose $N$ and noise magnitudes $\\bar{\\sigma}_n^2$ for $n=1,\\cdots,N$? Is there a theoretically optimal schedule? What is the affect of changing this schedule, either theoretically or empirically?\n\n- Does your algorithm lead to successful, practical applications that use intrinsic dimensions? For example, after running the proposed algorithm, you can find the correct latent dimension for a GAN model, and it outperforms other latent dimensions. ", "limitations": "The authors indicate there is no negative social impact as this is a theoretical paper, which I agree with. \n\n-----------------------------\n\nAfter rebuttal, I decide to increase my score to 6. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I am not an expert in the area of estimating intrinsic dimension, so I would like to leave the evaluation of originality and significance to other reviewers. I think this paper is clearly written, and the intuition is easy to follow. \n\nThe methodology of this paper is one major strength. Using NF to estimate intrinsic dimension seems to be an interesting idea to me. The Jacobian matrix and its eigenvalues offer a nice way to investigate the sensitivity (variability) for each direction. In short, the entire section 4 makes a lot of sense to me. I especially like the idea of adding different magnitudes of Gaussian noises and training separate NFs. \n\nEmpirically, the proposed algorithm can indeed estimate intrinsic dimension very accurately and outperform prior methods, which is another strength. \n\nDespite the above strengths, I think this paper lacks some key points. On the theory side, the algorithm does not come with theoretical guarantee, for example, approximation properties or (probabilistic) error bounds. Also, the choice of NF $f$ and noise magnitudes $\\bar{\\sigma}_n^2$ can potentially affect results by a lot, but there is neither theoretical nor empirical discussion on these. Finally, there is no such experiment that the proposed algorithm finds the intrinsic dimension in a practical problem (e.g. of a real dataset) and lead to successful application (e.g. help fixing the latent dimension of a generative model). ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1QWOijnh6ak", "reviewer": "Reviewer_ozqo", "summary": "This paper discusses the use of normalizing flows for estimating the intrinsic dimensionality (d) of the data sub-manifold embedded in high-dimensional ambient space ($\\mathbb{R}^D, d < D$). The authors claim the proposed method based on flows is scalable and accurate compared to some standard techniques, e.g., nearest neighbor searches. The proposed method is based on a PCA-like rule, i.e., an eigendecomposition of a covariance transformation, by approximating the non-linear flow as a linear map with a Jacobian. The authors propose two techniques that can estimate whether a certain eigenvector is an on-manifold direction or not: the first is simply checking out the magnitude of the corresponding eigenvalue and the latter is judging the sensitivity of eigenvalues by injecting some noises. The authors validate their proposed method experimentally, compared with the nearest neighbor and another flow-based approach (LIDL) for some simple examples and StyleGAN2 manifolds.", "questions": "[Major comments]\n\n1. It seems the estimated intrinsic dimensionality is highly dependent on the manifold approximation performance of flows (i.e., the generative power of flows). Thus, it is not entirely clear whether the proposed method is suitable for extremely-complicated high-resolution datasets. Note that the method requires a down-sampling of StyleGAN-generated images (from $(1024, 1024, 3)$ to $(64, 64, 3)$), and fails to correctly estimate the dimensionality of such a generated manifold ($d=64$ but $\\hat{d}=53$).\n\n2. While the authors state the proposed method is scalable, there is no theoretical analysis as well as experimental demonstration regarding it. Because the proposed method should train a set of $N$ flows, it is not entirely sure it is indeed cheap. Please elaborate more.\n\n3. What would be the killer application of the intrinsic dimensionality estimation? Can it be used to, e.g., improve generative performance, find disentangled representations, or detect anomaly samples correctly? It will be nice if the authors state some possible applications of the proposed method by demonstrating a proof-of-concept experiment regarding it.\n\n[Minor comments]\n1. It is not clear why $\\beta_i$ should be used.\n\n2. In the pedagogical example 4.1, it is not clear why the eigenvalues of on-manifold directions are different (see Fig. 1 (a)) while the underlying sub-manifold is a 2-sphere.\n\n3. Observation 2 is not clear because (9) does not contain the injected noise $\\sigma$ explicitly (while one may infer $\\lambda^{(i)} = 1/ \\sqrt{\\sigma_{0}^{2} + \\sigma_{i}^{2} + \\sigma^{2}}$). \n\n4. In line 159 of page 4, the authors mention $\\beta_i / \\alpha_i = \\lambda^{(i)}$ must be much larger for large variability directions, while in Observation 1 they mention large eigenvalues correspond to directions of small variability.\n\n", "limitations": "The authors state the limitation of the proposed method in the Discussion section, e.g., the possible computational cost (which is consistent with this reviewer’s major comment 2) and the theoretical assumption on the boundness of the data manifold. In my opinion, the former is not fully addressed, thus should be elaborated more for a convincing presentation of the manuscript. The latter seems to be addressed well by proposing some practical solution to deal with the bounded data, e.g., $0.68 * x_{max}$ for image data.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[Strengths]\n\nThe main idea of this paper is simple and principled. It can be derived from the fundamental principle of linear algebra, thus easy-to-follow. The paper is generally well-written, while there are some confusing points (see minor comments). The proposed method outperforms other competitors including LIDL (which might be the SOTA so far), for some synthetic examples.\n\n\n[Weaknesses]\n\nI am not fully convinced with the proposed method, especially whether it can be used for a more complicated manifold regarding both in terms of accuracy and scalability (see major comments 1 and 2). In addition, I cannot find strong applications of the proposed method (see major comment 3). \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept