skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: FRAPPE: fast rank approximation with explainable features for tensors
Abstract Tensor decompositions have proven to be effective in analyzing the structure of multidimensional data. However, most of these methods require a key parameter: the number of desired components. In the case of the CANDECOMP/PARAFAC decomposition (CPD), the ideal value for the number of components is known as the canonical rank and greatly affects the quality of the decomposition results. Existing methods use heuristics or Bayesian methods to estimate this value by repeatedly calculating the CPD, making them extremely computationally expensive. In this work, we proposeFRAPPE, the first method to estimate the canonical rank of a tensor without having to compute the CPD. This method is the result of two key ideas. First, it is much cheaper to generate synthetic data with known rank compared to computing the CPD. Second, we can greatly improve the generalization ability and speed of our model by generating synthetic data that matches a given input tensor in terms of size and sparsity. We can then train a specialized single-use regression model on a synthetic set of tensors engineered to match a given input tensor and use that to estimate the canonical rank of the tensor—all without computing the expensive CPD.FRAPPEis over$$24\times $$ 24 × faster than the best-performing baseline, and exhibits a$$10\%$$ 10 % improvement in MAPE on a synthetic dataset. It also performs as well as or better than the baselines on real-world datasets.  more » « less
Award ID(s):
2112650
PAR ID:
10544398
Author(s) / Creator(s):
;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Data Mining and Knowledge Discovery
Volume:
38
Issue:
6
ISSN:
1384-5810
Format(s):
Medium: X Size: p. 4217-4232
Size(s):
p. 4217-4232
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract The electricE1 and magneticM1 dipole responses of the$$N=Z$$ N = Z nucleus$$^{24}$$ 24 Mg were investigated in an inelastic photon scattering experiment. The 13.0 MeV electrons, which were used to produce the unpolarised bremsstrahlung in the entrance channel of the$$^{24}$$ 24 Mg($$\gamma ,\gamma ^{\prime }$$ γ , γ ) reaction, were delivered by the ELBE accelerator of the Helmholtz-Zentrum Dresden-Rossendorf. The collimated bremsstrahlung photons excited one$$J^{\pi }=1^-$$ J π = 1 - , four$$J^{\pi }=1^+$$ J π = 1 + , and six$$J^{\pi }=2^+$$ J π = 2 + states in$$^{24}$$ 24 Mg. De-excitation$$\gamma $$ γ rays were detected using the four high-purity germanium detectors of the$$\gamma $$ γ ELBE setup, which is dedicated to nuclear resonance fluorescence experiments. In the energy region up to 13.0 MeV a total$$B(M1)\uparrow = 2.7(3)~\mu _N^2$$ B ( M 1 ) = 2.7 ( 3 ) μ N 2 is observed, but this$$N=Z$$ N = Z nucleus exhibits only marginalE1 strength of less than$$\sum B(E1)\uparrow \le 0.61 \times 10^{-3}$$ B ( E 1 ) 0.61 × 10 - 3  e$$^2 \, $$ 2 fm$$^2$$ 2 . The$$B(\varPi 1, 1^{\pi }_i \rightarrow 2^+_1)/B(\varPi 1, 1^{\pi }_i \rightarrow 0^+_{gs})$$ B ( Π 1 , 1 i π 2 1 + ) / B ( Π 1 , 1 i π 0 gs + ) branching ratios in combination with the expected results from the Alaga rules demonstrate thatKis a good approximative quantum number for$$^{24}$$ 24 Mg. The use of the known$$\rho ^2(E0, 0^+_2 \rightarrow 0^+_{gs})$$ ρ 2 ( E 0 , 0 2 + 0 gs + ) strength and the measured$$B(M1, 1^+ \rightarrow 0^+_2)/B(M1, 1^+ \rightarrow 0^+_{gs})$$ B ( M 1 , 1 + 0 2 + ) / B ( M 1 , 1 + 0 gs + ) branching ratio of the 10.712 MeV$$1^+$$ 1 + level allows, in a two-state mixing model, an extraction of the difference$$\varDelta \beta _2^2$$ Δ β 2 2 between the prolate ground-state structure and shape-coexisting superdeformed structure built upon the 6432-keV$$0^+_2$$ 0 2 + level. 
    more » « less
  2. Abstract Let us fix a primepand a homogeneous system ofmlinear equations$$a_{j,1}x_1+\dots +a_{j,k}x_k=0$$ a j , 1 x 1 + + a j , k x k = 0 for$$j=1,\dots ,m$$ j = 1 , , m with coefficients$$a_{j,i}\in \mathbb {F}_p$$ a j , i F p . Suppose that$$k\ge 3m$$ k 3 m , that$$a_{j,1}+\dots +a_{j,k}=0$$ a j , 1 + + a j , k = 0 for$$j=1,\dots ,m$$ j = 1 , , m and that every$$m\times m$$ m × m minor of the$$m\times k$$ m × k matrix$$(a_{j,i})_{j,i}$$ ( a j , i ) j , i is non-singular. Then we prove that for any (large)n, any subset$$A\subseteq \mathbb {F}_p^n$$ A F p n of size$$|A|> C\cdot \Gamma ^n$$ | A | > C · Γ n contains a solution$$(x_1,\dots ,x_k)\in A^k$$ ( x 1 , , x k ) A k to the given system of equations such that the vectors$$x_1,\dots ,x_k\in A$$ x 1 , , x k A are all distinct. Here,Cand$$\Gamma $$ Γ are constants only depending onp,mandksuch that$$\Gamma Γ < p . The crucial point here is the condition for the vectors$$x_1,\dots ,x_k$$ x 1 , , x k in the solution$$(x_1,\dots ,x_k)\in A^k$$ ( x 1 , , x k ) A k to be distinct. If we relax this condition and only demand that$$x_1,\dots ,x_k$$ x 1 , , x k are not all equal, then the statement would follow easily from Tao’s slice rank polynomial method. However, handling the distinctness condition is much harder, and requires a new approach. While all previous combinatorial applications of the slice rank polynomial method have relied on the slice rank of diagonal tensors, we use a slice rank argument for a non-diagonal tensor in combination with combinatorial and probabilistic arguments. 
    more » « less
  3. Abstract We consider the problem of covering multiple submodular constraints. Given a finite ground setN, a weight function$$w: N \rightarrow \mathbb {R}_+$$ w : N R + ,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$ f 1 , f 2 , , f r overNand requirements$$k_1,k_2,\ldots ,k_r$$ k 1 , k 2 , , k r the goal is to find a minimum weight subset$$S \subseteq N$$ S N such that$$f_i(S) \ge k_i$$ f i ( S ) k i for$$1 \le i \le r$$ 1 i r . We refer to this problem asMulti-Submod-Coverand it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$ r = 1 Multi-Submod-Covergeneralizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced toSubmod-SC. A simple greedy algorithm gives an$$O(\log (kr))$$ O ( log ( k r ) ) approximation where$$k = \sum _i k_i$$ k = i k i and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$ ( 1 - 1 / e - ε ) while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$ O ( 1 ϵ log r ) in the cost. Second, we consider the special case when each$$f_i$$ f i is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC), covering integer programs (CIPs) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems. 
    more » « less
  4. Abstract Low-lying states in$$^{54}$$ 54 Cr have been investigated via the$$\alpha $$ α -transfer reaction$$^{50}$$ 50 Ti($$^{7}$$ 7 Li,t) at a bombarding energy of 20 MeV. The exclusive$$\alpha $$ α -transfer channel is separated from other reaction channels through the appropriate energy gate on the complementary particle, triton. Levels of$$^{54}$$ 54 Cr populated exclusively by the$$\alpha $$ α -transfer process could be identified up to$$\approx $$ 5 MeV excitation energy and angular momentum up to$$(8)^{+}$$ ( 8 ) + , by identifying the corresponding known$$\gamma $$ γ -rays. These include multiple low-lying non-yrast 2$$^+$$ + and 4$$^+$$ + states, which would otherwise be unfavorable via fusion evaporation reactions. The feeding-subtracted$$\gamma $$ γ -ray yields have been extracted to estimate the population of various excited states through the transfer process. The measured integrated transfer cross sections for all the observed yrast and non-yrast states are compared with Coupled Channels calculations usingfrescoto extract the$$\alpha $$ α +$$^{50}$$ 50 Ti core spectroscopic factors. For the yrast states, a higher$$\alpha $$ α +core overlap is seen for the$$2^+$$ 2 + and$$4^+$$ 4 + states, while it is seen to be less favorable for the$$6^+$$ 6 + and$$(8)^+$$ ( 8 ) + states when$$\alpha $$ α -transfer is considered to occur predominantly as a direct one-step process to the$$^{50}$$ 50 Ti core ground state. The yrast$$2^+$$ 2 + , and$$4^+$$ 4 + states are predominantly populated by single-step transfer, while for the states with spin$$\ge $$ 5, the possibility of core excitation followed by$$\alpha $$ α -transfer shows a larger$$\alpha $$ α -core overlap. For the non-yrast$$0^+$$ 0 + ,$$2^+$$ 2 + , and$$4^+$$ 4 + states, single-step transfer shows moderate to small$$\alpha $$ α -core overlap. No higher spin non-yrast states are observed. 
    more » « less
  5. Abstract We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the$$\ell _0$$ 0 -norm of the vector. Our main results are new improved bounds on the minimal$$\ell _0$$ 0 -norm of solutions to systems$$A\varvec{x}=\varvec{b}$$ A x = b , where$$A\in \mathbb {Z}^{m\times n}$$ A Z m × n ,$${\varvec{b}}\in \mathbb {Z}^m$$ b Z m and$$\varvec{x}$$ x is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with$$\ell _0$$ 0 -norm satisfying the obtained bounds. We show that our bounds are tight. Our bounds can be seen as functions naturally generalizing the rank of a matrix over$$\mathbb {R}$$ R , to other subdomains such as$$\mathbb {Z}$$ Z . We show that these new rank-like functions are all NP-hard to compute in general, but polynomial-time computable for fixed number of variables. 
    more » « less