Search

Principal component analysis (PCA) has been widely used in analyzing high-dimensional data. It converts a set of observed data points of possibly correlated variables into a set of linearly uncorrelated variables via an orthogonal transformation. To handle streaming data and reduce the complexities of PCA, (subspace) online PCA iterations were proposed to iteratively update the orthogonal transformation by taking one observed data point at a time. Existing works on the convergence of (subspace) online PCA iterations mostly focus on the case where sample are almost surely uniformly bounded. In this paper, we analyze the convergence of a subspace online PCA iteration under more practical assumption and obtain a nearly optimal finite-sample error bound. Our convergence rate almost matches the minimax information lower bound. We prove that the convergence is nearly global in the sense that the subspace online PCA iteration is convergent with high probability for random initial guesses. This work also leads to a simpler proof of the recent work on analyzing online PCA for the first principal component only., Comment: 34 pages. Accepted for publication in SCIENCE CHINA Mathematics

In this paper, we study intermittent behaviors of coupled piecewise-expanding map lattices with two nodes and a weak coupling. We show that the successive phase transition between ordered and disordered phases occurs for almost every orbit. That is, we prove $\liminf_{n\rightarrow \infty}| x_1(n)-x_2(n)|=0$ and $\limsup_{n\rightarrow \infty}| x_1(n)-x_2(n)|\ge c_0>0$, where $x_1(n), x_2(n)$ correspond to the coordinates of two nodes at the iterative step $n$. We also prove the same conclusion for weakly coupled tent-map lattices with any multi-nodes., Comment: 33 pages, 4 figures

The eigenvalue problem of a graph Laplacian matrix $L$ arising from a simple, connected and undirected graph has been given more attention due to its extensive applications, such as spectral clustering, community detection, complex network, image processing and so on. The associated graph Laplacian matrix is symmetric, positive semi-definite, and is usually large and sparse. Computing some smallest positive eigenvalues and corresponding eigenvectors is often of interest. However, the singularity of $L$ makes the classical eigensolvers inefficient since we need to factorize $L$ for the purpose of solving large and sparse linear systems exactly. The next difficulty is that it is usually time consuming or even unavailable to factorize a large and sparse matrix arising from real network problems from big data such as social media transactional databases, and sensor systems because there is in general not only local connections. In this paper, we propose an eignsolver based on the inexact residual Arnoldi method together with an implicit remedy of the singularity and an effective deflation for convergent eigenvalues. Numerical experiments reveal that the integrated eigensolver outperforms the classical Arnoldi/Lanczos method for computing some smallest positive eigeninformation provided the LU factorization is not available.

Model compression is significant for the wide adoption of Recurrent Neural Networks (RNNs) in both user devices possessing limited resources and business clusters requiring quick responses to large-scale service requests. This work aims to learn structurally-sparse Long Short-Term Memory (LSTM) by reducing the sizes of basic structures within LSTM units, including input updates, gates, hidden states, cell states and outputs. Independently reducing the sizes of basic structures can result in inconsistent dimensions among them, and consequently, end up with invalid LSTM units. To overcome the problem, we propose Intrinsic Sparse Structures (ISS) in LSTMs. Removing a component of ISS will simultaneously decrease the sizes of all basic structures by one and thereby always maintain the dimension consistency. By learning ISS within LSTM units, the obtained LSTMs remain regular while having much smaller basic structures. Based on group Lasso regularization, our method achieves 10.59x speedup without losing any perplexity of a language modeling of Penn TreeBank dataset. It is also successfully evaluated through a compact model with only 2.69M weights for machine Question Answering of SQuAD dataset. Our approach is successfully extended to non- LSTM RNNs, like Recurrent Highway Networks (RHNs). Our source code is publicly available at https://github.com/wenwei202/iss-rnns, Comment: Published in ICLR 2018 ( the Sixth International Conference on Learning Representations)

Surface parameterizations have been widely applied to computer graphics and digital geometry processing. In this paper, we propose a novel stretch energy minimization (SEM) algorithm for the computation of equiareal parameterizations of simply connected open surfaces with a very small area distortion and a highly improved computational efficiency. In addition, the existence of nontrivial limit points of the SEM algorithm is guaranteed under some mild assumptions of the mesh quality. Numerical experiments indicate that the efficiency, accuracy, and robustness of the proposed SEM algorithm outperform other state-of-the-art algorithms. Applications of the SEM on surface remeshing and surface registration for simply connected open surfaces are demonstrated thereafter. Thanks to the SEM algorithm, the computations for these applications can be carried out efficiently and robustly., Comment: 29 pages, 15 figures

Long-range interacting systems such as nitrogen vacancy centers in diamond and trapped ions serve as useful experimental setups to probe a range of nonequilibrium many-body phenomena. In particular, via driving, various effective Hamiltonians with physics potentially quite distinct from short-range systems can be realized. In this Letter, we derive general bounds on the linear response energy absorption rates of periodically driven systems of spins or fermions with long-range interactions that are sign changing and fall off as $1/r^\alpha$ with $\alpha > d/2$. We show that the disordered averaged energy absorption rate at high temperature decays exponentially with the driving frequency. This strongly suggests the presence of a prethermal plateau in which dynamics is governed by an effective, static Hamiltonian for long times, and we provide numerical evidence to support such a statement. Our results are relevant for understanding timescales of both heating and hence new dynamical regimes described by effective Hamiltonians in such long-range systems., Comment: 6+6 pages

High network communication cost for synchronizing gradients and parameters is the well-known bottleneck of distributed training. In this work, we propose TernGrad that uses ternary gradients to accelerate distributed deep learning in data parallelism. Our approach requires only three numerical levels {-1,0,1}, which can aggressively reduce the communication time. We mathematically prove the convergence of TernGrad under the assumption of a bound on gradients. Guided by the bound, we propose layer-wise ternarizing and gradient clipping to improve its convergence. Our experiments show that applying TernGrad on AlexNet does not incur any accuracy loss and can even improve accuracy. The accuracy loss of GoogLeNet induced by TernGrad is less than 2% on average. Finally, a performance model is proposed to study the scalability of TernGrad. Experiments show significant speed gains for various deep neural networks. Our source code is available., Comment: NIPS 2017 Oral

We propose a modified Newton iteration for finding some nonnegative Z-eigenpairs of a nonnegative tensor. When the tensor is irreducible, all nonnegative eigenpairs are known to be positive. We prove local quadratic convergence of the new iteration to any positive eigenpair of a nonnegative tensor, under the usual assumption guaranteeing the local quadratic convergence of the original Newton iteration. A big advantage of the modified Newton iteration is that it seems capable of finding a nonnegative eigenpair starting with any positive unit vector. Special attention is paid to transition probability tensors.

Laser cooling of relativistic heavy ion beams of Li-like C$^{3+}$ and O$^{4+}$ is being in preparation at the experimental Cooler Storage Ring (CSRe). Recently, a preparatory experiment to test important prerequisites for laser cooling of relativistic $^{12}$C$^{3+}$ ion beams using a pulsed laser system has been performed at the CSRe. Unfortunately, the interaction between the ions and the pulsed laser cannot be detected. In order to study the laser cooling process and find the optimized parameters for future laser cooling experiment, a multi-particle tracking method was developed to simulate the detailed longitudinal dynamics of laser-cooled ion beams at the CSRe. The simulations of laser cooling of the $^{12}$C$^{3+}$ ion beams by scanning the frequency of RF-buncher or continuous wave (CW) laser wavelength were performed. The simulation results indicated that a large momentum spread ion beams could be laser-cooled by the combination of only one CW laser and the RF-buncher and shown the requirements of a successful laser cooling experiment. The optimized parameters for scanning the RF-buncher frequency or laser frequency were obtained. Furthermore, the heating effects were estimated for laser cooling at the CSRe. The Schottky noise spectra of longitudinally modulated and laser-cooled ion beams was simulated to fully explain and anticipate the experimental results. The combination of Schottky spectra from the highly sensitive resonant Schottky pick-up and the simulation methods developed in this paper will be helpful to investigate the longitudinal dynamics of RF-bunched and ultra-cold ion beams in the upcoming laser cooling experiments at the CSRe., Comment: To be published in Chinese Physics C

Very large-scale Deep Neural Networks (DNNs) have achieved remarkable successes in a large variety of computer vision tasks. However, the high computation intensity of DNNs makes it challenging to deploy these models on resource-limited systems. Some studies used low-rank approaches that approximate the filters by low-rank basis to accelerate the testing. Those works directly decomposed the pre-trained DNNs by Low-Rank Approximations (LRA). How to train DNNs toward lower-rank space for more efficient DNNs, however, remains as an open area. To solve the issue, in this work, we propose Force Regularization, which uses attractive forces to enforce filters so as to coordinate more weight information into lower-rank space. We mathematically and empirically verify that after applying our technique, standard LRA methods can reconstruct filters using much lower basis and thus result in faster DNNs. The effectiveness of our approach is comprehensively evaluated in ResNets, AlexNet, and GoogLeNet. In AlexNet, for example, Force Regularization gains 2x speedup on modern GPU without accuracy loss and 4.05x speedup on CPU by paying small accuracy degradation. Moreover, Force Regularization better initializes the low-rank DNNs such that the fine-tuning can converge faster toward higher accuracy. The obtained lower-rank DNNs can be further sparsified, proving that Force Regularization can be integrated with state-of-the-art sparsity-based acceleration methods. Source code is available in https://github.com/wenwei202/caffe, Comment: ICCV 2017

We analyze the quantum dynamics of periodically driven, disordered systems in the presence of long-range interactions. Focusing on the stability of discrete time crystalline (DTC) order in such systems, we use a perturbative procedure to evaluate its lifetime. For 3D systems with dipolar interactions, we show that the corresponding decay is parametrically slow, implying that robust, long-lived DTC order can be obtained. We further predict a sharp crossover from the stable DTC regime into a regime where DTC order is lost, reminiscent of a phase transition. These results are in good agreement with the recent experiments utilizing a dense, dipolar spin ensemble in diamond [Nature 543, 221-225 (2017)]. They demonstrate the existence of a novel, critical DTC regime that is stabilized not by many-body localization but rather by slow, critical dynamics. Our analysis shows that the DTC response can be used as a sensitive probe of nonequilibrium quantum matter., Comment: 5 + 4 pages, 3 figures, updated references and corrected some typos, paper updated to match published version

Let $F$ be a local field of characteristic not $2$. We propose a definition of stable conjugacy for all the covering groups of $\mathrm{Sp}(2n,F)$ constructed by Brylinski and Deligne, whose degree we denote by $m$. To support this notion, we follow Kaletha's approach to construct genuine epipelagic $L$-packets for such covers in the non-archimedean case with $p \nmid 2m$, or some weaker variant when $4 \mid m$; we also prove the stability of packets when $F \supset \mathbb{Q}_p$ with $p$ large. When $m=2$, the stable conjugacy reduces to that defined by J. Adams, and the epipelagic $L$-packets coincide with those obtained by $\Theta$-correspondence. This fits within Weissman's formalism of L-groups. For $n=1$ and $m$ even, it is also compatible with the transfer factors proposed by K. Hiraga and T. Ikeda., Comment: 92 pages, with an index. The new Section 10 is the Errata that fixes the mistakes in Sections 7.2 and 8.3 in the published version

Recently, DNN model compression based on network architecture design, e.g., SqueezeNet, attracted a lot attention. No accuracy drop on image classification is observed on these extremely compact networks, compared to well-known models. An emerging question, however, is whether these model compression techniques hurt DNN's learning ability other than classifying images on a single dataset. Our preliminary experiment shows that these compression methods could degrade domain adaptation (DA) ability, though the classification performance is preserved. Therefore, we propose a new compact network architecture and unsupervised DA method in this paper. The DNN is built on a new basic module Conv-M which provides more diverse feature extractors without significantly increasing parameters. The unified framework of our DA method will simultaneously learn invariance across domains, reduce divergence of feature representations, and adapt label prediction. Our DNN has 4.1M parameters, which is only 6.7% of AlexNet or 59% of GoogLeNet. Experiments show that our DNN obtains GoogLeNet-level accuracy both on classification and DA, and our DA method slightly outperforms previous competitive ones. Put all together, our DA strategy based on our DNN achieves state-of-the-art on sixteen of total eighteen DA tasks on popular Office-31 and Office-Caltech datasets., Comment: 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR'17)

In this paper, a homotopy continuation method for the computation of nonnegative Z-/H-eigenpairs of a nonnegative tensor is presented. We show that the homotopy continuation method is guaranteed to compute a nonnegative eigenpair. Additionally, using degree analysis, we show that the number of positive Z-eigenpairs of an irreducible nonnegative tensor is odd. A novel homotopy continuation method is proposed to compute an odd number of positive Z-eigenpairs, and some numerical results are presented., Comment: 22 pages, 3 figures

Synapse crossbar is an elementary structure in Neuromorphic Computing Systems (NCS). However, the limited size of crossbars and heavy routing congestion impedes the NCS implementations of big neural networks. In this paper, we propose a two-step framework (namely, group scissor) to scale NCS designs to big neural networks. The first step is rank clipping, which integrates low-rank approximation into the training to reduce total crossbar area. The second step is group connection deletion, which structurally prunes connections to reduce routing congestion between crossbars. Tested on convolutional neural networks of LeNet on MNIST database and ConvNet on CIFAR-10 database, our experiments show significant reduction of crossbar area and routing area in NCS designs. Without accuracy loss, rank clipping reduces total crossbar area to 13.62\% and 51.81\% in the NCS designs of LeNet and ConvNet, respectively. Following rank clipping, group connection deletion further reduces the routing area of LeNet and ConvNet to 8.1\% and 52.06\%, respectively., Comment: Accepted in DAC 2017

This paper is a physicist's review of the major conceptual issues concerning the problem of spectral universality in quantum systems. Here we present a unified, graph-based view of all archetypical models of such universality (billiards, particles in random media, interacting spin or fermion systems). We find phenomenological relations between the onset of ergodicity (Gaussian-random delocalization of eigenstates) and the structure of the appropriate graphs, and we construct a heuristic picture of summing trajectories on graphs that describes why a generic interacting system should be ergodic. We also provide an operator-based discussion of quantum chaos and propose criteria to distinguish bases that can usefully diagnose ergodicity. The result of this analysis is a rough but systematic outline of how ergodicity changes across the space of all theories with a given Hilbert space dimension. As a special case, we study the SYK model and report on the transition from maximal to partial ergodicity as the disorder strength is decreased., Comment: 56 pages, many figures

Brain inspired neuromorphic computing has demonstrated remarkable advantages over traditional von Neumann architecture for its high energy efficiency and parallel data processing. However, the limited resolution of synaptic weights degrades system accuracy and thus impedes the use of neuromorphic systems. In this work, we propose three orthogonal methods to learn synapses with one-level precision, namely, distribution-aware quantization, quantization regularization and bias tuning, to make image classification accuracy comparable to the state-of-the-art. Experiments on both multi-layer perception and convolutional neural networks show that the accuracy drop can be well controlled within 0.19% (5.53%) for MNIST (CIFAR-10) database, compared to an ideal system without quantization., Comment: Best Paper Award of ASP-DAC 2017