Search

We revisit the sample and computational complexity of completing a rank-1 tensor in $\otimes_{i=1}^{N} \mathbb{R}^{d}$, given a uniformly sampled subset of its entries. We present a characterization of the problem (i.e. nonzero entries) which admits an algorithm amounting to Gauss-Jordan on a pair of random linear systems. For example, when $N = \Theta(1)$, we prove it uses no more than $m = O(d^2 \log d)$ samples and runs in $O(md^2)$ time. Moreover, we show any algorithm requires $\Omega(d\log d)$ samples. By contrast, existing upper bounds on the sample complexity are at least as large as $d^{1.5} \mu^{\Omega(1)} \log^{\Omega(1)} d$, where $\mu$ can be $\Theta(d)$ in the worst case. Prior work obtained these looser guarantees in higher rank versions of our problem, and tend to involve more complicated algorithms., Comment: 16 pages; corrected typos in Prior Work section & Theorem 1.5

We introduce a new tensor norm, the average spectrum norm, to study sample complexity of tensor completion problems based on the canonical polyadic decomposition (CPD). Properties of the average spectrum norm and its dual norm are investigated, demonstrating their utility for low-rank tensor recovery analysis. Our novel approach significantly reduces the provable sample rate for CPD-based noisy tensor completion, providing the best bounds to date on the number of observed noisy entries required to produce an arbitrarily accurate estimate of an underlying mean value tensor. Under Poisson and Bernoulli multivariate distributions, we show that an $N$-way CPD rank-$R$ parametric tensor $\boldsymbol{\mathscr{M}}\in\mathbb{R}^{I\times \cdots\times I}$ generating noisy observations can be approximated by large likelihood estimators from $\mathcal{O}(IR^2\log^{N+2}(I))$ revealed entries. Furthermore, under nonnegative and orthogonal versions of the CPD we improve the result to depend linearly on the rank, achieving the near-optimal rate $\mathcal{O}(IR\log^{N+2}(I))$., Comment: Error, in Section 2.1.2

We consider the class $S_n(1324)$ of permutations of size $n$ that avoid the pattern 1324 and examine the subset $S_n^{a\prec n}(1324)$ of elements for which $a\prec n\prec [a-1]$, $a\ge 1$. This notation means that, when written in one line notation, such a permutation must have $a$ to the left of $n$, and the elements of $\{1,\dots,a-1\}$ must all be to the right of $n$. For $n\ge 2$, we establish a connection between the subset of permutations in $S_n^{1\prec n}(1324)$ having the 1 adjacent to the $n$ (called primitives), and the set of 1324-avoiding dominoes with $n-2$ points. For $a\in\{1,2\}$, we introduce constructive algorithms and give formulas for the enumeration of $S_n^{a\prec n}(1324)$ by the position of $a$ relative to the position of $n$. For $a\ge 3$, we formulate some conjectures for the corresponding generating functions., Comment: 10 pages. Revised version

The massive cost of 3D acquisition calls for methods to reduce the number of receivers by designing optimal receiver sampling masks. Recent studies on 2D seismic showed that maximizing the spectral gap of the subsampling mask leads to better wavefield reconstruction results. We enrich the current study by proposing a simulation-free method to generate optimal 3D acquisition by maximizing the spectral gap of the subsampling mask via a simulated annealing algorithm. Numerical experiments confirm improvement of the proposed method over receiver sampling locations obtained by jittered sampling.

Tensor completion is a core machine learning algorithm used in recommender systems and other domains with missing data. While the matrix case is well-understood, theoretical results for tensor problems are limited, particularly when the sampling patterns are deterministic. Here we bound the generalization error of the solutions of two tensor completion methods, Poisson loss and atomic norm minimization, providing tighter bounds in terms of the target tensor rank. If the ground-truth tensor is order $t$ with CP-rank $r$, the dependence on $r$ is improved from $r^{2(t-1)(t^2-t-1)}$ in arXiv:1910.10692 to $r^{2(t-1)(3t-5)}$. The error in our bounds is deterministically controlled by the spectral gap of the sampling sparsity pattern. We also prove several new properties for the atomic tensor norm, reducing the rank dependence from $r^{3t-3}$ in arXiv:1711.04965 to $r^{3t-5}$ under random sampling schemes. A limitation is that atomic norm minimization, while theoretically interesting, leads to inefficient algorithms. However, numerical experiments illustrate the dependence of the reconstruction error on the spectral gap for the practical max-quasinorm, ridge penalty, and Poisson loss minimization algorithms. This view through the spectral gap is a promising window for further study of tensor algorithms., Comment: In proceedings of SampTA 2023

Metachronal locomotion is a widespread swimming mode used by aquatic swarming organisms to achieve performance and maneuverability in the intermediate Reynolds number regime. Our understanding of the mechanisms driving these abilities is limited due to the challenges of studying live organisms. Designs inspired by nature present an approach for developing small and maneuverable underwater self-propelled robots. Here, we present the design, manufacture, and validation of the \emph{Pleobot} --a unique krill-inspired robotic swimming appendage constituting the first platform to study metachronal propulsion comprehensively. Our methods combine a multi-link 3D printed mechanism with active and passive actuation of the joints to generate natural kinematics. Using force and fluid flow measurements in parallel with biological data, we show the link between the flow produced by the appendage and thrust. Further, we provide the first account of a leading-edge suction effect that contributes to lift during the power stroke. The repeatability and modularity of the \emph{Pleobot} enable the independent manipulation of particular motions and traits to test hypotheses central to understanding the relationship between form and function. Lastly, we outline future directions for the \emph{Pleobot}, including adapting morphological features. We foresee a broad appeal to a wide array of scientific disciplines, from fundamental studies in ecology, biology, and engineering, to developing new platforms for studying oceans across the solar system., Comment: 13 pages, 5 figures

Modern-day reservoir management and monitoring of geological carbon storage increasingly call for costly time-lapse seismic data collection. In this letter, we show how techniques from graph theory can be used to optimize acquisition geometries for low-cost sparse 4D seismic. Based on midpoint-offset domain connectivity arguments, the proposed algorithm automatically produces sparse non-replicated time-lapse acquisition geometries that favor wavefield recovery.

Many empirical studies suggest that samples of continuous-time signals taken at locations randomly deviated from an equispaced grid (i.e., off-the-grid) can benefit signal acquisition, e.g., undersampling and anti-aliasing. However, explicit statements of such advantages and their respective conditions are scarce in the literature. This paper provides some insight on this topic when the sampling positions are known, with grid deviations generated i.i.d. from a variety of distributions. By solving a square-root LASSO decoder with an interpolation kernel we demonstrate the capabilities of nonuniform samples for compressive sampling, an effective paradigm for undersampling and anti-aliasing. For functions in the Wiener algebra that admit a discrete $s$-sparse representation in some transform domain, we show that $\mathcal{O}(s\log N)$ random off-the-grid samples are sufficient to recover an accurate $\frac{N}{2}$-bandlimited approximation of the signal. For sparse signals (i.e., $s \ll N$), this sampling complexity is a great reduction in comparison to equispaced sampling where $\mathcal{O}(N)$ measurements are needed for the same quality of reconstruction (Nyquist-Shannon sampling theorem). We further consider noise attenuation via oversampling (relative to a desired bandwidth), a standard technique with limited theoretical understanding when the sampling positions are non-equispaced. By solving a least squares problem, we show that $\mathcal{O}(N\log N)$ i.i.d. randomly deviated samples provide an accurate $\frac{N}{2}$-bandlimited approximation of the signal with suppression of the noise energy by a factor $\sim\frac{1}{\sqrt{\log N}}$.

Recent work in the matrix completion literature has shown that prior knowledge of a matrix's row and column spaces can be successfully incorporated into reconstruction programs to substantially benefit matrix recovery. This paper proposes a novel methodology that exploits more general forms of known matrix structure in terms of subspaces. The work derives reconstruction error bounds that are informative in practice, providing insight to previous approaches in the literature while introducing novel programs that severely reduce sampling complexity. The main result shows that a family of weighted nuclear norm minimization programs incorporating a $M_1 r$-dimensional subspace of $n\times n$ matrices (where $M_1\geq 1$ conveys structural properties of the subspace) allow accurate approximation of a rank $r$ matrix aligned with the subspace from a near-optimal number of observed entries (within a logarithmic factor of $M_1 r)$. The result is robust, where the error is proportional to measurement noise, applies to full rank matrices, and reflects degraded output when erroneous prior information is utilized. Numerical experiments are presented that validate the theoretical behavior derived for several example weighted programs., Comment: 41 pages, 2 figures

Seismic imaging in challenging sedimentary basins and reservoirs requires acquiring, processing, and imaging very large volumes of data (tens of terabytes). To reduce the cost of acquisition and the time from acquiring the data to producing a subsurface image, novel acquisition systems based on compressive sensing, low-rank matrix recovery, and randomized sampling have been developed and implemented. These approaches allow practitioners to achieve dense wavefield reconstruction from a substantially reduced number of field samples. However, designing acquisition surveys suited for this new sampling paradigm remains a critical and challenging role in oil, gas, and geothermal exploration. Typical random designs studied in the low-rank matrix recovery and compressive sensing literature are difficult to achieve by standard industry hardware. For practical purposes, a compromise between stochastic and realizable samples is needed. In this paper, we propose a deterministic and computationally cheap tool to alleviate randomized acquisition design, prior to survey deployment and large-scale optimization. We consider universal and deterministic matrix completion results in the context of seismology, where a bipartite graph representation of the source-receiver layout allows for the respective spectral gap to act as a quality metric for wavefield reconstruction. We provide realistic scenarios to demonstrate the utility of the spectral gap as a flexible tool that can be incorporated into existing survey design workflows for successful seismic data acquisition via low-rank and sparse signal recovery.

Marine exploration is essential to understanding ocean processes and organisms. While the use of current unmanned underwater vehicles has enabled many discoveries, there are still plenty of limitations toward exploring complex environments. Bio-inspired robots are a promising solution for highly maneuverable underwater swimming at moderate speeds. Krill, especially, are efficient swimmers in the intermediate Reynolds number regime and can inform engineering solutions for ocean exploration. In this paper, we present the design, manufacture, and validation of a new krill-inspired, metachronal, drag-based robotic system. By combining active and passive actuation of the joints with 3D printed parts, our unique design recreates the swimming kinematics of Euphausia superba in a compact and reproducible robotic platform. The motion of the anterior and posterior appendage segments is achieved using servo motors and a multi-link mechanism, while the out-of-plane motion of the biramous distal segments is attained via fluid-structure interactions. Going forward, our platform will be leveraged to study metachronal, drag-based swimmers across taxa to identify unifying success mechanisms at different scales, facilitating the development of a new generation of underwater robots.

We propose a novel statistical inference methodology for multiway count data that is corrupted by false zeros that are indistinguishable from true zero counts. Our approach consists of zero-truncating the Poisson distribution to neglect all zero values. This simple truncated approach dispenses with the need to distinguish between true and false zero counts and reduces the amount of data to be processed. Inference is accomplished via tensor completion that imposes low-rank tensor structure on the Poisson parameter space. Our main result shows that an $N$-way rank-$R$ parametric tensor $\boldsymbol{\mathscr{M}}\in(0,\infty)^{I\times \cdots\times I}$ generating Poisson observations can be accurately estimated by zero-truncated Poisson regression from approximately $IR^2\log_2^2(I)$ non-zero counts under the nonnegative canonical polyadic decomposition. Our result also quantifies the error made by zero-truncating the Poisson distribution when the parameter is uniformly bounded from below. Therefore, under a low-rank multiparameter model, we propose an implementable approach guaranteed to achieve accurate regression in under-determined scenarios with substantial corruption by false zeros. Several numerical experiments are presented to explore the theoretical results., Comment: 30 pages, 5 figures

This paper shows that Bitcoin is not correlated to a general uncertainty index as measured by the Google Trends data of Castelnuovo and Tran (2017). Instead, Bitcoin is linked to a Google Trends attention measure specific for the cryptocurrency market. First, we find a bidirectional relationship between Google Trends attention and Bitcoin returns up to six days. Second, information flows from Bitcoin volatility to Google Trends attention seem to be larger than information flows in the other direction. These relations hold across different sub-periods and different compositions of the proposed Google Trends Cryptocurrency index., Comment: 9 pages, 5 figures

Computationally modeling the behavior of wavelength-sized non-spherical particles in optical tweezers can give insight into the existence and stability of trapping equilibria as well as the optical manipulation of such particles more broadly. Here, we report Brownian dynamics simulations of non-spherical particles that account for detailed optical, hydrodynamic, and thermal interactions. We use a $T$-matrix formalism to calculate the optical forces and torques exerted by focused laser beams on clusters of wavelength-sized spheres, and we incorporate detailed diffusion tensors that capture the anisotropic Brownian motion of the clusters. For two-sphere clusters whose size is comparable to or larger than the wavelength, we observe photokinetic effects in elliptically-polarized beams. We also demonstrate that multiple trapping equilibria exist for a highly asymmetric chiral cluster of seven spheres. Our simulations may lead to practical suggestions for optical trapping and manipulation as well as a deeper understanding of the underlying physics., Comment: 20 pages, 15 figures

Modern-day seismic imaging and monitoring technology increasingly rely on dense full-azimuth sampling. Unfortunately, the costs of acquiring densely sampled data rapidly become prohibitive and we need to look for ways to sparsely collect data, e.g. from sparsely distributed ocean bottom nodes, from which we then derive densely sampled surveys through the method of wavefield reconstruction. Because of their relatively cheap and simple calculations, wavefield reconstruction via matrix factorizations has proven to be a viable and scalable alternative to the more generally used transform-based methods. While this method is capable of processing all full azimuth data frequency by frequency slice, its performance degrades at higher frequencies because monochromatic data at these frequencies is not as well approximated by low-rank factorizations. We address this problem by proposing a recursive recovery technique, which involves weighted matrix factorizations where recovered wavefields at the lower frequencies serve as prior information for the recovery of the higher frequencies. To limit the adverse effects of potential overfitting, we propose a limited-subspace recursively weighted matrix factorization approach where the size of the row and column subspaces to construct the weight matrices is constrained. We apply our method to data collected from the Gulf of Suez, and our results show that our limited-subspace weighted recovery method significantly improves the recovery quality.

In this article, we consider a Markov-modulated model with jumps for short rate dynamics. We obtain closed formulas for the term structure and forward rates using the properties of the jump-telegraph process and the expectation hypothesis. The results are compared with the numerical solution of the corresponding partial differential equation.