Highly Scalable and Provably Accurate Classification in Poincare Balls

Many high-dimensional and large-volume data sets of practical relevance have hierarchical structures induced by trees, graphs or time series. Such data sets are hard to process in Euclidean spaces and one often seeks low-dimensional embeddings in other space forms to perform required learning tasks. For hierarchical data, the space of choice is a hyperbolic space since it guarantees low-distortion embeddings for tree-like structures. Unfortunately, the geometry of hyperbolic spaces has properties not encountered in Euclidean spaces that pose challenges when trying to rigorously analyze algorithmic solutions. Here, for the first time, we establish a unified framework for learning scalable and simple hyperbolic linear classifiers with provable performance guarantees. The gist of our approach is to focus on Poincare ball models and formulate the classification problems using tangent space formalisms. Our results include a new hyperbolic and second-order perceptron algorithm as well as an efficient and highly accurate convex optimization setup for hyperbolic support vector machine classifiers. All algorithms provably converge and are highly scalable as they have complexities comparable to those of their Euclidean counterparts. Their performance accuracies on synthetic data sets comprising millions of points, as well as on complex real-world data sets such as single-cell RNA-seq expression measurements, CIFAR10, Fashion-MNIST and mini-ImageNet.

Conflict-Free Four-Dimensional Path Planning for Urban Air Mobility Considering Airspace Occupations

Urban air mobility (UAM) has attracted the attention of aircraft manufacturers, air navigation service providers and governments in recent years. Preventing the conflict among urban aircraft is crucial to UAM traffic safety, which is a key in enabling large scale UAM operation. Pre-flight conflict-free path planning can provide a strategic layer in the maintenance of safety performance, thus becomes an important element in UAM. This paper aims at tackling conflict-free path planning problem for UAM operation with a consideration of four-dimensional airspace management. In the first place, we introduced and extended a four-dimensional airspace management concept, AirMatrix. On the basis of AirMatrix, we formulated the shortest flight time path planning problem considering resolution of conflicts with both static and dynamic obstacles. A Conflict-Free A-Star algorithm was developed for planning four-dimensional paths based on first-come-first-served scheme. The algorithm contains a novel design of heuristic function as well as a conflict detection and resolution strategy. Numerical experiment was carried out in Jurong East area in Singapore, and the results show that the algorithm can generate paths resolving a significant number of potential conflicts in airspace utilization, with acceptable computational time and flight delay. The contributions of this study provide references for stakeholders to support the development of UAM.

Disentangled Implicit Shape and Pose Learning for Scalable 6D Pose Estimation

6D pose estimation of rigid objects from a single RGB image has seen tremendous improvements recently by using deep learning to combat complex real-world variations, but a majority of methods build models on the per-object level, failing to scale to multiple objects simultaneously. In this paper, we present a novel approach for scalable 6D pose estimation, by self-supervised learning on synthetic data of multiple objects using a single autoencoder. To handle multiple objects and generalize to unseen objects, we disentangle the latent object shape and pose representations, so that the latent shape space models shape similarities, and the latent pose code is used for rotation retrieval by comparison with canonical rotations. To encourage shape space construction, we apply contrastive metric learning and enable the processing of unseen objects by referring to similar training objects. The different symmetries across objects induce inconsistent latent pose spaces, which we capture with a conditioned block producing shape-dependent pose codebooks by re-entangling shape and pose representations. We test our method on two multi-object benchmarks with real data, T-LESS and NOCS REAL275, and show it outperforms existing RGB-based methods in terms of pose estimation accuracy and generalization.

A new theorem on quadratic residues modulo primes

Let $p>3$ be a prime, and let $(frac{cdot}p)$ be the Legendre symbol. Let $binmathbb Z$ and $varepsilonin{pm 1}$. We mainly prove that $$left|left{N_p(a,b): 1<a<p text{and} left(frac apright)=varepsilonright}right|=frac{3-(frac{-1}p)}2,$$ where $N_p(a,b)$ is the number of positive integers $x<p/2$ with ${x^2+b}_p>{ax^2+b}_p$, and ${m}_p$ with $minmathbb{Z}$ is the least nonnegative residue of $m$ modulo $p$.

Third Party Risk Modelling and Assessment for Safe UAV Path Planning in Metropolitan Environments

Various applications of advanced air mobility (AAM) in urban environments facilitate our daily life and public services. As one of the key issues of realizing these applications autonomously, path planning problem has been studied with main objectives on minimizing travel distance, flight time and energy cost. However, AAM operations in metropolitan areas bring safety and society issues. Because most of AAM aircraft are unmanned aerial vehicles (UAVs) and they may fail to operate resulting in fatality risk, property damage risk and societal impacts (noise and privacy) to the public. To quantitatively assess these risks and mitigate them in planning phase, this paper proposes an integrated risk assessment model and develops a hybrid algorithm to solve the risk-based 3D path planning problem. The integrated risk assessment method considers probability and severity models of UAV impact ground people and vehicle. By introducing gravity model, the population density and traffic density are estimated in a finer scale, which enables more accurate risk assessment. The 3D risk-based path planning problem is first formulated as a special minimum cost flow problem. Then, a hybrid estimation of distribution algorithm (EDA) and risk-based A* (named as EDA-RA*) algorithm is proposed to solve the problem. To improve computational efficiency, k-means clustering method is incorporated into EDA-RA* to provide both global and local search heuristic information, which formed the EDA and fast risk-based A* algorithm we call EDA-FRA*. Case study results show that the risk assessment model can capture high risk areas and the generated risk map enables safe UAV path planning in urban complex environments.

You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks

Hypergraphs are used to model higher-order interactions amongst agents and there exist many practically relevant instances of hypergraph datasets. To enable efficient processing of hypergraph-structured data, several hypergraph neural network platforms have been proposed for learning hypergraph properties and structure, with a special focus on node classification. However, almost all existing methods use heuristic propagation rules and offer suboptimal performance on many datasets. We propose AllSet, a new hypergraph neural network paradigm that represents a highly general framework for (hyper)graph neural networks and for the first time implements hypergraph neural network layers as compositions of two multiset functions that can be efficiently learned for each task and each dataset. Furthermore, AllSet draws on new connections between hypergraph neural networks and recent advances in deep learning of multiset functions. In particular, the proposed architecture utilizes Deep Sets and Set Transformer architectures that allow for significant modeling flexibility and offer high expressive power. To evaluate the performance of AllSet, we conduct the most extensive experiments to date involving ten known benchmarking datasets and three newly curated datasets that represent significant challenges for hypergraph node classification. The results demonstrate that AllSet has the unique ability to consistently either match or outperform all other hypergraph neural networks across the tested datasets. Our implementation and dataset will be released upon acceptance.

CRC-Aided List Decoding of Convolutional Codes in the Short Blocklength Regime

This paper identifies convolutional codes (CCs) used in conjunction with a CC-specific cyclic redundancy check (CRC) code as a promising paradigm for short blocklength codes. The resulting CRC-CC concatenated code naturally permits the use of the serial list Viterbi decoding (SLVD) to achieve maximum-likelihood decoding. The CC of interest is of rate-$1/omega$ and is either zero-terminated (ZT) or tail-biting (TB). For CRC-CC concatenated code designs, we show how to find the optimal CRC polynomial for a given ZTCC or TBCC. Our complexity analysis reveals that SLVD decoding complexity is a function of the terminating list rank, which converges to one at high SNR. This behavior allows the performance gains of SLVD to be achieved with a small increase in average complexity at the SNR operating point of interest. With a sufficiently large CC constraint length, the performance of CRC-CC concatenated code under SLVD approaches the random-coding union (RCU) bound as the CRC size is increased while average decoding complexity does not increase significantly. TB encoding further reduces the backoff from the RCU bound by avoiding the termination overhead. As a result, several CRC-TBCC codes outperform the RCU bound at moderate SNR values while permitting decoding with relatively low complexity.

Unsupervised Shape Completion via Deep Prior in the Neural Tangent Kernel Perspective

We present a novel approach for completing and reconstructing 3D shapes from incomplete scanned data by using deep neural networks. Rather than being trained on supervised completion tasks and applied on a testing shape, the network is optimized from scratch on the single testing shape, to fully adapt to the shape and complete the missing data using contextual guidance from the known regions. The ability to complete missing data by an untrained neural network is usually referred to as the deep prior. In this paper, we interpret the deep prior from a neural tangent kernel (NTK) perspective and show that the completed shape patches by the trained CNN are naturally similar to existing patches, as they are proximate in the kernel feature space induced by NTK. The interpretation allows us to design more efficient network structures and learning mechanisms for the shape completion and reconstruction task. Being more aware of structural regularities than both traditional and other unsupervised learning-based reconstruction methods, our approach completes large missing regions with plausible shapes and complements supervised learning-based methods that use database priors by requiring no extra training data set and showing flexible adaptation to a particular shape instance.

FESTA: Flow Estimation via Spatial-Temporal Attention for Scene Point Clouds

Scene flow depicts the dynamics of a 3D scene, which is critical for various applications such as autonomous driving, robot navigation, AR/VR, etc. Conventionally, scene flow is estimated from dense/regular RGB video frames. With the development of depth-sensing technologies, precise 3D measurements are available via point clouds which have sparked new research in 3D scene flow. Nevertheless, it remains challenging to extract scene flow from point clouds due to the sparsity and irregularity in typical point cloud sampling patterns. One major issue related to irregular sampling is identified as the randomness during point set abstraction/feature extraction -- an elementary process in many flow estimation scenarios. A novel Spatial Abstraction with Attention (SA^2) layer is accordingly proposed to alleviate the unstable abstraction problem. Moreover, a Temporal Abstraction with Attention (TA^2) layer is proposed to rectify attention in temporal domain, leading to benefits with motions scaled in a larger range. Extensive analysis and experiments verified the motivation and significant performance gains of our method, dubbed as Flow Estimation via Spatial-Temporal Attention (FESTA), when compared to several state-of-the-art benchmarks of scene flow estimation.

Deep Implicit Moving Least-Squares Functions for 3D Reconstruction

Point set is a flexible and lightweight representation widely used for 3D deep learning. However, their discrete nature prevents them from representing continuous and fine geometry, posing a major issue for learning-based shape generation. In this work, we turn the discrete point sets into smooth surfaces by introducing the well-known implicit moving least-squares (IMLS) surface formulation, which naturally defines locally implicit functions on point sets. We incorporate IMLS surface generation into deep neural networks for inheriting both the flexibility of point sets and the high quality of implicit surfaces. Our IMLSNet predicts an octree structure as a scaffold for generating MLS points where needed and characterizes shape geometry with learned local priors. Furthermore, our implicit function evaluation is independent of the neural network once the MLS points are predicted, thus enabling fast runtime evaluation. Our experiments on 3D object reconstruction demonstrate that IMLSNets outperform state-of-the-art learning-based methods in terms of reconstruction quality and computational efficiency. Extensive ablation tests also validate our network design and loss functions.