extfieldsofstudy:
Computer Science
Medicine

text:
Data segmentation based on the local intrinsic dimension

One of the founding paradigms of machine learning is that a small number of variables is often sufficient to describe high-dimensional data. The minimum number of variables required is called the intrinsic dimension (ID) of the data. Contrary to common intuition, there are cases where the ID varies within the same data set. This fact has been highlighted in technical discussions, but seldom exploited to analyze large data sets and obtain insight into their structure. Here we develop a robust approach to discriminate regions with different local IDs and segment the points accordingly. Our approach is computationally efficient and can be proficiently used even on large data sets. We find that many real-world data sets contain regions with widely heterogeneous dimensions. These regions host points differing in core properties: folded versus unfolded configurations in a protein molecular dynamics trajectory, active versus non-active regions in brain imaging data, and firms with different financial risk in company balance sheets. A simple topological feature, the local ID, is thus sufficient to achieve an unsupervised segmentation of high-dimensional data, complementary to the one given by clustering algorithms.

In this work, we propose a method to segment data based on the local ID which aims at overcoming the aforementioned limitations. Building on TWO-NN 23 , a recently proposed ID estimator which is insensitive to density variations and uses only the distances between points, we develop a Bayesian framework that allows identifying, by Gibbs sampling, the regions in the data landscape in which the ID can be considered constant. Our approach works even if the data are embedded on highly curved and twisted manifolds, topologically complex and not isomorphic to hyperplanes, and if they are harvested from a non-uniform probability density. Moreover, it is specifically designed to use only the distance between data points, and not their coordinates. These features, as we will show, make our approach computationally efficient and more robust than other methods. Applying our approach to data of various origins, we show that ID variations between different regions are common. These variations often reveal fundamental properties of the data: for example, unfolded states in a molecular dynamics trajectory of a protein lie on a manifold of a lower dimension than the one hosting the folded states. Identifying regions of different dimensionality in a dataset can thus be a way to perform an unsupervised segmentation of the data. At odds with common approaches, we do not group the data according to their density but perform segmentation based on a geometric property defined on a local scale: the number of independent directions along which neighboring data are spread.

Methods
A Bayesian approach for discriminating manifolds with different IDs. The starting point of our approach is the recently proposed TWO-NN estimator 23 , which infers the IDs from the statistics of the distances of the first two neighbors of each point. Let the data (x 1 , x 2 , . . . , x N ) , with N indicating the number of points, be i) independent and identically distributed samples from a probability density ρ(x) with support on a manifold with unknown dimension d, such that ii) for each point x i , ρ(x i ) is approximately constant in the spherical neighborhood with center i and radius given by the distance between i and its second neighbor. Assumption i) is shared all methods that infer the ID from the distribution of distances (e.g., Refs. 5,6,[9][10][11][12]14 . Assumption ii) is the key assumption of TWO-NN: while of course it may not be perfectly satisfied, other methods used to infer the ID from distances require uniformity of the density on a larger scale including the first k neighbors, usually with k ≫ 2 . Let r i1 and r i2 be the distances of the first and second neighbor of x i , then µ i . = r i2 r i1 follows the Pareto distribution f (µ i |d) = dµ −(d+1) i . This readily allows the estimation of d from µ i , i = 1, 2, . . . , N . We can write the global likelihood of µ ≡ {µ i } as where V . = N i=1 log(µ i ) . From Eq. (1), and upon specifying a suitable prior on d, a Bayesian estimate of d is immediately obtained. This estimate is particularly robust to density variations: in 23 it was shown that restricting the uniformity requirement only to the region containing the first two neighbors allows properly estimating the ID also in cases where ρ is strongly varying.
TWO-NN can be extended to yield a heterogeneous-dimensional model with an arbitrarily high number of components. Let x = {x i } be i.i.d samples from a density ρ(x) with support on the union of K manifolds with varying dimensions. This multi-manifold framework is common with many previous works investigating heterogeneous dimension in a dataset [8][9][10][11][14][15][16][18][19][20]24,25 . Formally, let ρ(x) = K k=1 p k ρ k (x) where each ρ k (x) has support on a manifold of dimension d k and p . = (p 1 , p 2 , . . . , p K ) are the a priori probabilities that a point belongs to the manifolds 1, . . . , K . We shall first assume that K is known, and later show how it can be estimated from the data. The distribution of the µ i is simply a mixture of Pareto distributions: Here, like in ref. 23 , we assume that the variables µ i are independent. This condition could be rigorously imposed by restricting the product in Eq. (1) to data points with no common first and second neighbors. In fact, one does not find significant differences between the empirical distribution of µ obtained with all points and the one obtained by restricting the sample to the independent points (i.e., the empirical distribution of µ , obtained considering entire sample, is well fitted by the theoretical Pareto law). However, restricting the estimation to independent samples generally worsens the estimates, as one is left with a small fraction (typically, ≈ 15% ) of the original points. Therefore, for the purpose of parametric inference, we decide to include all points in the estimation. In Supplementary Table S1 we show that restricting the estimation to independent points yields results that are qualitatively in good agreement with those obtained using all points, but with generally worse dimension estimates. Following the customary approach 26 we introduce latent variables z . = (z 1 , z 2 , . . . , z K ) where z i = k indicates that point i belongs to manifold k. We have P(µ i |d, p, z) = P(µ i |z i , d)P pr (z i |p) with with , P pr (z i |p) = p z i . This yields the posterior We use independent Gamma priors on d , d k ∼ Gamma(a k , b k ) and a joint Dirichlet prior on p ∼ Dir(c 1 , . . . , c K ) . We fix a k , b k , c k = 1 ∀k , corresponding to a maximally non-informative prior on the p and an expectation of E[d k ] = 1 for all k. If one has a different prior expectation on d and p , other choices of prior may be more convenient. (1) (3) P post (z, d, p|µ) ∝ P(µ|z, d)P pr (z|p)P pr (d)P pr (p).  (3) does not have an analytically simple form, but it can be sampled by standard Gibbs sampling 27 , allowing for the joint estimation of d, p, z . However, model (3) has a serious limitation: Pareto distributions with (even largely) different values of d overlap to a great extent. Therefore, the method can not be expected to correctly estimate the z i : a given value µ i may be compatible with several manifold memberships. This issue can be addressed by correcting an unrealistic feature of model (3), namely, the independence of the z i . We assume that the neighborhood of a point is more likely to contain points from the same manifold than from different manifolds. This requirement can be enforced with an additional term in the likelihood that penalizes local inhomogeneity (see also Ref. 14 ). Consider the q-neighbor matrix N (q) with nonzero entries N (q) ij only if j = i is among the first q neighbors of i. Let ξ be the probability to sample the neighbor of a point from the same manifold, and 1 − ξ the probability to sample it from a different manifold, with ξ > 0.5. Define n in i as the number of neighbors of i with the same manifold membership ( n in ij δ z i z j ). Then we introduce a probability distribution for N (q) as: where Z q is a normalization factor that depends also on the sizes of the manifolds (see Supplementary Information for its explicit expression). This term favors homogeneity within a q-neighborhood of each point. With this addition, the model now reads: The posterior (5) is sampled with Gibbs sampling starting from a random configuration of the parameters. We repeat the sampling M times starting from different random configurations of the parameters, keeping the chain with the highest maximum log-posterior value. The parameters d and p can be estimated by their posterior averages. For all estimations, we only include the last 10% of the points. This ensures that the initial burn-in period is excluded 28 . Moreover, visual inspection of the MCMC output is performed to ensure that we do not incur in any label switching issues 29 . Indeed, we observed that once the chains converge to one mode of the posterior distribution they do not transition to different modes. As for the z , we estimate the value of π ik ≡ P post (z i = k) . Point i can be safely assigned to manifold k if π ik > 0.8 , otherwise we will consider its assignment to be uncertain. Note that our definition of "manifold" requires compactness: two spatially separated regions with approximately the same dimension are recognized as distinct manifolds by our approach.
We name our method Hidalgo (Heterogeneous Intrinsic Dimension Algorithm). Hidalgo has three free parameters: the number of manifolds, K; the local homogeneity range, denoted by q; the local homogeneity level, denoted by ξ.We fix q and ξ based on preliminary tests conducted on several artificial data sets, which show that the optimal "working point" of the method is at q = 3, ξ = 0.8 ( Supplementary Fig. S1). As is common for mixture models, the value of K can be estimated by model selection. In particular, we can compare the models with K and K + 1 for increasing K, starting from K = 1 and stopping when there is no longer significant improvement, as measured by the average log-posterior.
The computational complexity of the algorithm depends on the total number of points N, the number of manifolds K, and the parameter q. As input to the Gibbs sampling, the method requires the neighbor matrix and the µ vector. To compute the latter, one must identify the first q neighbors of each point, which, starting from the distance matrix, requires O(qN 2 ) steps (possibly reducible to O(qN log N) with efficient nearest-neighbor-search algorithms 30 ). The computation of a distance matrix from a coordinate matrix takes as O(DN 2 ) steps, where D is the total number of coordinates. In all practical examples with N 10 6 points these preprocessing steps require much less computational time than the Gibbs sampling. The complexity of the Gibbs sampler is dominated by the sampling of the Z , which scales linearly with N and K, and quadratically with q (in total, KNq 2 ). The number of iterations required for convergence cannot be simply estimated. In practice, we found this time to be roughly linear in N ( Supplementary Fig. S2). Thus, in practice the total complexity of Hidalgo is roughly quadratic in N. The code implementing Hidalgo is freely available at https ://githu b.com/miche leall egra/Hidal go.

Results
Validation of the method on artificial data. We first test Hidalgo on artificial data for which the true manifold partition of the data is known. We start from the simple case of two manifolds with different IDs, d 1 and d 2 . We consider several examples, varying the higher dimension d 1 from 5 to 9 while fixing the lower dimension d 2 to 4. On both manifolds N = 1000 points are sampled from a multivariate Gaussian with a variance matrix given by 1/d i , i = 1, 2 multiplied by the identity matrix of proper dimension. The two manifolds are embedded in a space with dimension corresponding to the highest dimension d 2 , with their centers at a distance of 0.5 standard deviations, so they are partly overlapping. In Fig. 1a,b we illustrate the results obtained in the case of fixed ξ = 0.5 , equivalent to the absence of any statistical constraint on neighborhood uniformity (note that for ξ = 0.5 the parameter q is irrelevant). The estimates of the two dimensions are shown together with the normalized mutual information (NMI) between the estimated assignment of points and the true one. The latter is defined as the MI of the assignment and the ground truth labeling divided by the entropy of the ground truth labeling. As expected, without a constraint on the assignment of neighbors, the method is not able to correctly separate the points and thus to estimate the dimensions of the two manifolds, even in the case of quite different IDs (NMI< 0.001 ). As soon as we consider ξ > 0.5 , results improve. A detailed analysis of the influence of the hyperparameters q and ξ is reported in Supplementary Information. Based on such analysis, we identify the optimal parameter choice as q = 3, ξ = 0.8 . In Fig. 1c,d we repeat the same tests as in Fig. 1a,b but with q = 3 and ξ = 0.8 . Now the NMI between the estimated and ground truth assignment is almost 1 in all cases and, cor- Scientific RepoRtS | (2020) 10:16449 | https://doi.org/10.1038/s41598-020-72222-0 www.nature.com/scientificreports/ respondingly, the estimation of d 1 and d 2 is accurate. To verify whether our approach can discriminate between more than two manifolds ( K > 2 ), we consider a more challenging scenario consisting of five Gaussians with unitary variance in dimensions 1, 2, 4, 5, 9 respectively. Some of the Gaussians have similar IDs, as in the case of dimensions 1 and 2, or 4 and 5: Moreover, they can be very close to each other: the centers of those in dimensions 4 and 5 are only half a variance far from each other, and they are crossed by the Gaussian in dimension 1.
To analyze such dataset we again choose the hyperparameters q = 3 and ξ = 0.8 . We do not fix the number of manifolds K to its ground truth value K = 5 , but we try to let the method estimate K without relying on a priori information. We perform the analysis with different values of K = 1, . . . , 6 and compute an estimate of the average of the logarithm of the posterior value L for each K. Results are shown in Fig. 1e. We see that L increases up to K = 5 , and then decreases, from which we infer that the optimal number of manifolds is K = 5 . In Fig. 1f we illustrate the final assignment of points to the respective manifolds together with the estimated dimensions, upon setting the number of manifolds to K = 5 . The separation of the manifolds is very good. Only a few points of the manifold with dimension 1 are incorrectly assigned to the one with dimension 2 and vice versa. The values of normalized mutual information between the ground truth and our classification is 0.89. Finally, we show that our method can handle data embedded in curved manifolds, or with complex topologies. Such data should not pose additional challenges to the method: Hidalgo is sensitive only to the local structure of data. In terms of the distribution of the first and second nearest-neighbor distances, a 2-d torus looks exactly like a 2-d plane, and thus we should be able to correctly classify these objects, that are so topologically different, as 2-d objects regardless of their shape. We generated a dataset with 5 Gaussians in dimension 1, 2, 4, 5, 9 (Fig. 2a). Each Gaussian is then embedded on a curved nonlinear manifold: a 1-dimensional circle, a 2-dimensional torus, a 4-dimensional Swiss roll, a 5-dimensional sphere, and a 9-dimensional sphere. None of these manifolds is topologically isomorphic to a hyperplane, except for the Swiss roll. Moreover, the manifolds are intersecting.

Figure 1.
Results on simple artificial data sets. We consider sets of points drawn from mixtures of multivariate Gaussians in different dimensions. In all cases, we perform 10 5 iterations of the Gibbs sampling and repeat the sampling M = 10 times starting from different random configurations of the parameters. We then consider the sampling with the highest maximum average of the log-posterior value. Panels (a,b) Points are drawn from two Gaussians in different dimensions. The higher dimension varies from d 1 = 5 to d 1 = 9 , the lower dimension is fixed at d 2 = 4 . N = 1000 points are sampled from each manifold. We fix K = 2 . We show results obtained with ξ = 0.5 , namely, without enforcing neighborhood uniformity (here q = 1 , but since ξ = 0.5 the value of q is irrelevant). In panel (a) we plot the estimated dimensions of the manifolds (dots: posterior means; error bars: posterior standard deviations) and the MI between our classification and the ground truth. In panel (b) we show the assignment of points to the low-dimensional (blue) and high-dimensional (orange) manifolds for the case d 1 = 9 (points are projected onto the first 3 coordinates). Similar figures are obtained for other values of d 1 . Panels (c,d) The same setting as in panel (a,b), but now we enforce neighborhood uniformity, using ξ = 0.8 and q = 3 . Points are now correctly assigned to the manifolds whose ID is properly estimated. Panels (e,f) Points drawn from five Gaussians in dimensions www.nature.com/scientificreports/ As shown in Fig. 2b, our approach can distinguish the five manifolds. The dimensions are correctly retrieved (Fig. 2b), points are assigned to the right manifold with an accuracy corresponding to a value of the normalized mutual information (NMI) = 0.84 . Only some points of the 3d-torus are misassigned to the 4d-swiss roll. As in the previous example, L increases up to K = 5 , and then decreases, from which we infer that the optimal number of manifolds is K = 5 (Fig. 2c).
ID variability in a protein folding trajectory. As a first real application of Hidalgo, we address ID estimation for a dynamical system. Asymptotically, dynamical systems are usually restrained to a low-dimensional manifold in phase space, called an attractor. Much effort has been devoted to characterizing the ID of such attractor 4 . However, in the presence of multiple metastable states an appropriate description of the visited phase space may require the use of multiple IDs. Here, we consider the dynamics of the villin headpiece (PDB entry: 2F4K). Due to its small size and fast folding kinetics, this small protein is a prototypical system for molecular dynamics simulations. Our analysis is based on the longest available simulated trajectory of the system from Ref. 33 . During the simulated 125 µs , the protein performs approximately 10 transitions between the folded and the unfolded state. We expect to find different dimensions in the folded and unfolded state, since these two states are metastable, and they would be considered as different attractors in the language of dynamical systems. Moreover, they are characterized by different chemical and physical features: the folded state is compact and dry in its core, while the unfolded state is swollen, with most of the residues interacting with a large number of water molecules. We extract the value of the 32 key observables (the backbone dihedral angles) for all the N = 31,000 states in the trajectory and apply Hidalgo to this data of extrinsic dimension D = 32 . We obtain a vector of estimated intrinsic dimensions d and an assignment of each point i to one of the K manifolds. We find four manifolds, three low-dimensional ones ( d 1 = 11.8 , d 2 = 12.9 , d 3 = 13.2 ) and a high-dimensional one ( d 4 = 22.7 ). We recall that two spatially separated regions with approximately the same dimension (in this case, d 2 and d 3 ) are recognized as distinct manifolds by our approach. To test whether this partition into manifolds is related to the separation between the folded and the unfolded state we relate the partition to the fraction of native contacts Q, which can be straightforwardly estimated on each configuration of the system. Q is close to one only if the configuration is folded, while it approaches zero when the protein is unfolded. In Fig. 3 we plot the probability distribution of Q restricted to the four manifolds. We find that the vast majority of the folded configurations ( Q > 0.8 ) are assigned to the high-dimensional manifold. Conversely, the unfolded configurations ( Q ≤ 0.8 ) are most of the times assigned to one of the low-dimensional manifolds. This implies that a configuration belonging to the low dimensional manifolds is almost surely unfolded. The normalized mutual information between the manifold assignment and the folded/unfolded classification is 0.60. Thus, we can essentially identify the folded state using the intrinsic dimension, a purely topological observable unaware of any chemical detail.
ID variability in time-series from brain imaging. In the next example, we analyze a set of time-series from functional resonance imaging (fMRI) of the brain, representing the BOLD (blood oxygen-level dependent) signal of each voxel, which captures the activity a small part of the brain 34 . fMRI time-series are often projected on a lower dimension through linear projection techniques like PCA 35 , a step that assumes a uniform ID. However, the gross features of the signal (e.g., power spectrum and entropy) are often highly variable in different parts of the brain, and also non-uniformities in the ID may well be present. Here, we consider a single-subject fMRI recording containing D = 202 images collected while a subject was performing a visuomotor task 31,36 .
From the images we extract the N = 29851 time series corresponding to the BOLD signals of each voxel. Apply- www.nature.com/scientificreports/ ing Hidalgo, we find two manifolds with very different dimensions d 1 = 16.2 , d 2 = 31.9 . Again, we relate the identified manifolds to a completely independent quantity, the clustering frequency introduced in 31,32 , which measures the temporal coherence of the signal of a voxel with the signals of other voxels in the brain. Voxels with non-negligible clustering frequency ( � > 0.2 ) are likely to belong to brain areas involved in the cognitive task at hand. In Fig. 4 we show the probability distribution of restricted to the two manifolds. We find that the "task-related" voxels ( � > 0.2 ) almost invariably belong to the manifold with high dimensionality. These voxels appear concentrated in the occipital, parietal, and temporal cortex (Fig. 4 bottom), and belong to a task-relevant network of coherent activity 31 . The normalized mutual information between the manifold assignment and the task-relevant/task-irrelevant classification is 0.24; note that this value is lower than for the protein folding case, because the the low-dimensional manifold is "contaminated" by many points with low . This result finds an interesting interpretation: the subset of "relevant" voxels gives rise to patterns that are not only coherent but also characterized by a larger ID than the remainder of the voxels. On the contrary, the incoherent voxels exhibit a lower ID, hence a reduced variability, which is consistent with the fact that the corresponding time series are dominated by low-dimensional noise. Again, this feature emerges from the global topology of the data, revealed by our ID analysis, without exploiting any knowledge of the task that the subject is performing.

ID variability in financial data.
Our final example is in the realm of economics. We consider firms in the well-known Compustat database ( N = 8309 ). For each firm, we consider D = 31 balance sheet variables from the fiscal year 2016 (for details, see Supplementary Table S2). Applying Hidalgo we find four manifolds of dimensions d 1 = 5.4 , d 2 = 6.3 , d 3 = 7.0 and d 4 = 9.1 . To understand this result, we try to relate our classification with common indexes showing the type and financial stability of a firm. We start by relating our classification to the Fama-French classification 37 , which assigns each firm to one of twelve categories depending on the firm's trade. In Fig. 5(top) we separately consider firms belonging to the different Fama-French classes, and compute the fraction of firms assigned to each the four manifolds identified by Hidalgo. The two classifications are not independent, since the fractions for different Fama-French classes are highly non-uniform. More precisely, the normalized mutual information between the two classifications is 0.19, rejecting hypothesis of statistical independence (p-value < 10 −5 ). In particular, firms in the utilities and energy sector show a preference for low dimensions ( d 1 and d 2 ), while firms purchasing products (nondurables, durables, manufacturing chemicals, equipment, wholesale) are concentrated in the manifold with the highest dimension d 4 . The manifold with intrinsic dimension d 3 mostly includes firms in the financial and health care sectors. Different dimensions are not only related to the classification of the firm, but also their financial robustness. We consider the S&P quality ratings for the firms assigned to each manifold (also from Compustat; ratings are available for 2894 firms). In Fig. 5(bottom) www.nature.com/scientificreports/ we show the distribution of ratings for the different manifolds. These distributions appear to be different. We cannot predict the rating based on the manifold assignment (the normalized mutual information between the manifold assignment and the rating is 0.04), but companies with worse ratings show a preference to belong to low-dimensional manifolds: by converting ratings into numerical values scores from 1 to 8, we found a Pearson correlation of 0.22 between the local ID and the rating ( p < 10 −10 ) We suggest a possible interpretation for this phenomenon: a low ID may imply a more rigid balance structure, which may entail a higher sensitivity to market shocks which, in turn, may trigger domino effects in contagion processes. This result shows that information  www.nature.com/scientificreports/ about the S&P rating can be derived using only the topological properties of the data landscape, without any in-depth financial analysis. For example, no information on the commercial relationship between the firms or the nature of their business is used.
Comparison with other methods. We have compared our method with two state-of-the-art methods in the literature, considering the synthetic datasets as well as the protein folding dataset (for which the folded/ unfolded classification yields an approximate "ground truth"). The first method we consider is the "sparse manifold clustering and embedding" (SMCE, Ref. 19 ). The method creates a graph by connecting neighboring points, supposedly lying on the same manifold, and then uses spectral clustering on this graph to retrieve the manifolds.
As an output, it returns a manifold assignment for each point, together with an ID estimate. We resort to the implementation provided by Ehsan Elhamifar (http://khour y.neu.edu/home/eelha mi/codes .htm). For SMCE, we can compute the NMI between the manifold assignment and the ground-truth manifold label. Furthermore, we can report the estimated local ID for points with a given ground-truth assignment, identified with the ID of the manifold to which they are assigned. SMCE requires to specify the number of manifolds K as input and depends on a free parameter . To present a fair comparison, we fixed K at its ground truth value and explored different values in the range 0.01 ≤ ≤ 20 , and we report the results corresponding to the highest NMI with the ground truth. Furthermore, we repeated the estimation M = 10 times and kept the results with the highest NMI with the ground truth. The second method is the local ID (LID) estimation by Carter et al. 10 , which combines ID estimation restricted to a (large) neighborhood and local smoothing to produce an integer ID estimate for each point. We used the implementation provided by Kerstin Johnsson 38 (https ://githu b.com/kjohn sson/intri nsicD imens ion) using a neighborhood size k = 50 which is a standard value. Note that the LID estimation is deterministic, so we do not need to repeat the estimation several times. For LID, we can compute the NMI between the (integer) label given by the local ID estimate and the ground truth; moreover, we can compute the average ID, d for the points with a given ground truth assignment.
The results of the comparison are presented in Table 1.
For the examples with two manifolds, SMCE 19 is able to correctly retrieve the manifolds with high accuracy (NMI≥ 0.94 ). The estimate of the lower dimension d 2 = 4 is always correct, while the highest dimension is underestimated for d 1 ≥ 7 . Overall, SMCE performs very well (even better than Hidalgo) on the datasets with two manifolds, as the two manifolds are well separated, matching well the assumptions of the model. On the examples with five manifolds, the performance of SMCE is worse, as the method cannot correctly retrieve intersecting manifolds. In the example with five linear manifolds, SMCE cannot retrieve the manifold of dimension d 1 = 1 , which is intersecting the manifolds of dimension d 3 = 4 and d 4 = 5 . Moreover, the ID estimates are quite poor. In the example with five curved manifolds, SMCE merges the manifolds with d 4 = 5 and d 5 = 9 , and cannot retrieve the manifolds with d 1 = 1 and d 3 = 4 , which get split. Again, the dimension estimates are poor. For the protein folding data, where regions with different IDs are probably not well separated, SMCE finds a single manifold with d = 11 , and thus it is not able to detect any ID variation.
For the examples with two manifolds, the LID method 10 is generally able to correctly retrieve regions with different IDs with high accuracy (NMI≥ 0.92 ), except for the case with d 1 = 5, d 2 = 4 where results are inaccurate. The estimate of the lower dimension d 2 = 4 is always precise, while the higher dimension is always underestimated. The degree of underestimation increases with increasing d 1 . This is expected, since the ID estimates are produced by assuming a uniform density in a large neighborhood of each point, an assumption that fails in these data, especially for points on the manifold with higher dimension. Overall, LID performs quite well (comparably with Hidalgo) in separating regions with different IDs in the datasets with two manifolds, but gives worse ID estimates than Hidalgo. In the examples with five manifolds, the performance of LID is slightly worse. In the example with five linear manifolds LID merges the manifolds of dimension d 3 = 4 and d 4 = 5 , and misassigns some of their points to the manifold of dimension 1. This is because relatively large neighborhoods are used for the estimation of the local ID: this leads to a difficulty in discriminating close regions with similar ID ( d 3 = 4 and d 4 = 5 ) and to a "contamination" of results by points of the manifold with d 1 = 1 intersecting the two. In the example with five curved manifolds, LID can correctly identify the manifolds with d 2 = 2 , d 4 = 5 , and d 5 = 9 , even if it underestimates the ID in the latter two cases (high dimension, large density variations). Many points in the manifold of dimension d 3 = 4 are mis-assigned to the manifold of dimension d 1 = 1 , due to the fact that the two manifolds are highly intersecting. Finally, for the protein folding data, where the density is highly variable, LID shows a tendency for unfolded configurations to have a higher local ID than unfolded ones. However, it cannot discriminate between folded and unfolded configurations as Hidalgo. The ID of the folded configurations is highly underestimated compared to the Hidalgo estimate, probably because of density variations.
In Fig. 6 we compare the results of the three methods (Hidalgo, SMCE, and LID) for the dataset with five curved manifolds.

Discussion
The increasing availability of a large amount of data has considerably expanded the opportunities and challenges for unsupervised data analysis. Often data come in the form of a completely uncharted "point cloud" for which no model is at hand. The primary goal of the analyst is to uncover some structure within the data. For this purpose, a typical approach is dimensionality reduction, whereby the data are simplified by projecting them onto a low-dimensional space.
The appropriate intrinsic dimension (ID) of the space onto which one should project the data is not constant everywhere. In this work, we developed an algorithm (Hidalgo) to find manifolds of different IDs in the data. Applying Hidalgo, we observed large variations of the ID in datasets of diverse origin (a molecular dynamics simulation, a set of time series from brain imaging, a dataset of firm balance sheets). This finding suggests that a  www.nature.com/scientificreports/ highly non-uniform ID is not an oddity, but a rather common feature. Generally speaking, ID variations can be expected whenever the system under study can be in various "macrostates" characterized by a different number of degrees of freedom due, for instance, to differences in the constraints. As an example, the folded state the protein is able to locally explore the phase space in many independent directions, while in the unfolded state it only performs wider movements in fewer directions. In the case of companies, a financially stable company may have more degrees of freedom to adjust its balance sheet.
In the cases we have analyzed, regions characterized by different dimensions were found to host data points differing in important properties. Thus, variations of the ID within a dataset can be used to classify the data into different categories. It is remarkable that such classification is achieved by looking at a simple topological property, the local ID. Let us stress that ID-based segmentation should not be considered an alternative to clustering methods. In fact, in most cases (e.g., most classical benchmark sets for clustering) different clusters do not correspond to significantly different intrinsic dimensions -rather, they correspond to regions of high density of points within a single manifold of well-defined ID. In such cases, clusters cannot be identified as different manifolds by Hidalgo. Conversely, when the ID is variable, regions of different IDs do not necessarily correspond to clusters in the standard meaning of the word: they may or may not correspond to regions of high density of points. A typical example could be that of protein folding: while the folded configurations are quite similar to one another, and hence constitute a cluster in the traditional sense, the unfolded configurations may be very heterogeneous, hence quite far in data space and then not a "cluster" in the standard meaning of the word.
The idea that ID may vary in the same data is not new. In fact, many works have discussed the possibility of a variable ID and developed methods to estimate multiple IDs 7-18,20-22 . Our method builds on these previous contributions but is designed with the specific goal of overcoming technical limitations of other available approaches and make ID-based segmentation a general-purpose tool. Our scheme uses only the distances between the data points, and not their coordinates, which significantly enlarges its scope of applicability. Moreover, the scheme uses only the distances between a point and its q nearest neighbors, with q ≤ 5 . We thus circumvent the notoriously difficult problem of defining a globally meaningful metric 3 , only needing a consistent metric on a small local scale. Finally, Hidalgo is not hindered by density variations or curvature. For these reasons, Hidalgo is competitive with other manifold learning and variable ID estimation methods and, in particular, can yield better ID estimates and manifold reconstruction. We have compared our method with two state-of-the-art methods in the literature, the local ID method (LID 10 ), and the sparse manifold clustering and embedding (SMCE 19 ) method. Both methods show issues in the cases of intersecting manifolds and variable densities and yield worse ID estimates than Hidalgo, especially for large IDs.
Hidalgo is computationally efficient and therefore suitable for the analysis of large data sets. For example, it takes ≈ 30 mins to perform the analysis of the neuroimaging data, which includes 30000 data points, on a standard computer using a single core. Implementing the algorithm with parallel Gibbs sampling 39 may considerably reduce computing time and then yield a fully scalable method. Obviously, Hidalgo has some limitations. Some are intrinsic to the way the data are modeled. Hidalgo is not suitable to cover cases in which the ID is a continuously varying parameter 21 , or in which sparsity is so strong that points cannot be assumed to be sampled from a Figure 6. Results of other variable-ID analysis methods on topologically complex artificial data. We consider sets of points drawn from mixtures of multivariate Gaussians embedded in curved nonlinear manifolds, as detailed in Fig. 2, and compared the results of Hidalgo (a), SMCE (b), LID (c). In panel (a) we plot again, for ease of comparison, the results of Fig. 2b. In panel (b), we show the local ID estimates given by LID 10 , considering k = 50 nearest neighbors for local ID estimation and smoothing. The method assigns an integer dimension to each point: in the plot, the dimension of each point is represented by its color, according to the color bar shown. The method correctly retrieves the manifolds of dimension 5 and 9, even though the points in the manifold with dimension 5 are assigned a local ID that oscillates between 4 and 5, and points in the manifold with dimension 9 are assigned a local ID that oscillates between 7 and 8. Also, the manifold of dimension 2 is well identified. The manifolds of dimension 1 and 4, however, cannot be correctly discriminated. Points of the manifold of dimension 4 are assigned ID estimates of 1 or 3, without a clear separation of the manifolds. The NMI between the ground truth and the integer local ID is 0.77. In panel (c) we show the assignment of points as given by SMCE 19 . The manifolds of dimension 5 and 9 are merged. The manifold of dimension 2 is identified, but it is also contaminated by points from the manifold of dimension 4. SMCE cannot correctly retrieve the manifolds of dimension 1 and 4. The NMI between the ground truth and the assignment is 0.61. ID estimates obtained according to the prescription given in 19  www.nature.com/scientificreports/ continuous distribution. In particular, Hidalgo is not suitable for discrete data for which the basic assumptions of the method are violated. For example, ties in the sample could lead to null distances between neighbors, jeopardizing the computation of µ . Others are technical issues related with the estimation procedure, and, and least in principle, susceptible to improvement in refined versions of the algorithm: for instance, one may improve the estimation with suitable enhanced sampling techniques. Finally, let us point out some further implications of our work. Our findings suggest a caveat with respect to common practices of dimensionality reduction, which assume a uniform ID. In the case of significant variations, a global dimensionality reduction scheme may become inaccurate. In principle, the partition in manifolds obtained with Hidalgo may be the starting point for using standard dimensionality reduction schemes. For example, one can imagine to apply PCA 1 or Isomap 3 , or sketchmap 40 separately to each manifold. However, we point out that a feasible scheme to achieve this goal does not come as an immediate byproduct of our method. Once a manifold with given ID is identified, it is highly nontrivial to provide a suitable parameterization thereof, especially because the manifolds may be highly nonlinear, and even topologically non-trivial. How to suitably integrate our approach with a dimensionality reduction scheme remains a topic for further research. Another implication is that a simple topological invariant, the ID, can be very a powerful tool for unsupervised data analysis, lending support to current efforts at characterizing topological properties of the data 41,42 .


extfieldsofstudy:
Computer Science
Mathematics

s2fieldsofstudy:
Computer Science
Mathematics

text:
Penalized regression with multiple loss functions and selection by vote

This article considers a linear model in a high dimensional data scenario. We propose a process which uses multiple loss functions both to select relevant predictors and to estimate parameters, and study its asymptotic properties. Variable selection is conducted by a procedure called"vote", which aggregates results from penalized loss functions. Using multiple objective functions separately simplifies algorithms and allows parallel computing, which is convenient and fast. As a special example we consider a quantile regression model, which optimally combines multiple quantile levels. We show that the resulting estimators for the parameter vector are asymptotically efficient. Simulations and a data application confirm the three main advantages of our approach: (a) reducing the false discovery rate of variable selection; (b) improving the quality of parameter estimation; (c) increasing the efficiency of computation.

Introduction
Consider a linear model where Y = (Y 1 , . . . , Y n ) T is an n-dimensional vector of responses, X = (X 1 , . . . , X n ) T is an n×p design matrix of predictors with X i = (X i1 , . . . , X ip ) T for i = 1, . . . , n, ϑ = (ϑ 1 , . . . , ϑ p ) T is a p-dimensional vector of parameters, and ε = (ε 1 , . . . , ε n ) T is an n-dimensional vector of independent and identically distributed random errors, which is independent of X. We study a scenario with high dimensional data where the dimension of the predictors p = p n is allowed to be greater than the sample size n and tend to infinity as n increases. We further assume that the model is sparse, i.e. only a fraction of the predictors significantly affects the response, while the parameters of the other predictors are zero.
One possible approach to selecting the important predictors and to estimate parameters is penalized regression. Various types of penalties, such as the Lasso (Tibshirani, 1996), the smoothly clipped absolute deviation (SCAD) penalty (Fan & Li, 2001), and the adaptive Lasso (Zou, 2006), have been applied to least squares regression. Penalized quantile regression has been considered because of its robustness (Fan et al., 2014;Wang et al., 2012;Wu & Liu, 2009). In addition to these articles working with a single loss function, Zou & Yuan (2008) introduced a composite quantile regression approach, which combines multiple quantile loss functions. They used an adaptive Lasso penalty to detect sparsity in linear models with a fixed number of parameters. Each of the above loss functions only works well for certain classes of error distributions. To obtain universal optimality, Bradic et al. (2011) developed a composite quasi-likelihood function, which approximates the log-likelihood function of the random error by a weighted linear combination of convex loss functions, and adopts a weighted Lasso penalty. The use of multiple loss functions in Zou & Yuan (2008) and Bradic et al. (2011) improves the efficiency of estimation. However, it does not necessarily reduce the false discovery rate in model selection. In fact, a loss function that yields an efficient estimator for a parameter may not be optimal for variable selection. For example, in Section 5.1 of Bradic et al. (2011), the simulation results show that penalized least squares regression can have higher false discovery rates than methods using other loss functions, even though it attains the Cramér-Rao bound because the error distribution is normal. Moreover, solving a penalized combination of multiple loss functions can be computationally complex, requiring complicated algorithms. For high dimensional data, the computation becomes increasingly intensive as the number of loss functions rises (Bradic et al., 2011, Section 4.2).
To make full use of multiple loss functions and facilitate computation, this article proposes a two-step process for the linear model (1): in the first step, the "vote procedure", the relevant predictors are determined. Then, in the second step, the parameters of the selected variables are estimated. This is different from the methods above, which generate a sparse estimator in one step by minimizing a penalized objective function. Our method uses multiple loss functions to which a weighted Lasso penalty is added. This yields different sparse (preliminary) estimators for the parameter vector ϑ. If a component of ϑ is identified as nonzero by a sufficient number of models, i.e. it has received enough "votes", the corresponding predictor is included in the final model. Our approach has smaller variance than most existing methods and excludes unimportant predictors more effectively. It requires no sophisticated algorithms and allows parallel computing to reduce processing time. A further advantage is that one can use different loss functions for variable selection and for parameter estimation, which brings more flexibility.
In the next section we introduce our approach, including the vote procedure, and study its asymptotic properties. Section 3 focuses on a special example, which optimally combines multiple quantile levels, and proves it is asymptotically efficient when the number of loss functions tends to infinity. Our method is compared with other competing methods by means of simulations in Section 4. In Section 5 we illustrate our approach with a real data analysis. Section 6 concludes the article with a brief summary and a discussion of further questions. All proofs are in the Appendix.

Variable selection and parameter estimation with multiple loss functions
In the following we will, for convenience of notation, let the lower case letter c represent a generic constant. The lower case letter r denotes a vector of a proper length whose components all equal one and the lower case letter v represents a unit vector of a proper length.
For a matrix B, let λ max (B) and λ min (B) denote its maximum and minimum eigenvalues.
, B ∞ equal to the largest absolute value of the entries in B and Assume that in the model (1), the parameter vector ϑ is sparse, i.e. there exists a set Q n ⊂ {1, 2, . . . , p n } such that ϑ j = 0 for any j ∈ Q n and ϑ j = 0 for any j ∈ Q c n = {1, 2, . . . , p n }\Q n . Without loss of generality, let Q n = {1, 2, . . . , q n } for some positive sequence q n < p n . To identify the set Q n we consider K different loss functions ℓ 1 (·), . . . , ℓ K (·). A weighted Lasso penalty with weights d k1 , . . . , d kpn and a tuning parameter λ n,k , is applied to the k th loss function. Then we obtain preliminary estimators for k = 1, . . . , K, where θ = (θ 1 , . . . , θ pn ) T . For some positive integer α ≤ K, the set Q n is estimated by the vote procedure, i.e., where I(·) is the indicator function and α is a threshold. This means that the j th component ϑ j of ϑ is included in the model if it receives α or more votes, i.e. at least α of the K estimates ϑ 1j , . . . , ϑ Kj are nonzero. In Theorem 1, we will see that the choice of α does not affect the result of variable selection asymptotically. When the sample size is finite we recommend cross validation to determine α for simulations and data analysis. A similar vote procedure was employed by Meinshausen & Bühlmann (2010) to develop stability selection and by Chen & Xie (2014) to apply the split and conquer strategy to penalized regression.
Unlike these two articles, which calculate multiple estimators on subsets of data, our method obtains each preliminary estimator (2) on the whole data set. This is desirable when the sample size is is not too large. In addition, the same penalty tuning parameter is used for all estimators in Meinshausen & Bühlmann (2010), while we choose a tuning parameter λ n,k for each estimator independently.
In the above process multiple loss functions are used not only to increase the efficiency of parameter estimation by the weighted combination (5) but also to improve the result of variable selection by the vote procedure (3). For the calculation of the estimators in (2) and (4), we only need algorithms for the K single objective functions. The multiple minimization procedures can then be conducted in parallel; see Section 4 for details. The two estimation steps may use different sets of loss functions. For example, if the error distribution is thought to be normal, we can use multiple loss functions for (2) and only the quadratic loss function for (4). For simplicity of notation, in the rest of this section and the next section we assume . Except for minor differences in notation, the conclusions are exactly the same if we drop these assumptions.
Assumptions 1 and 2 regulate the loss functions in (2) and (4). Common loss functions, such as the square function and the check function, satisfy these conditions. Assumption 3 is a standard condition on the growth rate of the model size for linear models with a diverging number of parameters, which can also be found in Bradic et al. (2011) and Wang et al. (2012), among others. Assumptions 4 and 5 guarantee good behaviour of the design matrix. Assumptions 6 and 7 are imposed on the weighted Lasso penalty to ensure important predictors can be detected. Assumption 8 excludes situations where the values of nonzero parameters decay too fast. Conditions similar to Assumptions 1-7 were required in Bradic et al. (2011) for penalized regression with a weighted linear combination of loss functions, while Assumption 8 is necessary for the nonzero parameters to be identified with probability approaching one by the preliminary estimators (2) and vote procedure (3).
In Theorem 1, we first state that, with probability close to one, the preliminary estimator which is the minimizer of the penalized objective function in the set Θ n = {θ ∈ R pn : θ j = 0 for j / ∈ Q n }, for k = 1, . . . , K. This indicates that ϑ k can exclude the unimportant variables. Then we show that by aggregating multiple such preliminary estimators, i.e. ϑ 1 , . . . , ϑ K , the vote procedure (3) owns model selection consistency. This means, with probability tending to one, the procedure can recover the index set of the nonzero parameters Q n .
We now specify the optimal weights, which minimizes the asymptotic variance in Theorem 2, for the estimator in (5) and show that the limiting distribution is not changed if we replace the optimal weights by a consistent estimator.
Corollary 1 Suppose the conditions in Theorem 2 hold. Then the optimal weight vector for the weighted estimator ϑ Qn (w) in Theorem 2 is w * = (r T H −1 r) −1 (H −1 r). In addition, if w * converges to w * in probability as n → ∞, the estimator ϑ Qn ( w * ) converges in distribution as Theorems 1 and 2 establish the model selection consistency and the asymptotic normality of the estimator with arbitrary weights when multiple loss functions are used for both variable selection and parameter estimation. Corollary 1 gives the optimal weights and the asymptotic distribution of the estimator (5)

An example
A special example of the weighted estimator (5) is the estimator from a quantile regression model optimally combining multiple quantile levels, which was considered in Section 3 of Zhao & Xiao (2014) for a fixed number of parameters without sparsity. These authors used and β k is the τ k quantile of the random error ε 1 , which can be estimated along with the slope vector ϑ as an additional parameter. In this scenario, the (i, j) th component of the matrix H in Corollary 1 is where f (·) is the density function of the random error ε 1 . We show the asymptotic efficiency of ϑ under the following assumption, which regulates the error distribution.

Assumption 9
The error density f (·) is positive, twice differentiable and bounded over the is the distribution function of ε 1 . For some constant The above assumption is satisfied by most of common continuous distributions. The value of ν 3 is related to the support of the error density. For example, the constant ν 3 equals zero if the support is (−∞, ∞). When the support has the form [s 1 , s 2 ], (−∞, s 2 ] or [s 1 , ∞) for some constants s 1 < s 2 , it is easy to see that ν 3 is infinite.
The following theorem gives the limit of the asymptotic variance (r T H −1 r) −1 of the optimally weighted estimator ϑ Qn (w * ) from Corollary 1 when the number of quantiles K tends to infinity.
Theorem 3 Consider the asymptotic variance in Corollary 1 and suppose Assumption 9 holds true, then the reciprocal of that variance satisfies where ν 3 is the constant in Assumption 9.
In the above conclusion, the integral on the right-hand side is the Fisher information. Consequently, we see that (r T H −1 r) coincides with the Fisher information, i.e. we have asymptotic efficiency, when the number of quantiles tends to infinity and ν 3 equals zero. This is the case, for example, if the error distribution is normal. For error distributions with ν 3 greater than zero, the limit of (r T H −1 r) is larger than the Fisher information, i.e. the asymptotic variance becomes even smaller. This holds for irregular cases such as the uniform distribution on [−1, 1]. The above shows that the estimator ϑ is close to being asymptotically efficient if the number of quantiles is large.

Simulations
In this section we study the numerical performance of our method. We consider samples of size n = 200 throughout. We draw random vectors X 1 , . . . , X n independently from a p-dimensional multivariate normal distribution with mean zero and a variance-covariance matrix whose (i, j) th component is 0.5 |i−j| . The full model size is p = 12 or p = 400 and the nonzero parameters are (ϑ 1 , ϑ 2 , ϑ 5 ) = (3.0, 1.5, 2.0). The response vector is Y = X T ϑ + ε.
In the objective functions (2) and (4) for the preliminary and the final estimator we set K = K ′ = 9 and use the same loss function, namely the check function ℓ k (x) = ℓ ′ k (x) = (x−β k ){τ k −I(x < β k )} with τ k = k/10, k = 1, . . . , 9. We call this method "weighted quantile regression through vote" (WQR-vote). To guarantee the best performance we use an iterative scheme for the preliminary estimator ϑ k . The initial value is ϑ |θ j |} and the updates in the t th iteration are Here λ k d k (x) = λ k I(|x| ≤ λ k ) + (b − 1) −1 (bλ k − |x|) + I(|x| > λ k ) is the derivative of the SCAD penalty with b being a constant that is usally set to 3.7 (Fan & Li, 2001). We repeat Table 1: Mean numbers of correctly selected nonzero parameters (MNC) and mean numbers of incorrectly selected zero parameters (MNI) of the weighted quantile regression through vote method (WQR-vote), least absolute deviation regression (LADR), least squares regression (LSR) and composite quantile regression (CQR), and the relative efficiency (RE) of the WQR-Vote to the three competing methods for various error distributions. Higher values of relative efficiency indicate better performance of the WQR-vote in estimation. The full model size is p = 12; The abbreviation SMN stands for a scale mixture of normal distributions 0.5N(0, 6)+0.5N(0, 6×0.5 6 ); LMN is a location mixture of normal distributions 0.5N(−2, 1)+0.5N(2, 1) and DE denotes the double exponential distribution with mean 0 and variance 2.  (Zou & Li, 2008).
To solve (8) we use the quick iterative coordinate descent algorithm (Peng & Wang, 2015). We minimize the multiple objective functions in (2) and (4) in parallel by using the foreach function from the R package foreach. The tuning parameters in the penalty term and the threshold α for the vote procedure (3) are determined by minimizing prediction errors that are calculated over an independent validation set {( X i , Y i ) : i = 1, . . . , n ′ } with n ′ = 2, 000, which is generated from the distribution of (X 1 , Y 1 ). We choose the tuning parameter λ k in (8) by setting λ k = arg min a∈L where L is a fine grid and ϑ a,k is the outcome of the iterative process (8) with λ k = a. The candidate set for α is A = {⌈K/2⌉, ⌈K/2⌉ + 1, . . . , K − 1} and the criterion is α = arg min a∈A Here the parameter estimator is ϑ a,k = arg min θ∈ Θn(a) n i=1 ℓ k (Y i − X T i θ) with Θ n (a) = {θ ∈ R pn : θ j = 0 for j / ∈ Q n (a)}. The vector ξ = ( ξ 1 , . . . , ξ K ) T is a consistent estimator of the optimal weights ξ = R −1 ψ, where R is a K × K matrix with (i, j) th entry Bradic et al., 2011, Section 4.2). Recall that β k is the τ k quantile of the error distribution for k = 1, . . . , K. After obtaining the set Q(α), we construct the estimator ϑ in (5) as described in Remark 1 in Section 3. Remark 1 also explains how to estimate f (β k ) for k = 1, . . . , K.
For comparison we consider least absolute deviation regression, least squares regression and composite quantile regression with the same nine quantile levels 1/10, . . . , 9/10. The iterative penalty in (8) is also applied to the three competing methods. For each of the four estimators, three indices from 200 simulated data sets are recorded in the following tables: 1. mean number of correctly selected nonzero parameters; 2. mean number of incorrectly selected zero parameters; where ϑ oracle is the oracle version of the four respective estimators and ϑ WQR−vote is the estimator from the WQR-vote. Here "oracle" means knowing the index set Q = {1, 2, 5} of the nonzero parameters before estimating and applying no penalty.
In Table 1 (Bradic et al., 2011, Sections 3.4 and 4.2), which takes extra time. In Table 2 we present simulation results as in Table 1, but now for the high dimensional scenario with p = 400 predictors. When dealing with high dimensional data, the WQR-vote still yields the smallest numbers of incorrect selections for all of the cases and the lowest mean squared errors of estimation for most of the cases. In the 200 simulations with normal errors the average time required for the WQR-vote and the composite quantile regression is 27.12 seconds and 106.41 seconds, respectively, when both methods use the nine quantile levels. The advantage of adopting parallel computing in the WQR-vote procedure is obvious.

A data application
In this section we analyze a microarray dataset from Scheetz et al. (2006), which is available at https://www.ncbi.nlm.nih.gov/geo/geo2r/?acc=GSE5680. The dataset contains the gene expression values of 31,042 probes on 120 rats. We are interested in how the expression of TRIM32, which is related to human hereditary diseases of the retina and corresponding to probe 1389163 at, depends on that of other genes. To exclude genes without sufficient variability, we first remove probes whose maximum among the 120 rats is less than the 25 th percentile of all the expression values or whose range among the 120 rats is less than 1. We then sort the remaining 18,984 probes by the absolute values of their correlation coefficients with the response, 1389163 at. The top 300 probes are used as predictors in the anlaysis.
To identify important predictors by the vote procedure (3), we set K = 9 and ℓ k (x) = x{k/10 − I(x < β k )} in the objective function (2), where β k is the k/10 quantile of the error distribution and can be estimated as an extra parameter. Then three different estimators are computed based on one loss function, i.e. K ′ = 1 in (4): the square function, the absolute value function and the composite check function ℓ ′ 1 (x) = 9 m=1 x{m/10 − I(x < β m )}. For comparison, the data are also analyzed by penalized regression using each of the above three loss functions. The iterative penalty (8) is applied to all methods.
We first use the entire dataset to fit models. Then the dataset is randomly divided into a training set of 80 observations and a validation set of 40 observations. Models are fitted with the training set and prediction errors are calculated by the loss functions on the validation set. Based on five-fold cross validation, we choose the tuning parameters in the penalty and the threshold α in (3) by the criteria stated in Section 4. This is repeated 50 times. Table 3 gives the sizes of the models that are selected by the vote procedure and by the three competing penalized regression approaches. The left panel provides the sizes that are obtained using all data. The first column of the right panel lists the means and, in parentheses, the standard deviations of the model sizes that are obtained using the 50 randomly generated partitions. The top half of the second column provides the prediction errors of the parameter estimates that are obtained in the second step of our method, i.e. after model selection by the vote procedure, using least absolute deviation regression, least Table 3: Sizes of selected subsets based on all data and on the 50 randomly generated partitions. We consider least absolute deviation regression (LADR), least squares regression (LSR) and composite quantile regression (CQR). The term LADR-Vote denotes the LADR appoach (without penalty) after variable selection through the vote procedure; LSR-Vote and CQR-Vote are defined analogously. Among all methods, the vote method generates the smallest models in the situations of both all data and random partition. In addition to achieving more sparsity, the submodel selected by the vote method yields a smaller mean prediction error compared with that selected by the penalized regression approach, when the same loss function is used to estimate the parameters. This confirms the superiority of the vote method in variable selection. Furthermore, this analysis illustrates the flexibility of our approach from employing different loss functions for selection and estimation. One may also apply the method optimally combining multiple quantile levels described in Section 3 to the data. We do not consider it here because the competing methods use different loss functions for estimation. The prediction errors are therefore not directly comparable.

Conclusion and discussion
We have developed a process that uses multiple loss functions separately to analyze linear models in the high dimensional data situation. Our approach has three notable advantages: (a) it lowers the false discovery rate of variable selection by using our newly-developed vote procedure; (b) it improves the quality of parameter estimation by combining results from multiple loss functions; (c) it increases the speed of computation by adopting parallel computing.
A specific instance of our approach, which optimally combines multiple quantile levels, achieves asymptotic efficiency of parameter estimation under mild conditions.
In practical applications some loss functions may be more relevant for model selection than others. Therefore a weighted version of the variable selector (3), namely with a nonnegative weight vector w = (w 1 , . . . , w K ) T , may improve our vote procedure, which uses uniform weights w k = 1 for k = 1, . . . , K. Specifying and estimating the weight vector w may be data-driven and vary from case to case. However, using uniform weights makes the vote procedure easier to implement. According to the results of Sections 4 and 5, this suffices to improve on competing methods with respect to variable selection.
The equations (12) and (13) gurantee the conditions (27) and (28) of Lemma 1 in Bradic et al. (2011) are satisfied, which implies that ϑ o k is the unique global minimizer of the objective function in (2) on Γ n,k . This combined with (10), the definition of ϑ k in (2) and Assumption 6 implies This gives the first conclusion of the theorem. The equation (14) and the definition of ϑ o k in (6) further yield Moreover, we know that, with probability tending to one, In the above the first two steps use (15) and (14) and the last step follows from (11). Then we have with ϑ kQn = ( ϑ k1 , . . . , ϑ kqn ) T , where the convergence follows from (16) and Assumption 8.
Let w * be a consistent estimator of w * . Then The last step uses the fact that |v T (X T X) 1/2 ( ϑ kQn − ϑ Qn )| = O p (1) for 1 ≤ k ≤ K, which holds by Theorem 2, and the consistency of w * . Combining (23) and (24) yields Proof of Theorem 3: The i th diagonal element of the K × K matrix H −1 is 2(K + 1){f (β i )} 2 for i = 1, . . . , K. The (i, i + 1) th and (i + 1, i) th entries are −(K + 1)f (β i )f (β i+1 ) for i = 1, . . . , K − 1, and the other entries are zero. Hence we have where The sixth step in the above uses the Cauchy-Schwarz inequality and the last step follows from Assumption 9. Then, using (25), we obtain The last step follows from Assumption 9, the equation (26) and the fact that τ 1 = (K + 1) −1 → 0 as K → ∞. This completes the proof.