Xiaodong Wang

Shengming Yin, Chenfei Wu, Huan Yang et al. · microsoft-research, pku

In this paper, we propose NUWA-XL, a novel Diffusion over Diffusion architecture for eXtremely Long video generation. Most current work generates long videos segment by segment sequentially, which normally leads to the gap between training on short videos and inferring long videos, and the sequential generation is inefficient. Instead, our approach adopts a ``coarse-to-fine'' process, in which the video can be generated in parallel at the same granularity. A global diffusion model is applied to generate the keyframes across the entire time range, and then local diffusion models recursively fill in the content between nearby frames. This simple yet effective strategy allows us to directly train on long videos (3376 frames) to reduce the training-inference gap, and makes it possible to generate all segments in parallel. To evaluate our model, we build FlintstonesHD dataset, a new benchmark for long video generation. Experiments show that our model not only generates high-quality long videos with both global and local coherence, but also decreases the average inference time from 7.55min to 26s (by 94.26\%) at the same hardware setting when generating 1024 frames. The homepage link is \url{https://msra-nuwa.azurewebsites.net/}

Le Zheng, Marco Lops, Yonina C. Eldar et al.

Increased amounts of bandwidth are required to guarantee both high-quality/high-rate wireless services (4G and 5G) and reliable sensing capabilities such as automotive radar, air traffic control, earth geophysical monitoring and security applications. Therefore, co-existence between radar and communication systems using overlapping bandwidths has been a primary investigation field in recent years. Various signal processing techniques such as interference mitigation, pre-coding or spatial separation, and waveform design allow both radar and communications to share the spectrum. This article reviews recent work on co-existence between radar and communication systems, including signal models, waveform design and signal processing techniques. Our goal is to survey contributions in this area in order to provide a primary starting point for new researchers interested in these problems.

Minheng Ni, Chenfei Wu, Xiaodong Wang et al. · pku

Avoiding synthesizing specific visual concepts is an essential challenge in responsible visual synthesis. However, the visual concept that needs to be avoided for responsible visual synthesis tends to be diverse, depending on the region, context, and usage scenarios. In this work, we formalize a new task, Open-vocabulary Responsible Visual Synthesis (ORES), where the synthesis model is able to avoid forbidden visual concepts while allowing users to input any desired content. To address this problem, we present a Two-stage Intervention (TIN) framework. By introducing 1) rewriting with learnable instruction through a large-scale language model (LLM) and 2) synthesizing with prompt intervention on a diffusion synthesis model, it can effectively synthesize images avoiding any concepts but following the user's query as much as possible. To evaluate on ORES, we provide a publicly available dataset, baseline models, and benchmark. Experimental results demonstrate the effectiveness of our method in reducing risks of image generation. Our work highlights the potential of LLMs in responsible visual synthesis. Our code and dataset is public available.

Ming Zhu, Xiao-Yang Liu, Xiaodong Wang

Public vehicle (PV) systems are promising transportation systems for future smart cities which provide dynamic ride-sharing services according to passengers' requests. PVs are driverless/self-driving electric vehicles which require frequent recharging from smart grids. For such systems, the challenge lies in both the efficient scheduling scheme to satisfy transportation demands with service guarantee and the cost-effective charging strategy under the real-time electricity pricing. In this paper, we study the joint transportation and charging scheduling for PV systems to balance the transportation and charging demands, ensuring the long-term operation. We adopt a cake cutting game model to capture the interactions among PV groups, the cloud and smart grids. The cloud announces strategies to coordinate the allocation of transportation and energy resources among PV groups. All the PV groups try to maximize their joint transportation and charging utilities. We propose an algorithm to obtain the unique normalized Nash equilibrium point for this problem. Simulations are performed to confirm the effects of our scheme under the real taxi and power grid data sets of New York City. Our results show that our scheme achieves almost the same transportation performance compared with a heuristic scheme, namely, transportation with greedy charging; however, the average energy price of the proposed scheme is 10.86% lower than the latter one.

Xiao-Yang Liu, Xiaodong Wang

The big data era is swamping areas including data analysis, machine/deep learning, signal processing, statistics, scientific computing, and cloud computing. The multidimensional feature and huge volume of big data put urgent requirements to the development of multilinear modeling tools and efficient algorithms. In this paper, we build a novel multilinear tensor space that supports useful algorithms such as SVD and QR, while generalizing the matrix space to fourth-order tensors was believed to be challenging. Specifically, given any multidimensional discrete transform, we show that fourth-order tensors are bilinear operators on a space of matrices. First, we take a transform-based approach to construct a new tensor space by defining a new multiplication operation and tensor products, and accordingly the analogous concepts: identity, inverse, transpose, linear combinations, and orthogonality. Secondly, we define the $\mathcal{L}$-SVD for fourth-order tensors and present an efficient algorithm, where the tensor case requires a stronger condition for unique decomposition than the matrix case. Thirdly, we define the tensor $\mathcal{L}$-QR decomposition and propose a Householder QR algorithm to avoid the catastrophic cancellation problem associated with the conventional Gram-Schmidt process. Finally, we validate our schemes on video compression and one-shot face recognition. For video compression, compared with the existing tSVD, the proposed $\mathcal{L}$-SVD achieves $3\sim 10$dB gains in RSE, while the running time is reduced by about $50\%$ and $87.5\%$, respectively. For one-shot face recognition, the recognition rate is increased by about $10\% \sim 20\%$.

Amirhossein Taherpour, Xiaodong Wang

Cross-chain settlement must preserve safety across heterogeneous ledgers while tolerating delayed computation, Byzantine participants, and adversarial transaction issuance. This paper presents SPID-Chain, an adapter-compatible settlement architecture for escrow-backed fungible transfers across programmable blockchains. SPID-Chain maintains settlement state through persistent Polar-coded fragments, validates candidate state transitions using hidden linear verification checks, and records certified transfers in a weighted directed acyclic graph (DAG). The design separates native-chain finality from cross-chain settlement: source-chain finality establishes an immutable reservation, whereas weighted DAG confirmation determines when the corresponding destination credit becomes executable. We derive an exact recovery-time distribution for heterogeneous coded workers, a verification-soundness bound for Byzantine responses, and an exact weighted-quorum condition for conflicting-block safety. These components are coupled in a cross-layer stability theorem showing how the coded-validation completion probability determines the effective honest issuance rate and, consequently, the stable adversarial-load region of the settlement DAG. We further establish an end-to-end settlement guarantee covering balance non-negativity, asset conservation, conflict exclusion, replay protection, coded-state consistency, and finite expected lock-to-release latency under the stated liveness conditions. Prototype-assisted simulations indicate that coded validation reduces sensitivity to stragglers, improves validation and confirmation throughput under heterogeneous delays, and produces the predicted transition between stable and unstable DAG operation. The resulting framework provides a verifiable and analytically grounded settlement layer without modifying the native consensus protocol of participating chains.

Peijie Dong, Xin Niu, Zhiliang Tian et al.

Practical networks for edge devices adopt shallow depth and small convolutional kernels to save memory and computational cost, which leads to a restricted receptive field. Conventional efficient learning methods focus on lightweight convolution designs, ignoring the role of the receptive field in neural network design. In this paper, we propose the Meta-Pooling framework to make the receptive field learnable for a lightweight network, which consists of parameterized pooling-based operations. Specifically, we introduce a parameterized spatial enhancer, which is composed of pooling operations to provide versatile receptive fields for each layer of a lightweight model. Then, we present a Progressive Meta-Pooling Learning (PMPL) strategy for the parameterized spatial enhancer to acquire a suitable receptive field size. The results on the ImageNet dataset demonstrate that MobileNetV2 using Meta-Pooling achieves top1 accuracy of 74.6\%, which outperforms MobileNetV2 by 2.3\%.

Le Zheng, Xiaodong Wang

Feature aided tracking can often yield improved tracking performance over the standard multiple target tracking (MTT) algorithms with only kinematic measurements. However, in many applications, the feature signal of the targets consists of sparse Fourier-domain signals. It changes quickly and nonlinearly in the time domain, and the feature measurements are corrupted by missed detections and mis-associations. These two factors make it hard to extract the feature information to be used in MTT. In this paper, we develop a feature-aided nearest neighbour joint probabilistic data association filter (NN-JPDAF) for joint MTT and feature extraction in dense target environments. To estimate the rapidly varying feature signal from incomplete and corrupted measurements, we use the atomic norm constraint to formulate the sparsity of feature signal and use the $\ell_1$-norm to formulate the sparsity of the corruption induced by mis-associations. Based on the sparse representation, the feature signal are estimated by solving a semidefinite program (SDP) which is convex. We also provide an iterative method for solving this SDP via the alternating direction method of multipliers (ADMM) where each iteration involves closed-form computation. With the estimated feature signal, re-filtering is performed to estimate the kinematic states of the targets, where the association makes use of both kinematic and feature information. Simulation results are presented to illustrate the performance of the proposed algorithm in a radar application.

Xiaodong Wang, Junbao Zhuo, Shuhao Cui et al.

Semi-supervised domain adaptation (SSDA) aims to solve tasks in target domain by utilizing transferable information learned from the available source domain and a few labeled target data. However, source data is not always accessible in practical scenarios, which restricts the application of SSDA in real world circumstances. In this paper, we propose a novel task named Semi-supervised Source Hypothesis Transfer (SSHT), which performs domain adaptation based on source trained model, to generalize well in target domain with a few supervisions. In SSHT, we are facing two challenges: (1) The insufficient labeled target data may result in target features near the decision boundary, with the increased risk of mis-classification; (2) The data are usually imbalanced in source domain, so the model trained with these data is biased. The biased model is prone to categorize samples of minority categories into majority ones, resulting in low prediction diversity. To tackle the above issues, we propose Consistency and Diversity Learning (CDL), a simple but effective framework for SSHT by facilitating prediction consistency between two randomly augmented unlabeled data and maintaining the prediction diversity when adapting model to target domain. Encouraging consistency regularization brings difficulty to memorize the few labeled target data and thus enhances the generalization ability of the learned model. We further integrate Batch Nuclear-norm Maximization into our method to enhance the discriminability and diversity. Experimental results show that our method outperforms existing SSDA methods and unsupervised model adaptation methods on DomainNet, Office-Home and Office-31 datasets. The code is available at https://github.com/Wang-xd1899/SSHT.

Udit Gupta, Carole-Jean Wu, Xiaodong Wang et al.

The widespread application of deep learning has changed the landscape of computation in the data center. In particular, personalized recommendation for content ranking is now largely accomplished leveraging deep neural networks. However, despite the importance of these models and the amount of compute cycles they consume, relatively little research attention has been devoted to systems for recommendation. To facilitate research and to advance the understanding of these workloads, this paper presents a set of real-world, production-scale DNNs for personalized recommendation coupled with relevant performance metrics for evaluation. In addition to releasing a set of open-source workloads, we conduct in-depth analysis that underpins future system design and optimization for at-scale recommendation: Inference latency varies by 60% across three Intel server generations, batching and co-location of inferences can drastically improve latency-bounded throughput, and the diverse composition of recommendation models leads to different optimization strategies.

Yubo Zhang, Jeremy Johnston, Xiaodong Wang

We develop an end-to-end deep learning framework for downlink beamforming in large-scale sparse MIMO channels. The core is a deep EDN architecture with three modules: (i) an encoder NN, deployed at each user end, that compresses estimated downlink channels into low-dimensional latent vectors. The latent vector from each user is compressed and then fed back to the BS. (ii) a beamformer decoder NN at the BS that maps recovered latent vectors to beamformers, and (iii) a channel decoder NN at the BS that reconstructs downlink channels from recovered latent vectors to further refine the beamformers. The training of EDN leverages two key strategies: (a) semi-amortized learning, where the beamformer decoder NN contains an analytical gradient ascent during both training and inference stages, and (b) knowledge distillation, where the loss function consists of a supervised term and an unsupervised term, and starting from supervised training with MMSE beamformers, over the epochs, the model training gradually shifts toward unsupervised using the sum-rate objective. The proposed EDN beamforming framework is extended to both far-field and near-field hybrid beamforming scenarios. Extensive simulations validate its effectiveness under diverse network and channel conditions.

Yinchuan Li, Guangchen Lan, Xiaodong Wang

We propose a tensor generalized approximate message passing (TeG-AMP) algorithm for low-rank tensor inference, which can be used to solve tensor completion and decomposition problems. We derive TeG-AMP algorithm as an approximation of the sum-product belief propagation algorithm in high dimensions where the central limit theorem and Taylor series approximations are applicable. As TeG-AMP is developed based on a general TR decomposition model, it can be directly applied to many low-rank tensor types. Moreover, our TeG-AMP can be simplified based on the CP decomposition model and a tensor simplified AMP is proposed for low CP-rank tensor inference problems. Experimental results demonstrate that the proposed methods significantly improve recovery performances since it takes full advantage of tensor structures.

Fushing Hsieh, Xiaodong Wang

Under any Multiclass Classification (MCC) setting defined by a collection of labeled point-cloud specified by a feature-set, we extract only stochastic partial orderings from all possible triplets of point-cloud without explicitly measuring the three cloud-to-cloud distances. We demonstrate that such a collective of partial ordering can efficiently compute a label embedding tree geometry on the Label-space. This tree in turn gives rise to a predictive graph, or a network with precisely weighted linkages. Such two multiscale geometries are taken as the coarse scale information content of MCC. They indeed jointly shed lights on explainable knowledge on why and how labeling comes about and facilitates error-free prediction with potential multiple candidate labels supported by data. For revealing within-label heterogeneity, we further undergo labeling naturally found clusters within each point-cloud, and likewise derive multiscale geometry as its fine-scale information content contained in data. This fine-scale endeavor shows that our computational proposal is indeed scalable to a MCC setting having a large label-space. Overall the computed multiscale collective of data-driven patterns and knowledge will serve as a basis for constructing visible and explainable subject matter intelligence regarding the system of interest.

Miao Yin, Siyu Liao, Xiao-Yang Liu et al.

Recurrent Neural Networks (RNNs) have been widely used in sequence analysis and modeling. However, when processing high-dimensional data, RNNs typically require very large model sizes, thereby bringing a series of deployment challenges. Although various prior works have been proposed to reduce the RNN model sizes, executing RNN models in resource-restricted environments is still a very challenging problem. In this paper, we propose to develop extremely compact RNN models with fully decomposed hierarchical Tucker (FDHT) structure. The HT decomposition does not only provide much higher storage cost reduction than the other tensor decomposition approaches but also brings better accuracy performance improvement for the compact RNN models. Meanwhile, unlike the existing tensor decomposition-based methods that can only decompose the input-to-hidden layer of RNNs, our proposed fully decomposition approach enables the comprehensive compression for the entire RNN models with maintaining very high accuracy. Our experimental results on several popular video recognition datasets show that our proposed fully decomposed hierarchical tucker-based LSTM (FDHT-LSTM) is extremely compact and highly efficient. To the best of our knowledge, FDHT-LSTM, for the first time, consistently achieves very high accuracy with only few thousand parameters (3,132 to 8,808) on different datasets. Compared with the state-of-the-art compressed RNN models, such as TT-LSTM, TR-LSTM and BT-LSTM, our FDHT-LSTM simultaneously enjoys both order-of-magnitude (3,985x to 10,711x) fewer parameters and significant accuracy improvement (0.6% to 12.7%).

Dheevatsa Mudigere, Yuchen Hao, Jianyu Huang et al.

Deep learning recommendation models (DLRMs) are used across many business-critical services at Facebook and are the single largest AI application in terms of infrastructure demand in its data-centers. In this paper we discuss the SW/HW co-designed solution for high-performance distributed training of large-scale DLRMs. We introduce a high-performance scalable software stack based on PyTorch and pair it with the new evolution of Zion platform, namely ZionEX. We demonstrate the capability to train very large DLRMs with up to 12 Trillion parameters and show that we can attain 40X speedup in terms of time to solution over previous systems. We achieve this by (i) designing the ZionEX platform with dedicated scale-out network, provisioned with high bandwidth, optimal topology and efficient transport (ii) implementing an optimized PyTorch-based training stack supporting both model and data parallelism (iii) developing sharding algorithms capable of hierarchical partitioning of the embedding tables along row, column dimensions and load balancing them across multiple workers; (iv) adding high-performance core operators while retaining flexibility to support optimizers with fully deterministic updates (v) leveraging reduced precision communications, multi-level memory hierarchy (HBM+DDR+SSD) and pipelining. Furthermore, we develop and briefly comment on distributed data ingestion and other supporting services that are required for the robust and efficient end-to-end training in production environments.

Bilge Acun, Matthew Murphy, Xiaodong Wang et al.

The use of GPUs has proliferated for machine learning workflows and is now considered mainstream for many deep learning models. Meanwhile, when training state-of-the-art personal recommendation models, which consume the highest number of compute cycles at our large-scale datacenters, the use of GPUs came with various challenges due to having both compute-intensive and memory-intensive components. GPU performance and efficiency of these recommendation models are largely affected by model architecture configurations such as dense and sparse features, MLP dimensions. Furthermore, these models often contain large embedding tables that do not fit into limited GPU memory. The goal of this paper is to explain the intricacies of using GPUs for training recommendation models, factors affecting hardware efficiency at scale, and learnings from a new scale-up GPU server design, Zion.

Miao Yin, Siyu Liao, Xiao-Yang Liu et al.

Recurrent Neural Networks (RNNs) have been widely used in sequence analysis and modeling. However, when processing high-dimensional data, RNNs typically require very large model sizes, thereby bringing a series of deployment challenges. Although the state-of-the-art tensor decomposition approaches can provide good model compression performance, these existing methods are still suffering some inherent limitations, such as restricted representation capability and insufficient model complexity reduction. To overcome these limitations, in this paper we propose to develop compact RNN models using Hierarchical Tucker (HT) decomposition. HT decomposition brings strong hierarchical structure to the decomposed RNN models, which is very useful and important for enhancing the representation capability. Meanwhile, HT decomposition provides higher storage and computational cost reduction than the existing tensor decomposition approaches for RNN compression. Our experimental results show that, compared with the state-of-the-art compressed RNN models, such as TT-LSTM, TR-LSTM and BT-LSTM, our proposed HT-based LSTM (HT-LSTM), consistently achieves simultaneous and significant increases in both compression ratio and test accuracy on different datasets.

Yu Emma Wang, Carole-Jean Wu, Xiaodong Wang et al.

State-of-the-art machine learning frameworks support a wide variety of design features to enable a flexible machine learning programming interface and to ease the programmability burden on machine learning developers. Identifying and using a performance-optimal setting in feature-rich frameworks, however, involves a non-trivial amount of performance profiling efforts and often relies on domain-specific knowledge. This paper takes a deep dive into analyzing the performance impact of key design features in a machine learning framework and quantifies the role of parallelism. The observations and insights distill into a simple set of guidelines that one can use to achieve much higher training and inference speedup. Across a diverse set of real-world deep learning models, the evaluation results show that the proposed performance tuning guidelines outperform the Intel and TensorFlow recommended settings by 1.29x and 1.34x, respectively.

Maxim Naumov, Dheevatsa Mudigere, Hao-Jun Michael Shi et al.

With the advent of deep learning, neural network-based recommendation models have emerged as an important tool for tackling personalization and recommendation tasks. These networks differ significantly from other deep learning networks due to their need to handle categorical features and are not well studied or understood. In this paper, we develop a state-of-the-art deep learning recommendation model (DLRM) and provide its implementation in both PyTorch and Caffe2 frameworks. In addition, we design a specialized parallelization scheme utilizing model parallelism on the embedding tables to mitigate memory constraints while exploiting data parallelism to scale-out compute from the fully-connected layers. We compare DLRM against existing recommendation models and characterize its performance on the Big Basin AI platform, demonstrating its usefulness as a benchmark for future algorithmic experimentation and system co-design.

Mehmet Necip Kurt, Yasin Yilmaz, Xiaodong Wang

Timely detection of abrupt anomalies is crucial for real-time monitoring and security of modern systems producing high-dimensional data. With this goal, we propose effective and scalable algorithms. Proposed algorithms are nonparametric as both the nominal and anomalous multivariate data distributions are assumed unknown. We extract useful univariate summary statistics and perform anomaly detection in a single-dimensional space. We model anomalies as persistent outliers and propose to detect them via a cumulative sum-like algorithm. In case the observed data have a low intrinsic dimensionality, we learn a submanifold in which the nominal data are embedded and evaluate whether the sequentially acquired data persistently deviate from the nominal submanifold. Further, in the general case, we learn an acceptance region for nominal data via Geometric Entropy Minimization and evaluate whether the sequentially observed data persistently fall outside the acceptance region. We provide an asymptotic lower bound and an asymptotic approximation for the average false alarm period of the proposed algorithm. Moreover, we provide a sufficient condition to asymptotically guarantee that the decision statistic of the proposed algorithm does not diverge in the absence of anomalies. Experiments illustrate the effectiveness of the proposed schemes in quick and accurate anomaly detection in high-dimensional settings.

Ming Zhu, Xiao-Yang Liu, Xiaodong Wang

As efficient traffic-management platforms, public vehicle (PV) systems are envisioned to be a promising approach to solving traffic congestions and pollutions for future smart cities. PV systems provide online/dynamic peer-to-peer ride-sharing services with the goal of serving sufficient number of customers with minimum number of vehicles and lowest possible cost. A key component of the PV system is the online ride-sharing scheduling strategy. In this paper, we propose an efficient path planning strategy that focuses on a limited potential search area for each vehicle by filtering out the requests that violate passenger service quality level, so that the global search is reduced to local search. We analyze the performance of the proposed solution such as reduction ratio of computational complexity. Simulations based on the Manhattan taxi data set show that, the computing time is reduced by 22% compared with the exhaustive search method under the same service quality performance.

Morteza Ashraphijuo, Xiaodong Wang

Minimizing the nuclear norm of a matrix has been shown to be very efficient in reconstructing a low-rank sampled matrix. Furthermore, minimizing the sum of nuclear norms of matricizations of a tensor has been shown to be very efficient in recovering a low-Tucker-rank sampled tensor. In this paper, we propose to recover a low-TT-rank sampled tensor by minimizing a weighted sum of nuclear norms of unfoldings of the tensor. We provide numerical results to show that our proposed method requires significantly less number of samples to recover to the original tensor in comparison with simply minimizing the sum of nuclear norms since the structure of the unfoldings in the TT tensor model is fundamentally different from that of matricizations in the Tucker tensor model.

Morteza Ashraphijuo, Xiaodong Wang, Vaneet Aggarwal

Recently, fundamental conditions on the sampling patterns have been obtained for finite completability of low-rank matrices or tensors given the corresponding ranks. In this paper, we consider the scenario where the rank is not given and we aim to approximate the unknown rank based on the location of sampled entries and some given completion. We consider a number of data models, including single-view matrix, multi-view matrix, CP tensor, tensor-train tensor and Tucker tensor. For each of these data models, we provide an upper bound on the rank when an arbitrary low-rank completion is given. We characterize these bounds both deterministically, i.e., with probability one given that the sampling pattern satisfies certain combinatorial properties, and probabilistically, i.e., with high probability given that the sampling probability is above some threshold. Moreover, for both single-view matrix and CP tensor, we are able to show that the obtained upper bound is exactly equal to the unknown rank if the lowest-rank completion is given. Furthermore, we provide numerical experiments for the case of single-view matrix, where we use nuclear norm minimization to find a low-rank completion of the sampled data and we observe that in most of the cases the proposed upper bound on the rank is equal to the true rank.

Yingming Tsai, Le Zheng, Xiaodong Wang

The millimeter-wave (mmWave) full-dimensional (FD) MIMO system employs planar arrays at both the base station and user equipment and can simultaneously support both azimuth and elevation beamforming. In this paper, we propose atomic-norm-based methods for mmWave FD-MIMO channel estimation under both uniform planar arrays (UPA) and non-uniform planar arrays (NUPA). Unlike existing algorithms such as compressive sensing (CS) or subspace methods, the atomic-norm-based algorithms do not require to discretize the angle spaces of the angle of arrival (AoA) and angle of departure (AoD) into grids, thus provide much better accuracy in estimation. In the UPA case, to reduce the computational complexity, the original large-scale 4D atomic norm minimization problem is approximately reformulated as a semi-definite program (SDP) containing two decoupled two-level Toeplitz matrices. The SDP is then solved via the alternating direction method of multipliers (ADMM) where each iteration involves only closed-form computations. In the NUPA case, the atomic-norm-based formulation for channel estimation becomes nonconvex and a gradient-decent-based algorithm is proposed to solve the problem. Simulation results show that the proposed algorithms achieve better performance than the CS-based and subspace-based algorithms.

Morteza Ashraphijuo, Xiaodong Wang

We consider the problem of low canonical polyadic (CP) rank tensor completion. A completion is a tensor whose entries agree with the observed entries and its rank matches the given CP rank. We analyze the manifold structure corresponding to the tensors with the given rank and define a set of polynomials based on the sampling pattern and CP decomposition. Then, we show that finite completability of the sampled tensor is equivalent to having a certain number of algebraically independent polynomials among the defined polynomials. Our proposed approach results in characterizing the maximum number of algebraically independent polynomials in terms of a simple geometric structure of the sampling pattern, and therefore we obtain the deterministic necessary and sufficient condition on the sampling pattern for finite completability of the sampled tensor. Moreover, assuming that the entries of the tensor are sampled independently with probability $p$ and using the mentioned deterministic analysis, we propose a combinatorial method to derive a lower bound on the sampling probability $p$, or equivalently, the number of sampled entries that guarantees finite completability with high probability. We also show that the existing result for the matrix completion problem can be used to obtain a loose lower bound on the sampling probability $p$. In addition, we obtain deterministic and probabilistic conditions for unique completability. It is seen that the number of samples required for finite or unique completability obtained by the proposed analysis on the CP manifold is orders-of-magnitude lower than that is obtained by the existing analysis on the Grassmannian manifold.

Morteza Ashraphijuo, Xiaodong Wang

In this paper, we analyze the fundamental conditions for low-rank tensor completion given the separation or tensor-train (TT) rank, i.e., ranks of unfoldings. We exploit the algebraic structure of the TT decomposition to obtain the deterministic necessary and sufficient conditions on the locations of the samples to ensure finite completability. Specifically, we propose an algebraic geometric analysis on the TT manifold that can incorporate the whole rank vector simultaneously in contrast to the existing approach based on the Grassmannian manifold that can only incorporate one rank component. Our proposed technique characterizes the algebraic independence of a set of polynomials defined based on the sampling pattern and the TT decomposition, which is instrumental to obtaining the deterministic condition on the sampling pattern for finite completability. In addition, based on the proposed analysis, assuming that the entries of the tensor are sampled independently with probability $p$, we derive a lower bound on the sampling probability $p$, or equivalently, the number of sampled entries that ensures finite completability with high probability. Moreover, we also provide the deterministic and probabilistic conditions for unique completability.

Shaohe Lv, Yong Lu, Mianxiong Dong et al.

Human-machine systems required a deep understanding of human behaviors. Most existing research on action recognition has focused on discriminating between different actions, however, the quality of executing an action has received little attention thus far. In this paper, we study the quality assessment of driving behaviors and present WiQ, a system to assess the quality of actions based on radio signals. This system includes three key components, a deep neural network based learning engine to extract the quality information from the changes of signal strength, a gradient based method to detect the signal boundary for an individual action, and an activitybased fusion policy to improve the recognition performance in a noisy environment. By using the quality information, WiQ can differentiate a triple body status with an accuracy of 97%, while for identification among 15 drivers, the average accuracy is 88%. Our results show that, via dedicated analysis of radio signals, a fine-grained action characterization can be achieved, which can facilitate a large variety of applications, such as smart driving assistants.

Morteza Ashraphijuo, Xiaodong Wang, Vaneet Aggarwal

We consider the multi-view data completion problem, i.e., to complete a matrix $\mathbf{U}=[\mathbf{U}_1|\mathbf{U}_2]$ where the ranks of $\mathbf{U},\mathbf{U}_1$, and $\mathbf{U}_2$ are given. In particular, we investigate the fundamental conditions on the sampling pattern, i.e., locations of the sampled entries for finite completability of such a multi-view data given the corresponding rank constraints. In contrast with the existing analysis on Grassmannian manifold for a single-view matrix, i.e., conventional matrix completion, we propose a geometric analysis on the manifold structure for multi-view data to incorporate more than one rank constraint. We provide a deterministic necessary and sufficient condition on the sampling pattern for finite completability. We also give a probabilistic condition in terms of the number of samples per column that guarantees finite completability with high probability. Finally, using the developed tools, we derive the deterministic and probabilistic guarantees for unique completability.

Morteza Ashraphijuo, Vaneet Aggarwal, Xiaodong Wang

We investigate the fundamental conditions on the sampling pattern, i.e., locations of the sampled entries, for finite completability of a low-rank tensor given some components of its Tucker rank. In order to find the deterministic necessary and sufficient conditions, we propose an algebraic geometric analysis on the Tucker manifold, which allows us to incorporate multiple rank components in the proposed analysis in contrast with the conventional geometric approaches on the Grassmannian manifold. This analysis characterizes the algebraic independence of a set of polynomials defined based on the sampling pattern, which is closely related to finite completion. Probabilistic conditions are then studied and a lower bound on the sampling probability is given, which guarantees that the proposed deterministic conditions on the sampling patterns for finite completability hold with high probability. Furthermore, using the proposed geometric approach for finite completability, we propose a sufficient condition on the sampling pattern that ensures there exists exactly one completion for the sampled tensor.

Xiao-Yang Liu, Shuchin Aeron, Vaneet Aggarwal et al.

The low-tubal-rank tensor model has been recently proposed for real-world multidimensional data. In this paper, we study the low-tubal-rank tensor completion problem, i.e., to recover a third-order tensor by observing a subset of its elements selected uniformly at random. We propose a fast iterative algorithm, called {\em Tubal-Alt-Min}, that is inspired by a similar approach for low-rank matrix completion. The unknown low-tubal-rank tensor is represented as the product of two much smaller tensors with the low-tubal-rank property being automatically incorporated, and Tubal-Alt-Min alternates between estimating those two tensors using tensor least squares minimization. First, we note that tensor least squares minimization is different from its matrix counterpart and nontrivial as the circular convolution operator of the low-tubal-rank tensor model is intertwined with the sub-sampling operator. Second, the theoretical performance guarantee is challenging since Tubal-Alt-Min is iterative and nonconvex in nature. We prove that 1) Tubal-Alt-Min guarantees exponential convergence to the global optima, and 2) for an $n \times n \times k$ tensor with tubal-rank $r \ll n$, the required sampling complexity is $O(nr^2k \log^3 n)$ and the computational complexity is $O(n^2rk^2 \log^2 n)$. Third, on both synthetic data and real-world video data, evaluation results show that compared with tensor-nuclear norm minimization (TNN-ADMM), Tubal-Alt-Min improves the recovery error dramatically (by orders of magnitude). It is estimated that Tubal-Alt-Min converges at an exponential rate $10^{-0.4423 \text{Iter}}$ where $\text{Iter}$ denotes the number of iterations, which is much faster than TNN-ADMM's $10^{-0.0332 \text{Iter}}$, and the running time can be accelerated by more than $5$ times for a $200 \times 200 \times 20$ tensor.

Xiao-Yang Liu, Shuchin Aeron, Vaneet Aggarwal et al.

Indoor localization is a supporting technology for a broadening range of pervasive wireless applications. One promis- ing approach is to locate users with radio frequency fingerprints. However, its wide adoption in real-world systems is challenged by the time- and manpower-consuming site survey process, which builds a fingerprint database a priori for localization. To address this problem, we visualize the 3-D RF fingerprint data as a function of locations (x-y) and indices of access points (fingerprint), as a tensor and use tensor algebraic methods for an adaptive tubal-sampling of this fingerprint space. In particular using a recently proposed tensor algebraic framework in [1] we capture the complexity of the fingerprint space as a low-dimensional tensor-column space. In this formulation the proposed scheme exploits adaptivity to identify reference points which are highly informative for learning this low-dimensional space. Further, under certain incoherency conditions we prove that the proposed scheme achieves bounded recovery error and near-optimal sampling complexity. In contrast to several existing work that rely on random sampling, this paper shows that adaptivity in sampling can lead to significant improvements in localization accuracy. The approach is validated on both data generated by the ray-tracing indoor model which accounts for the floor plan and the impact of walls and the real world data. Simulation results show that, while maintaining the same localization accuracy of existing approaches, the amount of samples can be cut down by 71% for the high SNR case and 55% for the low SNR case.