An official website of the United States government
Tensor decomposition models have proven to be effective analysis tools in various applications, including signal processing, machine learning, and communications, to name a few. Canonical polyadic decomposition (CPD) is a very popular model, which decomposes a higher order tensor signal into a sum of rank 1 terms. However, when the tensor size gets big, computing the CPD becomes a lot more challenging. Previous works proposed using random (generalized) tensor sampling or compression to alleviate this challenge. In this work, we propose using a regular tensor sampling framework instead. We show that by appropriately selecting the sampling mechanism, we can simultaneously control memory and computational complexity, while guaranteeing identifiability at the same time. Numerical experiments with synthetic and real data showcase the effectiveness of our approach.
more »
« less
NLS Algorithm for Kronecker-Structured Linear Systems with a CPD Constrained Solution
In various applications within signal processing, system identification, pattern recognition, and scientific computing, the canonical polyadic decomposition (CPD) of a higher-order tensor is only known via general linear measurements. In this paper, we show that the computation of such a CPD can be reformulated as a sum of CPDs with linearly constrained factor matrices by assuming that the measurement matrix can be approximated by a sum of a (small) number of Kronecker products. By properly exploiting the hypothesized structure, we can derive an efficient non-linear least squares algorithm, allowing us to tackle large-scale problems.
more »
« less
- Award ID(s):
- 1704074
- PAR ID:
- 10169186
- Date Published:
- Journal Name:
- 27th European Signal Processing Conference (EUSIPCO), A Coruna, Spain, 2019
- Page Range / eLocation ID:
- 1 to 5
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Photochemical dimerization of adjacent pyrimidines is fundamental to the creation of mutagenic hotspots caused by ultraviolet light. Distribution of the resulting lesions (cyclobutane pyrimidine dimers, CPDs) is already known to be highly variable in cells, and in vitro models have implicated DNA conformation as a major basis for this observation. Past efforts have primarily focused on mechanisms that influence CPD formation and have rarely considered contributions of CPD reversion. However, reversion is competitive under the standard conditions of 254 nm irradiation as illustrated in this report based on the dynamic response of CPDs to changes in DNA conformation. A periodic profile of CPDs was recreated in DNA held in a bent conformation by λ repressor. After linearization of this DNA, the CPD profile relaxed to its characteristic uniform distribution over a similar time of irradiation to that required to generate the initial profile. Similarly, when a T tract was released from a bent conformation, its CPD profile converted under further irradiation to that consistent with a linear T tract. This interconversion of CPDs indicates that both its formation and reversion exert control on CPD populations long before photo-steady-state conditions are achieved and suggests that the dominant sites of CPDs will evolve as DNA conformation changes in response to natural cellular processes.more » « less
-
Given a sequence of random graphs, we address the problem of online monitoring and detection of changes in the underlying data distribution. To this end, we adopt the Random Dot Product Graph (RDPG) model which postulates each node has an associated latent vector, and inner products between these vectors dictate the edge formation probabilities. Existing approaches for graph change-point detection (CPD) rely either on extensive computation, or they store and process the entire observed time series. In this paper we consider the cumulative sum of a judicious monitoring function, which quantifies the discrepancy between the streaming graph observations and the nominal model. This reference distribution is inferred via spectral embeddings of the first few graphs in the sequence, and the monitoring function can be updated in an efficient, online fashion. We characterize the distribution of this running statistic, allowing us to select appropriate thresholding parameters that guarantee error-rate control. The end result is a lightweight online CPD algorithm, with a proven capability to flag distribution shifts in the arriving graphs. The novel method is tested on both synthetic and real network data, corroborating its effectiveness in quickly detecting changes in the input graph sequence.more » « less
-
Abstract Spatiotemporally functionalized hydrogels have exciting applications in tissue engineering, but their preparation often relies on radical‐based strategies that can be deleterious in biological settings. Herein, the computationally guided design, synthesis, and application of a water‐soluble cyclopentadienone‐norbornadiene (CPD‐NBD) adduct is disclosed as a diene photocage for radical‐free Diels‐Alder photopatterning. We show that this scalable CPD‐NBD derivative is readily incorporated into hydrogel formulations, providing gels that can be patterned with dienophiles upon 365 nm uncaging of cyclopentadiene. Patterning is first visualized through conjugation of cyanine dyes, then biological utility is highlighted by patterning peptides to direct cellular adhesion. Finally, the ease of use and versatility of this CPD‐NBD derivative is demonstrated by direct incorporation into a commercial 3D printing resin to enable the photopatterning of structurally complex, printed hydrogels.more » « less
-
We address the problem of slowdown caused by straggling nodes in distributed non-linear computations. Many common non-linear computations can be written as a sum of inexpensive non-linear functions (e.g. Taylor series). Based on this observation, we propose a new class of rateless codes called rateless sum-recovery codes whose aim is to recover the sum of source symbols, without necessarily recovering individual symbols. Source symbols correspond to individual inexpensive functions and each encoded symbol is the sum of a subset of source symbols. Encoded symbols are computed in a distributed fashion and for a computation that can be written as a sum of m inexpensive functions, successful sum-recovery is possible with high probability as long as slightly more than m encoded symbols are received. Our code is rateless, systematic and has sparse parities. Moreover, encoded symbols are constructed by sampling without replacement at individual nodes, thereby making decoding superfluous if the encoded symbols from any node cover all source symbols. We validate our claims through a range of simulations and also discuss open questions for future works.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.23919/EUSIPCO.2019.8902816
