We provide a rigorous analysis of implicit regularization in an overparametrized tensor factorization problem beyond the lazy training regime. For matrix factorization problems, this phenomenon has been studied in a number of works. A particular challenge has been to design universal initialization strategies which provably lead to implicit regularization in gradient-descent methods. At the same time, it has been argued by Cohen et. al. 2016 that more general classes of neural networks can be captured by considering tensor factorizations. However, in the tensor case, implicit regularization has only been rigorously established for gradient flow or in the lazy training regime. In this paper, we prove the first tensor result of its kind for gradient descent rather than gradient flow. We focus on the tubal tensor product and the associated notion of low tubal rank, encouraged by the relevance of this model for image data. We establish that gradient descent in an overparametrized tensor factorization model with a small random initialization exhibits an implicit bias towards solutions of low tubal rank. Our theoretical findings are illustrated in an extensive set of numerical simulations show-casing the dynamics predicted by our theory as well as the crucial role of using a small random initialization.

Abstract This paper studies the problem of recovering a signal from one-bit compressed sensing measurements under a manifold model; that is, assuming that the signal lies on or near a manifold of low intrinsic dimension. We provide a convex recovery method based on the Geometric Multi-Resolution Analysis and prove recovery guarantees with a near-optimal scaling in the intrinsic manifold dimension. Our method is the first tractable algorithm with such guarantees for this setting. The results are complemented by numerical experiments confirming the validity of our approach.

The widespread use of multisensor technology and the emergence of big data sets have brought the necessity to develop more versatile tools to represent higher order data with multiple aspects and high dimensionality. Data in the form of multidimensional arrays, also referred to as tensors, arise in a variety of applications including chemometrics, hyperspectral imaging, high-resolution videos, neuroimaging, biometrics, and social network analysis. Early multiway data analysis approaches reformatted such tensor data as large vectors or matrices and then resorted to dimensionality reduction methods developed for classical two-way analysis such as principal component analysis (PCA). However, one cannot discover hidden components within multiway data using conventional PCA. To this end, tensor decomposition methods which are flexible in the choice of the constraints and that extract more general latent components have been proposed. In this paper, we review the major tensor decomposition methods with a focus on problems targeted by classical PCA. In particular, we present tensor methods that aim to solve three important challenges typically addressed by PCA: dimensionality reduction, i.e., low-rank tensor approximation; supervised learning, i.e., learning linear subspaces for feature extraction; and robust low-rank tensor recovery. We also provide experimental results to compare different tensor models for both dimensionality reduction and supervised learning applications.

Advances in information technology are making it possible to collect increasingly massive amounts of multidimensional, multi-modal neuroimaging data such as functional magnetic resonance imaging (fMRI). Current fMRI datasets involve multiple variables including multiple subjects, as well as both temporal and spatial data. These high dimensional datasets pose a challenge to the signal processing community to develop data reduction methods that can exploit their rich structure and extract meaningful summarizations. In this paper, we propose a tensor-based framework for data reduction and low-dimensional structure learning with a particular focus on reducing high dimensional fMRI data sets into physiologically meaningful network components. We develop a multiscale tensor factorization method for higher order data inspired by hybrid linear modeling and subspace clustering techniques. In particular, we develop a multi-scale HoSVD approach where a given tensor is first permuted and then partitioned into several sub-tensors each of which can be represented more efficiently. This multi-scale framework is applied to resting state fMRI data to identify the default mode network from compressed data.

We develop a fast phase retrieval method which can utilize a large class of local phaseless correlation-based measurements in order to recover a given signal ${\bf x} \in \mathbb{C}^d$ (up to an unknown global phase) in near-linear $\mathcal{O} ( d \log^4 d )$-time. Accompanying theoretical analysis proves that the proposed algorithm is guaranteed to deterministically recover all signals ${\bf x}$ satisfying a natural flatness (i.e., nonsparsity) condition for a particular choice of deterministic correlation-based measurements. A randomized version of these same measurements is then shown to provide nonuniform probabilistic recovery guarantees for arbitrary signals ${\bf x} \in \mathbb{C}^d$. Numerical experiments demonstrate the method's speed, accuracy, and robustness in practice---all code is made publicly available. In its simplest form, our proposed phase retrieval method employs a modified lifting scheme akin to the one utilized by the well-known PhaseLift algorithm. In particular, it interprets quadratic magnitude measurements of ${\mathbf x}$ as linear measurements of a restricted set of lifted variables, $x_i \overline{x_j}$, for $| j - i | < \delta \ll d$. This leads to a linear system involving a total of $(2 \delta-1)d$ unknown lifted variables, all of which can then be solved for using only $\mathcal{O}(\delta d)$ measurements. Once these lifted variables, $x_i \overline{x_j}$ for $| j - i | < \delta \ll d$, have been recovered, a fast angular synchronization method can then be used to propagate the local phase difference information they provide across the entire vector in order to estimate the (relative) phases of every entry of ${\mathbf x}$. In addition, the lifted variables corresponding to $x_j \overline{x_j} = |x_j|^2$ automatically provide magnitude estimates for each entry, $x_j$, of ${\mathbf x}$. The proposed phase retrieval method then approximates ${\mathbf x}$ by carefully combining these entrywise phase and magnitude estimates. Finally, we conclude by developing an extension of the proposed method to the sparse phase retrieval problem; specifically, we demonstrate a sublinear-time compressive phase retrieval algorithm which is guaranteed to recover a given $s$-sparse vector ${\bf x} \in \mathbb{C}^d$ with high probability in just $\mathcal{O}(s \log^5 s \cdot \log d)$-time using only $\mathcal{O}(s \log^4 s \cdot \log d)$ magnitude measurements. In doing so we demonstrate the existence of compressive phase retrieval algorithms with near-optimal linear-in-sparsity runtime complexities.

We investigate the problem of decoding a bar code from a signal measured with a hand-held laser-based scanner. Rather than formulating the inverse problem as one of binary image reconstruction, we instead incorporate the symbology of the bar code into the reconstruction algorithm directly, and search for a sparse representation of the Universal Product Code bar code with respect to this known dictionary. Our approach significantly reduces the degrees of freedom in the problem, allowing for accurate reconstruction that is robust to noise and unknown parameters in the scanning device. We propose a greedy reconstruction algorithm and provide robust reconstruction guarantees. Numerical examples illustrate the insensitivity of our symbology-based reconstruction to both imprecise model parameters and noise on the scanned measurements.

Data sets are often modeled as samples from some probability distribution lying in a very high dimensional space. In practice, they tend to exhibit low intrinsic dimensionality, which enables both fast construction of efficient data representations and solving statistical tasks such as regression of functions on the data, or even estimation of the probability distribution from which the data is generated. In this paper we introduce a novel multiscale density estimator for high dimensional data and apply it to the problem of detecting changes in the distribution of dynamic data, or in a time series of data sets. We also show that our data representations, which are not standard sparse linear expansions, are amenable to compressed measurements. Finally, we test our algorithms on both synthetic data and a real data set consisting of a times series of hyperspectral images, and demonstrate their high accuracy in the detection of anomalies.

Current state-of-the-art association rule-based classifiers for gene expression data operate in two phases: (i) Association rule mining from training data followed by (ii) Classification of query data using the mined rules. In the worst case, these methods require an exponential search over the subset space of the training data set's samples and/or genes during at least one of these two phases. Hence, existing association rule-based techniques are prohibitively computationally expensive on large gene expression datasets. Our main result is the development of a heuristic rule-based gene expression data classifier called Boolean Structure Table Classification (BSTC). BSTC is explicitly related to association rule-based methods, but is guaranteed to be polynomial space/time. Extensive cross validation studies on several real gene expression datasets demonstrate that BSTC retains the classification accuracy of current association rule-based methods while being orders of magnitude faster than the leading classifier RCBT on large datasets. As a result, BSTC is able to finish table generation and classification on large datasets for which current association rule-based methods become computationally infeasible. BSTC also enjoys two other advantages over association rule-based classifiers: (i) BSTC is easy to use (requires no parameter tuning), and (ii) BSTC can easily handle datasets with any number of class types. Furthermore, in the process of developing BSTC we introduce a novel class of Boolean association rules which have potential applications to other data mining problems.

This project aims to reduce the time required to attain more detailed scans of small interesting regions present in a quick first-pass sample image. In particular, we concentrate on high fidelity imaging of small sample features via hyperspectral Raman imaging (e.g., small scale compositional variations in bone tissue). The current standard procedure for high quality hyperspectral Raman imaging of small sample features consists of four steps: first-pass imaging, detail identification, planning, and finally detail imaging. traditionally, detail imaging and planning have been carried out manually by human personnel - after acquiring some quick low-quality data in first-pass imaging, a researcher looks for interesting features (detail identification) and decides how to acquire higher-quality data for the interesting features (planning), which is done in the final detail imaging phase. In this paper we discuss automating the detail identification and planning steps, resulting in a decrease of the procedure's total integration time. We fix an arbitrary way to automate detail identification and compare several different planning methods. Our primary result is a method guaranteed to return a least cost (e.g., minimum integration time/number of scans) detail image under a general cost model. Because of their generality, the methodologies developed here may prove widely useful to basic biomedical scientists as well as to researchers in the pharmaceutical industry.

Significant advances in plan synthesis under classical assumptions have occurred in the last seven years. Such efficient planners are all centralized planners. One very major development among these is the Graphplan planner. Its popularity is clear from its several efficient adaptations/extensions. Since several practical planning problems are solved in a distributed manner it is important to adapt Graphplan to distributed planning. This involves dealing with significant challenges like decomposing the goal and set of actions without losing completeness. We report two sound two-agent planners DGP (distributed Graphplan) and IG-DGP (interaction graph-based DGP). Decomposition of goal and action set in DGP is carried out manually and in IG-DGP it is carried out automatically based on a new representation called interaction graphs. Our empirical evaluation shows that both these distributed planners are faster than Graphplan. IG-DGP is orders of magnitude faster than Graphplan. IG-DGP benefits significantly from interaction graphs which allow decomposition of a problem into fully independent subproblems under certain conditions. IG-DGP is a hybrid planner in which a centralized planner processes a problem until it becomes separable into two independent subproblems that are passed to a distributed planner This paper also shows that advances in centralized planning can significantly benefit distributed planners.

SAT-based planners have been characterized as disjunctive planners that maintain a compact representation of search space of action sequences. Several ideas from refinement planners (conjunctive planners) have been used to improve performance of SAT-based planners or get a better understanding of planning as SAT One important lesson from refinement planning is that backward search being goal directed can be more efficient than forward search. Another lesson is that bidirectional search is generally not efficient. This is because the forward and backward searches can miss each other Though effect of direction of plan refinement (forward, backward, bidirectional etc.) on efficiency of plan synthesis has been deeply investigated in refinement planning, the effect of directional solving of SAT encodings is not investigated in depth. We solved several propositional encodings of benchmark planning problems with a modified form (DSatz) of the systematic SAT solver Satz. DSatz offers 21 options for solving a SAT encoding of a planning problem, where the options are about assigning truth values to action and/or fluent variables in forward or backward or both directions, in an intermittent or non-intermittent style. Our investigation shows that backward search on plan encodings (assigning values to fluent variables first, starting with goal) is very inferior We also show bidirectional solving options and forward solving options turn out to be far more efficient than other solving options. Our empirical results show that the efficient systematic solver Satz which exploits variable dependencies call be significantly enhanced with use of our variable ordering heuristics which are also computationally very cheap to apply. Our main results are that directionality does matter in solving SAT encodings of planning problems and that certain directional solving options are superior to others.