Tensor-Train Point Cloud Compression and Efficient Approximate Nearest Neighbor Search

First of all, Thank you for insightful comments and constructive feedback. I truly believe that your suggestions will contribute significantly to making this work better!

1. Operator reshaping resembles similar operators from the numpy or torch. In Equation 8, we choose $K$ closest first-level centroids. $q$ here is a query vector, and $y_i$ are different first-level centroids. operator K-argmin will choose such $K$ indices $i_1, i_2, …, i_K$, that corresponding vectors $y_{i_1}, …, y_{i_k}$ are closest to $q$ among all $y_i$ and the resulting set of indices is stored in $J_1$. Then, in the following equation, the same procedure repeats with the second-level centroids, but instead of using all second-level centroids, only those with the first index from $J_1$ are used. Because of this filtration, it is not an exhaustive search but a fast, approximate search.

2. By "straightforward," we meant that we could just use an approximate, compressed point cloud in place of the original point cloud. So previously, the OOD decision was performed as follows: for query vector q, calculate the distance to the closest point in the training point cloud. If this distance is greater than some threshold, q is an out-of-distribution sample. Otherwise, it is a normal sample. If the approximated compressed point cloud is perfect, then it is sampled from the same distribution as the original point cloud, and thus we can just calculate the distance from $q$ to the compressed point cloud.

   This is in contrast with ANN, where we cannot use even perfectly trained compressed point clouds. As it does not contain vectors from the original database, the nearest neighbor point from the compressed point cloud will be a meaningless, newly generated vector without any correspondence with the original database.

3. If the TT point cloud represents a tensor of shape $[N_1, N_2, …, N_k, D]$, then first-level centroids are arranged in a tensor of shape $[N_1, D]$ that is a mean value across $N_2, … N_k$ dimensions. Second-level centroids are arranged in tensor of shape $[N_1, N_2, D]$ that are mean values across $N_3, … N_k$. And so on.

4. We can use these centroids in algorithms because the TT structure of our point cloud allows for a very fast calculation of any level centroid with any indices without explicitly instantiating any tensors in memory. And that is used in our algorithms to achieve good asymptotics.

5. Usage of higher-order TTs is associated with the following difficulties: first of all, more cores in TT will give a significant improvement only in larger-scale point clouds. Second of all, surely the more cores in the TT representation, the more unstable and hard-to-train the whole construction may become. But in this paper, we did not have the computational ability to process larger datasets (for example, we performed our experiments only on the 10M subset of the Deep1B dataset). And the point clouds in the MVTecAD benchmark are even smaller. So there was no need to use more than 3 cores. But nevertheless, it is possible to use higher-order TTs, and this is an important future work direction.

Thank you for insightful comments and constructive feedback. I truly believe that your suggestions will contribute significantly to making this work better.

Sliced Wasserstein loss alone is good enough to approximately fit the cloud in terms of overall shape, scale, location, and form. So visually, the two-dimensional PCA projections of the training cloud and the approximated cloud are very similar. But it has very poor actual task-dependent quality metrics (like quality of OOD detection or recall for ANN search). That means that Sliced Wasserstein cannot achieve precision on smaller, point-to-point scales at the end of the optimization process on its own.

Nearest Neighbor Loss, on the other hand, cannot be applied alone from the beginning of the optimization, as the nearest neighbor correspondence would be degenerate: only a few points from the TT point cloud will have non-empty clusters. But when used together with Sliced Wasserstein in the latter phases of the training, when two clouds are already very similar, Nearest Neighbor loss makes up for the lack of Sliced Wasserstein precision on smaller scales. That significantly improves the final metrics.

1. First of all, thank you for insightful comments and constructive feedback. I truly believe that your suggestions will contribute significantly to making this work better.

   The main difference between classical tensor compressions based on Tensor-Train representation and our approach is exactly the independence of the enumeration of samples in the dataset. The standard way of TT application requires constructing the actual compressible tensor, thus fixing a map from the multiindex to the values of the tensor. If a compressible tensor is built explicitly, then this map is an actual multidimensional tensor. If a tensor is built implicitly, it can be determined by some function $(i_1, …, i_k) \rightarrow f(i_1, …, i_k)$.

   This fixed map (fixed order of the vectors in the point cloud) will give poor results for our method. And thus we proposed a probabilistic interpretation of the TT point cloud optimization and then we proposed to use Wasserstein Distance. And this approach allows training TT parameters without predefined ordering of vectors in the database. One can think about it as an automatic implicit adjustment of the points enumeration right during the training procedure.

   The ability of training TT to compress point clouds, without predefined enumeration of points in the point cloud, is our main contribution.

2. Indeed, we did not use the full Deep1B dataset to solve approximate nearest neighbor queries. The reason for this was the lack of computational possibilities to process the full Deep1B dataset. Instead we performed our tests on the 10M subset of this dataset. The comparison with (G)NO-IMI method was performed on the same 10M subset: we retrained this method by ourselves, so we did not use values from the original paper, so the comparison was fair. Although we absolutely agree that for the more comprehensive comparison it is required to perform tests on the full Deep1B dataset.

Thank you for your insightful comments and constructive feedback. I truly believe that your suggestions will contribute significantly to making this work better!

1. Equation 19 estimates the number of points to process during the search without prior knowledge about the distribution of the query vector $q$. Thus, if we are given some query vector and the closest centroid is the $i$-th one with probability $p_i$, then we will process size($i$-th centroid) points with probability $p_i$. Because of that, the estimation is $\sum_i p_i N_i$.
2. TT can outperform clustering methods. For example, (G)NO-IMI outperforms KMeans for ANN search as index structure, and we showed that the TT point cloud is able to build a better index structure than (G)NO-IMI. But deeper research on the possibility of using the TT point cloud as a clustering method for other use cases is an important future work direction.
3. For the sizes of training datasets and TT point clouds used in the paper, training times are quite small and vary by about 10 minutes for the MVTec Ad subsets and 30 minutes for the 10M subset of the Deep1B considered in the paper. We will add comparisons to the main text. Thank you very much for the suggestion!