# Erdős–Hajnal problem for $H$‐free hypergraphs

Danila Cherkashin, Alexey Gordeev, Georgii Strukov11footnotemark: 1 The work
was supported by the Foundation for the Advancement of Theoretical Physics and
Mathematics ‘‘BASIS’’.

###### Abstract

This paper deals with the minimum number $m_{H}(r)$ of edges in an $H$-free
hypergraph with the chromatic number more than $r$. We show how bounds on
Ramsey and Turán numbers imply bounds on $m_{H}(r)$.

##  1 Introduction

A hypergraph $G=(V,E)$ consists of a finite set of vertices $V$ and a family
$E$ of subsets of $V$, which are called edges. A hypergraph $G$ is called
$n$-graph if every edge in $G$ has size $n$. A vertex $r$-coloring of a
hypergraph $G=(V,E)$ is a map from $V$ to $\\{1,\dots,r\\}$. A coloring is
proper if there are no monochromatic edges, i.e. any edge $g\in E$ contains
two vertices of different colors. The chromatic number of a hypergraph $G$ is
the smallest number $\chi(G)$ such that there exists a proper
$\chi(G)$-coloring of $G$. A vertex subset is independent in $G$ if it does
not contain an edge of $G$. The independence number of $G$ is the maximal size
$\alpha(G)$ of an independent set.

Although the subjects are defined and studied for $n$-graphs, this paper deals
with 3-graphs only. For convenience, we restrict cited results on 3-graphs
despite most of them being more general.

Let us start with best known bounds for 3-graphs without restrictions. Let
$m(r)$ be the smallest number of edges in a 3-graph with the chromatic number
at least $r+1$. Then

$(1+o(1))\frac{4}{e^{2}}r^{3}\leq
m(r)\leq\binom{2r+1}{3}=(1+o(1))\frac{4}{3}r^{3},$

see [2] for details. See also the survey on related problems on $n$-graphs
[10].

A subgraph of a 3-graph $G=(V,E)$ is a 3-graph
$G^{\prime}=(V^{\prime},E^{\prime})$, where $V^{\prime}\subset V$,
$E^{\prime}\subset E$ and $E^{\prime}\subset\binom{V^{\prime}}{3}$. An induced
subgraph of a 3-graph $G=(V,E)$ is a 3-graph $G[V^{\prime}]$, formed from a
vertex set $V^{\prime}\subset V$ and all of the edges from $G$ contained in
$V^{\prime}$. An $H$-free 3-graph is a 3-graph that does not contain $H$ as a
subgraph.

Bohman, Frieze and Mubayi [1] introduced the quantity $m_{H}(r)$, which is the
minimal number of edges in an $H$-free 3-graph with chromatic number more than
$r$. First of all, note that sometimes $m_{H}(r)$ is undefined. More
precisely, this is the case iff $H$ is a hyperforest, i.e. every two edges of
$H$ share at most one vertex and $H$ has no cycles. We discuss it with more
details later.

##### Structure of the paper.

The rest of the introduction is devoted to the known results, our contribution
and classical tools. Subsection 1.1 contains known bounds on $m_{H}(r)$,
mostly from paper [1]. Our results are listed in Subsection 1.2, where we show
some relations $m_{H}(r)$ has with Ramsey and Turán numbers. The tools which
we use in proofs of these relations are recalled in Subsection 1.3. The
correctness of the definition of $m_{H}(r)$ is discussed in Subsection 1.4. In
Section 2 we give proofs of the results. In Section 3 we list some open
questions.

###  1.1 Known bounds

######  Definition 1.

Let $H$ be a 3-graph. Define the balance $\rho(H)$ of $H$ as follows

$\rho(H):=\max_{H^{\prime}}\frac{e^{\prime}-1}{v^{\prime}-3},$

where $H^{\prime}$ is a (nonempty) subgraph of $H$ with $v^{\prime}$ vertices
and $e^{\prime}$ edges. We say that $H$ is balanced if this maximum occurs for
$H$.

######  Theorem 1 ([1]).

If $H$ is a balanced 3-graph with $\rho(H)>\frac{1}{2}$, then

$m_{H}(r)=O\left((r^{2}\log r)^{\frac{3\rho-1}{2\rho-1}}\right).$

In the following case an $H$-free 3-graph is also called a simple or linear
3-graph.

######  Theorem 2 ([7, 1]).

Let $H$ be the 3-graph on 4 vertices with the set of edges
$\\{\\{1,2,3\\},\\{1,2,4\\}\\}$, then

$m_{H}(r)=\theta\left(r^{4}\log^{2}r\right).$

In the following case an $H$-free 3-graph is also known as a graph with
independent neighbourhoods. The upper bound is a corollary of Theorem 1.

######  Theorem 3 ([1]).

Let $H$ be the 3-graph on 5 vertices with the set of edges
$\\{\\{1,2,3\\},\\{1,2,4\\},\\{1,2,5\\},\\{3,4,5\\}\\}$, then

$cr^{\frac{7}{2}}\leq m_{H}(r)\leq Cr^{\frac{7}{2}}\log^{\frac{7}{4}}r.$

Hypergraph $H$ in the following theorem is also known as $K^{3}_{4}$; further
we denote it by $K_{4}$ since we have a deal with 3-graphs only.

######  Theorem 4 ([1]).

Let $H$ be the 3-graph on 4 vertices with the set of edges
$\\{\\{1,2,3\\},\\{1,2,4\\},\\{1,3,4\\},\\{2,3,4\\}\\}$, then

$m_{H}(r)=O\left(r^{3}\log^{3}r\right).$

###  1.2 Results

####  1.2.1 Relation with Ramsey numbers

A Ramsey number $R(H,K_{t})$ is the minimal number of vertices in a 3-graph
$G$ that guarantees existence of a copy of $H$ or an independent set on $t$
elements in $G$. We show that bounds on Ramsey numbers imply bounds on
$m_{H}(r)$.

######  Theorem 5.

Consider a 3-graph $H$. Let $a,b>1$ and $A,B>0$ be numbers such that for all
$t\geq 1$

$At^{a}<R(H,K_{t})\leq Bt^{b}.$ (1)

Then for all $r\geq 1$

$B^{\prime}r^{\frac{b}{b-1}+2}\leq m_{H}(r)\leq A^{\prime}r^{\frac{3a}{a-1}},$
(2)

where

$A^{\prime}=\frac{(1+o(1))^{3a}}{6A^{\frac{3}{a-1}}},\qquad
B^{\prime}=\left(\frac{(1-2^{1-b})}{2^{\frac{b}{b-1}+b+3}(12e)^{b-1}B\bigl{(}\frac{b}{b-1}+2\bigr{)}^{b}}\right)^{1/(b-1)}.$
(3)

In [8] it was shown that for all $t\geq 1$

$\frac{at^{3/2}}{(\log t)^{3/4}}\leq R(C_{3},K_{t})\leq bt^{3/2},$ (4)

where $C_{3}$ is a loose cycle with 3 edges, i.e. the 3-graph on 6 vertices
with the set of edges $\\{\\{1,2,3\\},\\{3,4,5\\},\\{5,6,1\\}\\}$, and $a,b>0$
are some constants. A straightforward application of Theorem 5 gives

######  Corollary 1.

There is a constant $C>0$ such that for all $r\geq 1$

$Cr^{5}\leq m_{C_{3}}(r).$ (5)

However, the upper bound can be made more precise than the one implied by
Theorem 5.

######  Proposition 1.

There is a constant $C>0$ such that for all $r\geq 1$

$m_{C_{3}}(r)\leq Cr^{5}(\ln r)^{5/2}.$ (6)

######  Theorem 6.

Suppose that for a 3-graph $H$ and some constants $A,B>0$ and $b>1$ we have

$t^{At}<R(H,K_{t})\leq t^{Bt^{b}}.$ (7)

Then

$r^{3}\ln^{1/b-o(1)}r\leq
m_{H}(r)\leq(1+o(1))\frac{8}{A^{3}}r^{3}\left(\frac{\ln r}{\ln\ln
r}\right)^{3}.$ (8)

Let $K_{4}^{-}$ be the 3-graph with four vertices and three edges. In [5] it
was stated that

$R(K_{4}^{-},K_{t})=t^{\Theta(t)}.$ (9)

Then Theorem 6 immediately yields

######  Corollary 2.

For some constant $C>0$,

$r^{3}\ln^{1-o(1)}r\leq m_{K_{4}^{-}}(r)\leq Cr^{3}\left(\frac{\ln r}{\ln\ln
r}\right)^{3}.$ (10)

The following bounds are from [4]:

$2^{c_{1}n\log n}\leq R(K_{4},K_{n})\leq 2^{c_{2}n^{2}\log n}$ (11)

for some constants $c_{1},c_{2}>0$ and any sufficiently large $n$. A direct
application of Theorem 6 gives

######  Corollary 3.

For some constant $C>0$,

$r^{3}\ln^{1/2-o(1)}r\leq m_{K_{4}}(r)\leq Cr^{3}\left(\frac{\ln r}{\ln\ln
r}\right)^{3}.$ (12)

Moreover, using the same idea of graph reduction by coloring some big
independent set in the same color, as in proof of theorems of this section
(but with much less effort), we obtain

######  Proposition 2.

Let $H$ be the hypergraph on 7 vertices with the set of edges
$\\{\\{1,2,3\\},\\{1,4,5\\},\\{1,6,7\\},\\{2,4,6\\}\\}$. Then

$m_{H}(r)>Cr^{4},$ (13)

where $C=e/288$.

####  1.2.2 Relation with Turán numbers

A Turán number $\mathrm{ex}(n,H)$ is the maximum number of edges in an
$H$-free 3-graph with $n$ vertices. As with Ramsey numbers, we can obtain
bounds for $m_{H}(r)$ from bounds on Turán numbers.

######  Theorem 7.

Let $H$ be a 3-graph and let $C_{1}>0$ be a constant such that for all $n\geq
1$

$\mathrm{ex}(n,H)\leq C_{1}n^{b}.$ (14)

Then for any constant $C_{2}>0$ there exists some $R=R(C_{2})$ such that for
any $r>R$

$m_{H}(r)>\frac{C_{2}r^{\frac{2b}{b-1}}}{(\ln\ln r)^{1+\frac{2b}{b-1}}}.$ (15)

The following proposition is folklore.

######  Proposition 3.

Let $H$ be a 3-graph, such that $t=|V(H)|=|E(H)|+2$. Suppose that there is an
ordering of edges $h_{1},\dots,h_{t-2}$ such that
$h_{i}=\\{a_{i},b_{i},c_{i}\\}$ for each $i>1$, where
$\\{a_{i},b_{i}\\}\subset h_{j(i)}$ for some ${j(i)}<i$ and $c_{i}\not\in
h_{j}$ for $j<i$. Then

$ex(n,H)\leqslant(t-3)\binom{n}{2}.$ (16)

Note that such a graph $H$ is balanced with balance $1$, so Theorems 7 and 1
give

######  Corollary 4.

Suppose that 3-graph $H$ satisfies the conditions of Proposition 3. Then for
some positive constants $C_{1},C_{2}>0$ and for any sufficiently large $r$

$C_{1}\frac{r^{4}}{(\ln\ln r)^{5}}<m_{H}(r)<C_{2}r^{4}(\ln r)^{2}.$ (17)

###  1.3 Tools

####  1.3.1 Applications of LLL

We are going to use the following classical technique.

######  Lemma 1 (Symmetric Lovász local lemma).

Let $A_{1},\ldots,A_{n}$ be events with probabilities $\mathbf{P}(A_{i})\leq
p$ for $1\leq i\leq n$. Suppose that each event $A_{i}$ is mutually
independent of all the other events except at most $d$ of them. If
$ep(d+1)<1$, then $\mathbf{P}(\wedge_{i=1}^{n}\overline{A}_{i})>0$.

The following lemma is a folklore corollary of Lemma 1.

######  Lemma 2.

Let $G$ be a 3-graph. Let $r>0$ be some integer. Suppose that for every $v\in
V(G)$

$\deg v\leq\Delta=\frac{r^{2}}{3e}.$ (18)

Then $G$ can be properly colored with $r$ colors.

###### Proof.

Let us assign to each vertex one of $r$ colors at random uniformly and
independently. For each $f\in E$ consider an event $A_{f}=\text{``$f\in E$ is
monocromatic''}$. The probability of such event is $1/r^{2}=:p$. Clearly each
event $A_{f}$ is independent of $\\{A_{g}\colon f\cap g=\emptyset\\}$. There
are at most $3(\Delta-1)+1<3\Delta$ events (including $A_{f}$ itself) that are
not in this family, so

$ep(d+1)<\frac{3e\Delta}{r^{2}}=1,$ (19)

and, by Lemma 1, $G$ has some coloring in $r$ colors with no monochromatic
edges. ∎

Lemma 2 allows us to care only about vertices with big degree when we are
coloring some graph in $r$ colors. Let us make this statement more precise.

######  Definition 2.

Denote $c=(12e)^{-1}$. Consider an integer $r$ and a 3-graph $G$. Define

$V_{small}=\\{v\in V(G)\mid\deg v\leq cr^{2}\\},$ (20) $V_{big}=V(G)\setminus
V_{small}.$ (21)

By a direct application of Lemma 2 we obtain

######  Lemma 3.

Let $r$ be an integer and $G$ be a 3-graph. Then $G[V_{small}]$ is $\lceil
r/2\rceil$-colorable.

####  1.3.2 Greedy coloring

The following approach was introduced by Pluhár [9]. Let us consider an
arbitrary linear order $\pi$ on the vertex set of a given 3-graph $G$. Now one
can go through vertices in order $\pi$ and color each considered vertex into
the minimal color which does not create a monochromatic edge at this moment.
By the construction, the result is a proper coloring $f$ in some number of
colors.

Let an $r$-chain be a set of edges $g_{1},\dots,g_{r}$ such that $|g_{i}\cap
g_{j}|=1$ if $|i-j|=1$, and 0 otherwise. We say that an $r$-chain is ordered
in $\pi$ if $i<j$ implies that every vertex of $g_{i}$ is no bigger that every
vertex of $g_{j}$ with respect to $\pi$.

Pluhár noted that the number of colors in $f$ is the maximal size of an
ordered chain plus one. In particular, if $f$ uses more than $r$ colors, then
$G$ contains an $r$-chain (in fact, a lot of $r$-chains). Then Gyárfás and
Lehel [6] extended the latter statement as follows. If a greedy coloring of a
3-graph $G$ uses more than $r$ colors, then $G$ contains a copy of every
hypertree (connected hyperforest) with $r$ edges.

###  1.4 Correctness

We have claimed earlier that the function $m_{H}(r)$ is properly defined for
all $H$ except hyperforests. Here we provide a brief proof of this statement.
Indeed, if $H$ is a hyperforest, then, as was discussed in the previous
subsection, any $H$-free hypergraph can be properly colored in $|E(H)|$ colors
using greedy coloring method, so $m_{H}(r)$ is not defined for $r>|E(H)|$.

Otherwise, $H$ contains either a pair of edges intersecting by two vertices,
or a loose cycle $C_{l}$ for some $l\geq 3$, i.e. a 3-graph on $2l$ vertices
with the set of edges $\\{\\{1,2,3\\},\\{3,4,5\\},\dots,\\{2l-1,2l,1\\}\\}$.
In the first case any simple 3-graph is $H$-free, so, in view of Theorem 2,
$m_{H}(r)=O(r^{4}\log^{2}r)$. For a graph with a loose cycle $C_{l}$ one may
count the balance of the cycle as follows

$\rho(C_{l})=\frac{l-1}{2l-3}=\frac{1}{2}+\frac{1}{4l-6}.$

The maximum in the definition of the balance is achieved on the whole cycle,
so $C_{l}$ is balanced with the balance greater than $\frac{1}{2}$. Thus one
can apply Theorem 1 to obtain the inequality

$m_{H}(r)\leq m_{C_{l}}(r)=O\left((r^{2}\log
r)^{\frac{3\rho-1}{2\rho-1}}\right)=O(r^{2l}\log^{l}r).$

##  2 Proofs

###  2.1 Proof of Theorem 5

####  2.1.1 The upper bound

The lower bound on $R(H,K_{t})$ states that for each $t\geq 1$ there is an
$H$-free 3-graph $G$ with $|V(G)|=At^{a}$ and the independence number
$\alpha(G)<t$. The chromatic number of $G$ satisfies

$\chi(G)\geq\frac{|V(G)|}{\alpha(G)}\geq At^{a-1}.$ (22)

Now for a given $r$ we choose integer $t$ such that $A(t-1)^{a-1}\leq
r<At^{a-1}$. Then

$|E(G)|\leq\frac{|V(G)|^{3}}{6}=\frac{A^{3}t^{3a}}{6}=\frac{A^{3-\frac{3a}{a-1}}}{6}(At^{a-1})^{\frac{3a}{a-1}}<\frac{A^{3-\frac{3a}{a-1}}}{6}\biggl{(}A\Bigl{(}\bigl{(}1+o(1)\bigr{)}(t-1)\Bigr{)}^{a-1}\biggr{)}^{\frac{3a}{a-1}}\leq\frac{(1+o(1))^{3a}}{6A^{\frac{3}{a-1}}}\cdot
r^{\frac{3a}{a-1}}.$ (23)

####  2.1.2 The lower bound

Suppose that $G$ is an $H$-free 3-graph with
$|E(G)|<B^{\prime}r^{\frac{b}{b-1}+2}$ that is not $r$-colorable. Let such $r$
be minimal possible. From Lemma 3 it follows that $G[V_{big}]$ cannot be
colored with no more than $r/2$ colors. Then

$|E(G[V_{big}])|\geq\frac{B^{\prime}}{2^{\frac{b}{b-1}+2}}\cdot
r^{\frac{b}{b-1}+2},$ (24)

Let $V_{big}=V_{0}\cup V_{1}\cup V_{2}\cup\dots$, where

$V_{k}=\\{v\in V(G)\mid 2^{k}cr^{2}\leq\deg v<2^{k+1}cr^{2}\\},$ (25)

and $c=(12e)^{-1}$ is from the definition of $V_{big}$. Suppose there is some
$k$ for which

$\alpha(G[V_{k}])\geq\frac{B^{\prime}}{2^{k-1}cr^{2}}\bigl{(}r^{\frac{b}{b-1}+2}-(r-1)^{\frac{b}{b-1}+2}\bigr{)}.$
(26)

Then we can paint the vertices from a corresponding independent set in one
color. Now if we remove colored vertices from $G$, we get a 3-graph with less
than

$B^{\prime}r^{\frac{b}{b-1}+2}-\frac{1}{2}\cdot
2^{k}cr^{2}\cdot\alpha(G[V_{k}])=B^{\prime}(r-1)^{\frac{b}{b-1}+2}$ (27)

edges that is not $(r-1)$-colorable. That is in contradiction to the
minimality of $r$. So we can assume that for every $k$ the contrary of (26)
holds, so, by upper bound from (1), we have

$|V_{k}|<B\left(\frac{B^{\prime}}{2^{k-1}cr^{2}}\bigl{(}r^{\frac{b}{b-1}+2}-(r-1)^{\frac{b}{b-1}+2}\bigr{)}\right)^{b}.$
(28)

Using the fact that $x^{q}-(x-1)^{q}\leq qx^{q-1}$ for $x,q\geq 1$, we get

$|V_{k}|<B\left(\frac{B^{\prime}}{2^{k-1}cr^{2}}\cdot\biggl{(}\frac{b}{b-1}+2\biggr{)}\cdot
r^{\frac{b}{b-1}+1}\right)^{b}=C\left(\frac{r^{\frac{b}{b-1}+1}}{2^{k-1}r^{2}}\right)^{b}=\frac{1}{2^{b(k-1)}}\cdot
Cr^{\frac{b}{b-1}},$ (29)

where

$C=\frac{B{B^{\prime}}^{b}\bigl{(}\frac{b}{b-1}+2\bigr{)}^{b}}{c^{b}}.$ (30)

Now let $g_{k}$ be the number of edges that pass through vertices of $V_{k}$.
We have

$|E(G[V_{big}])|<\sum_{k\geq 0}g_{k}<\sum_{k\geq
0}2^{k+1}cr^{2}\cdot\frac{1}{2^{b(k-1)}}\cdot
Cr^{\frac{b}{b-1}}=cC2^{b+1}r^{\frac{b}{b-1}+2}\sum_{k\geq
0}2^{(1-b)k}<\frac{cC2^{b+1}}{1-2^{1-b}}\cdot r^{\frac{b}{b-1}+2}.$ (31)

Combining this with (24) and substituting $C$ and $c$ we get

$\frac{B^{\prime}}{2^{\frac{b}{b-1}+2}}<\frac{(1/12e)B{B^{\prime}}^{b}\bigl{(}\frac{b}{b-1}+2\bigr{)}^{b}2^{b+1}}{(1/12e)^{b}(1-2^{1-b})}$
(32)

or

${B^{\prime}}^{b-1}>\frac{(1-2^{1-b})}{2^{\frac{b}{b-1}+b+3}(12e)^{b-1}B\bigl{(}\frac{b}{b-1}+2\bigr{)}^{b}},$
(33)

which is a contradiction.

###  2.2 Proof of Proposition 1

A direct application of Theorem 5 gives the upper bound $r^{9+o(1)}$. To
obtain a better upper bound, let us count the number of edges in the example
constructed in [8]. The construction is as follows: let $G_{q}$ be a
generalized quadrangle, i.e. a $(q+1)$-regular $(q+1)$-uniform simple
$C_{3}$-free hypergraph on $q^{3}+q^{2}+q+1$ vertices. It is known that such
hypergraph exists whenever $q$ is a power of a prime number. Each edge of
$G_{q}$ is then replaced by a random 3-graph $F_{q}$ which is built as
follows: vertices of $F_{q}$ are randomly split into a set $V=\\{v_{ij}\ |\
1\leq i,j\leq\tau\\}$ and $2\tau$ sets
$S_{1},\dots,S_{\tau},T_{1},\dots,T_{\tau}$ of roughly the same size, where
$\tau=\lfloor 8\sqrt{\log q}\rfloor$. Edges of $F_{q}$ are all sets of the
form $\\{v_{ij},a,b\\}$, where $a\in S_{i}$, $b\in T_{j}$.

The result of the construction is a hypergraph on $cq^{3}$ vertices. With a
high probability its independence number does not exceed

$\frac{2\tau n}{q}=16q^{2}\sqrt{\log q},$

i.e. its chromatic number is at least $cq/\sqrt{\log q}$.

At the same time, this hypergraph has

$cq^{3}\tau^{2}\left(\frac{q+1-\tau^{2}}{2\tau}\right)^{2}=cq^{5}$

edges. Substituting $cq/\sqrt{\log q}=r$, we get

$m_{C_{3}}(r)\leq cr^{5}(\log r)^{5/2}.$

###  2.3 Proof of Theorem 6

####  2.3.1 The upper bound

For any $t\geq 1$ there is a $H$-free 3-graph $G_{t}$ with $|V(G_{t})|=t^{At}$
and $\alpha(G_{t})<t$. Then

$\chi(G_{t})\geq\frac{|V(G_{t})|}{\alpha(G_{t})}>\frac{t^{At}}{t}=t^{At-1},$

so one may put $r=t^{At-1}$. First we prove the desired bound only for such
$r$. Hence

$\ln r=(At-1)\ln t,$

so

$\frac{1}{A}\frac{\ln r}{\ln\ln r}=\frac{1}{A}\frac{(At-1)\ln t}{\ln((At-1)\ln
t)}=(1+o(1))t.$

Finally,

$|E(G_{t})|\leq|V(G_{t})|^{3}=t^{3At}=r^{3}t^{3}=(1+o(1))\left(\frac{r\ln
r}{A\ln\ln r}\right)^{3}.$

Then, consider any $r$ between $(t-1)^{A(t-1)-1}$ and $t^{At-1}$. Let
$A^{\prime}$ be such that $r=t^{A^{\prime}t-1}$. For a large enough $t$ one
has

$t^{At/2-1}<(t-1)^{A(t-1)-1},$

so $A>A^{\prime}>A/2$. Consider any subgraph $G^{\prime}_{t}$ of $G_{t}$ on
$t^{A^{\prime}t}$ vertices. It is $H$-free and has the independence number
smaller than $t$, so the chromatic number of $G^{\prime}_{t}$ is at least $r$.
Then one may repeat the previous argument to show

$|E(G^{\prime}_{t})|\leq|V(G^{\prime}_{t})|^{3}=t^{3A^{\prime}t}=r^{3}t^{3}=(1+o(1))\left(\frac{r\ln
r}{A^{\prime}\ln\ln r}\right)^{3}<(1+o(1))\left(\frac{2r\ln r}{A\ln\ln
r}\right)^{3}.$

####  2.3.2 The lower bound

Essentially, this proof follows along the proof of the lower bound in Theorem
5. First, we show that for each $\varepsilon\in(0,1/b)$ there is some constant
$C_{\varepsilon}>0$ such that

$m_{H}(r)\geq C_{\varepsilon}r^{3}\ln^{1/b-\varepsilon}r.$ (34)

Suppose that $G$ is an $H$-free 3-graph with
$|E(G)|<C_{\varepsilon}r^{3}\ln^{1/b-\varepsilon}r$ that is not $r$-colorable.
Here $C_{\varepsilon}$ is some constant which depends only on $\varepsilon$
and which will be chosen later. Let such $r$ be minimal possible. By Lemma 3
we have that $G[V_{big}]$ should not be $\lfloor r/2\rfloor$-colorable.

Let us look at the value of $\alpha(G[V_{big}])$. If

$\alpha(G[V_{big}])\geq\frac{2C_{\varepsilon}}{cr^{2}}\bigl{(}r^{3}\ln^{1/b-\varepsilon}r-(r-1)^{3}\ln^{1/b-\varepsilon}(r-1)\bigr{)},$
(35)

then we can paint vertices of the biggest independent set of $G[V_{big}]$ in
one color. By removing colored vertices from $G$ we get $H$-free 3-graph that
is not $(r-1)$-colorable but has less than

$C_{\varepsilon}r^{3}\ln^{1/b-\varepsilon}r-\frac{cr^{2}}{2}\cdot\frac{2C_{\varepsilon}}{cr^{2}}\bigl{(}r^{3}\ln^{1/b-\varepsilon}r-(r-1)^{3}\ln^{1/b-\varepsilon}(r-1)\bigr{)}=C_{\varepsilon}(r-1)^{3}\ln^{1/b-\varepsilon}(r-1)$
(36)

edges, which contradicts the minimality of $r$.

So the contrary to (35) must hold. Since
$r^{3}\ln^{a}r-(r-1)^{3}\ln^{a}(r-1)<4r^{2}\ln^{a}r$ for all $r\geq 1$ and
$a\geq 0$, we have

$\alpha(G[V_{big}])<\frac{8C_{\varepsilon}}{c}\cdot\ln^{1/b-\varepsilon}r.$
(37)

Due to the bound (7),

$\left|V_{big}\right|<\left(\frac{8C_{\varepsilon}}{c}\cdot\ln^{1/b-\varepsilon}r\right)^{B((8C_{\varepsilon}\ln^{1/b-\varepsilon}r)/c)^{b}}.$
(38)

We take logarithm of the right-hand side and see that when
$C_{\varepsilon}\leq c/8$

$B\left(\frac{8C_{\varepsilon}}{c}\ln^{1/b-\varepsilon}r\right)^{b}\cdot\left(\ln\frac{8C_{\varepsilon}}{c}+\ln\ln^{1/b-\varepsilon}r\right)\leq
B\left(\frac{8C_{\varepsilon}}{c}\right)^{b}\ln^{1-b\varepsilon}r\cdot\ln\ln^{1/b-\varepsilon}r<B\left(\frac{8C_{\varepsilon}}{c}\right)^{b}\ln^{1-b\varepsilon}r\cdot\ln\ln^{1/b}r.$
(39)

There exists $x_{\varepsilon}>0$ such that the function
$\ln^{b\varepsilon}x/\ln\ln^{1/b}x$ is positive and strictly increases when
$x\geq x_{\varepsilon}$. Then for any $C_{\varepsilon}$ such that

$\left(\frac{8C_{\varepsilon}}{c}\cdot\ln^{1/b-\varepsilon}x\right)^{B((8C_{\varepsilon}\ln^{1/b-\varepsilon}x)/c)^{b}}<x\text{
for any }x<x_{\varepsilon}\text{ and
}C_{\varepsilon}^{b}<\frac{1}{B}\cdot\left(\frac{c}{8}\right)^{b}\frac{\ln^{b\varepsilon}x_{\varepsilon}}{\ln\ln^{1/b}x_{\varepsilon}},$
(40)

we either have $|V_{big}|<r$ if $r<x_{\varepsilon}$, or we have

$\ln|V_{big}|<BC_{\varepsilon}^{b}\left(\frac{8}{c}\right)^{b}\ln^{1-b\varepsilon}r\cdot\ln\ln^{1/b}r<\ln^{1-b\varepsilon}r\cdot\ln^{b\varepsilon}r=\ln
r$ (41)

if $r\geq x_{\varepsilon}$, which also means that $|V_{big}|<r$. So vertices
of $V_{big}$ can be colored in $\lfloor r/2\rfloor$ colors with no more than
two vertices of same color. It means that there is a proper coloring of $G$ in
$r$ colors. Obtained contradiction finishes the proof of (34).

It remains to construct some function $g$ such that $g(r)\to 0$ as
$r\to\infty$ and

$m_{H}(r)\geq r^{3}\ln^{1/b-g(r)}r.$ (42)

For each $n$ there is some $r_{n}$ such that for $r\geq r_{n}$

$C_{1/n}\ln^{1/n}r>1,$ (43)

which means that

$m_{H}(r)\geq r^{3}\ln^{1/b-2/n}r.$ (44)

Finally, for $r\geq r_{1}$ let

$g(r)=\frac{2}{\max\limits_{\begin{subarray}{c}n\leq r\\\ r_{n}\leq
r\end{subarray}}n}.$ (45)

Clearly, $g(r)$ is non-increasing and can be arbitrary small, so
$g(r)\xrightarrow[r\to\infty]{}0$.

###  2.4 Proof of Proposition 2

Suppose the contrary, i. e. there is an $H$-free 3-graph $G$ with the
chromatic number more than $r$ and the number of edges at most $Cr^{4}$. Let
such $r$ be minimal possible.

Let us try to color $G[V_{big}]$ in $r^{\prime}=\lfloor r/2\rfloor$ colors
greedily with respect to an arbitrary linear order $\pi$ on the vertex set. If
it is impossible then there is a vertex $v$ such that it is the last vertex in
edges $f_{1},\dots,f_{r^{\prime}}$ such that set $f_{i}\setminus\\{v\\}$ has
color $i$. Then an arbitrary choice of one vertex from each set
$f_{i}\setminus\\{v\\}$ leads to an independent set $I$ of size $r^{\prime}$,
since $G$ is $H$-free.

By removing $I$ from $G$ we get some 3-graph that is not $(r-1)$-colorable, so
it must have more than $C(r-1)^{4}$ edges. So we removed less than

$Cr^{4}-C(r-1)^{4}<C\cdot 4r^{3}=\frac{er^{3}}{72}$ (46)

edges. But the sum of degrees of vertices in $I$ (in the initial graph $G$) is
at least $r^{\prime}\cdot cr^{2}$, so it intersects at least

$\frac{cr^{2}r^{\prime}}{2}\geq\frac{cr^{3}}{6}=\frac{er^{3}}{72}$ (47)

edges. That is a contradiction.

###  2.5 Proof of Theorem 7

Let $C_{2}>0$. Consider a 3-graph $G$ with

$|E(G)|\leq\frac{C_{2}r^{\frac{2b}{b-1}}}{(\ln\ln r)^{1+\frac{2b}{b-1}}}.$
(48)

We will show that it is $r$-colorable if $r$ is sufficiently big. Let
$V_{0}=V(G)$ and

$V_{i}=\left\\{v\in
V_{i-1}:\deg_{G[V_{i-1}]}v\geq\frac{1}{C_{3}}\left(\frac{r}{\ln\ln
r}\right)^{2}\right\\},\quad i\geq 1,$ (49)

where $C_{3}>0$ is chosen to satisfy the inequality

$\frac{1}{C_{3}}\left(\frac{r}{\ln\ln
r}\right)^{2}\leq\frac{1}{3e}\left[\frac{r}{\log_{b}\ln r}\right]^{2}$ (50)

for, let’s say, $r>100$, so, by Lemma 2, every 3-graph $G[V_{i}\setminus
V_{i+1}]$ for $i\geq 0$ has a proper coloring in $\bigl{[}\frac{r}{\log_{b}\ln
r}\bigr{]}$ colors. Clearly, $C_{3}$ can be chosen independently of $r$.

Now we are going to estimate sizes of $E(G[V_{i}])$ and $V_{i+1}$ from above
for each $i\geq 0$. As $V_{i+1}\subset V_{i}$, we have

$\left|E(G[V_{i}])\right|\geq\frac{1}{3}\sum_{v\in
V_{i+1}}\deg_{G[V_{i}]}v\geq\frac{1}{3}\cdot\left|V_{i+1}\right|\cdot\frac{1}{C_{3}}\left(\frac{r}{\ln\ln
r}\right)^{2},$ (51)

so

$\left|V_{i+1}\right|\leq 3C_{3}\left(\frac{\ln\ln
r}{r}\right)^{2}\left|E(G[V_{i}])\right|.$ (52)

Also, we have bound (48) for $\left|E(G[V_{0}])\right|=|E(G)|$, and, by (14),

$\left|E(G[V_{i}])\right|\leq C_{1}(\left|V_{i}\right|)^{b}\ \text{for $i\geq
1$}.$ (53)

Combining (53) and (52) and using induction on $i$, we obtain for $i\geq 0$

$\left|E(G[V_{i}])\right|\leq
C_{1}^{\frac{b^{i}-1}{b-1}}C_{2}^{b^{i}}(3C_{3})^{\frac{b^{i+1}-b}{b-1}}\cdot\frac{r^{\frac{2b}{b-1}}}{(\ln\ln
r)^{b^{i}+\frac{2b}{b-1}}},$ (54) $\left|V_{i+1}\right|\leq
C_{1}^{\frac{b^{i}-1}{b-1}}C_{2}^{b^{i}}(3C_{3})^{\frac{b^{i+1}-1}{b-1}}\cdot\frac{r^{\frac{2}{b-1}}}{(\ln\ln
r)^{b^{i}+\frac{2}{b-1}}}.$ (55)

The last inequality implies that $V_{N}$ is empty for $N$ and $r$ large
enough. Namely, let $C=C_{1}^{\frac{1}{b-1}}C_{2}(3C_{3})^{\frac{b}{b-1}}$.
Then for $r>r_{0}(C_{1},C_{3})$ from last inequality we get

$\left|V_{i+1}\right|\leq\frac{r^{\frac{2}{b-1}}}{C_{1}^{\frac{1}{b-1}}(3C_{3})^{\frac{1}{b-1}}\cdot(\ln\ln
r)^{\frac{2b}{b-1}}}\bigg{/}\left(\frac{\ln\ln r}{C}\right)^{b^{i}}\leq
r^{\frac{2}{b-1}}\bigg{/}\left(\frac{\ln\ln r}{C}\right)^{b^{i}}.$ (56)

So for $N>\log_{b}\ln r$

$|V_{i+1}|\leq r^{\frac{2}{b-1}}\bigg{/}\left(\frac{\ln\ln r}{C}\right)^{\ln
r}=\left(\frac{Ce^{\frac{2}{b-1}}}{\ln\ln r}\right)^{\ln r},$ (57)

which is less than 1 when $\ln\ln r>Ce^{2/(b-1)}$, i.e.

$r>e^{e^{Ce^{2/(b-1)}}}.$ (58)

We have divided $V$ into at most $\log_{b}\ln r$ sets of form $V_{i}\setminus
V_{i+1}$, and each 3-graph $G[V_{i}\setminus V_{i+1}]$ has a proper coloring
with at most $\frac{r}{\log_{b}\ln r}$ colors, so $G$ is $r$-colorable.
Therefore, we can put $R=\max\left(100,r_{0},e^{e^{Ce^{2/(b-1)}}}\right)$.

###  2.6 Proof of Proposition 3

Suppose that a 3-graph $G$ has more than $(t-3)\binom{n}{2}$ edges. We will
show that some subgraph of $G$ is isomorphic to $H$.

Let us repeat the following procedure: if there is an edge
$g=\\{v_{1},v_{2},v_{3}\\}$ such that the pair $(v_{1},v_{2})$ is contained in
at most $t-3$ edges (including $g$), remove $g$. There will be removed at most
$(t-3)\binom{n}{2}$ edges, and after that each pair of vertices will be joined
by either 0 or at least $t-2$ edges. Denote resulting 3-graph by $G^{\prime}$.

Let $H_{i}$ be a subgraph of $H$ induced by edges $h_{1},\dots,h_{i}$. We have
removed at most $(t-3)\binom{n}{2}$ edges from $G$, so
$\left|E(G^{\prime})\right|\geq 1$. A subgraph of $G^{\prime}$ induced by one
edge is isomorphic to $H_{1}$. Now we will show that if there is a subgraph
$H^{\prime}_{i-1}\subset G^{\prime}$ isomorphic to $H_{i-1}$, then there is a
subgraph isomorphic to $H_{i}$. All we have to do is find an edge which can be
put in correspondence to $h_{i}$. $H_{i-1}$ has an edge
$h_{j(i)}\supset\\{a_{i},b_{i}\\}$. Consider $v,u\in V(H^{\prime}_{i-1})$ that
correspond to $a_{i}$ and $b_{i}$. There is an edge in $H^{\prime}_{i-1}$ that
corresponds to $h_{j(i)}$, so $v$ and $u$ are joined by at least $t-2$ edges
in $G^{\prime}$. We have
$\left|V(H^{\prime}_{i-1})\right|-2=\left|V(H_{i-1})\right|-2=i-1<t-2$, so
there exists $e\in E(G^{\prime})$ such that $e=\\{v,u,w\\}$ and $w\notin
V(H^{\prime}_{i-1})$. This edge $e$ can be put in correspondence to $h_{i}$.

So there is a subgraph of $G^{\prime}$ that is isomorphic to $H_{t-2}=H$ and,
since $G^{\prime}\subset G$, it is a subgraph of $G$.

##  3 Discussion

##### Questions from [1].

######  Conjecture 1.

There exists a simple 3-graph $H$ for which

$m_{H}(r)=r^{3+o(1)}.$

######  Problem 1.

Characterize all 3-graphs $H$ such that

$m_{H}(r)=r^{3+o(1)}.$

##### Regularity issues.

It is known [3] that sequence $\frac{m(r)}{r^{3}}$ has a positive limit. The
same statement for quantity $m_{H}(r)$ is of interest ($H$ is assumed to be
fixed). In particular, it is unknown even for the case of simple 3-graphs,
i.e. when $H=\\{\\{1,2,3\\},\\{1,2,4\\}\\}$, for which the asymptotics is
known:

$m_{H}(r)=\Theta(r^{4}\log^{2}r).$

## References

  * [1] Tom Bohman, Alan Frieze, and Dhruv Mubayi.  Coloring ${H}$-free hypergraphs.  Random Structures & Algorithms, 36(1):11–25, 2010.
  * [2] D. D. Cherkashin.  On the Erdős–Hajnal problem for 3-graphs.  Journal of Mathematical Sciences, 255(1):103–108, 2021.
  * [3] Danila Cherkashin and Fedor Petrov.  Regular behavior of the maximal hypergraph chromatic number.  SIAM Journal on Discrete Mathematics, 34(2):1326–1333, 2020.
  * [4] David Conlon, Jacob Fox, and Benny Sudakov.  Hypergraph Ramsey numbers.  Journal of the American Mathematical Society, 23(1):247–266, 2010\.
  * [5] Jacob Fox and Xiaoyu He.  Independent sets in hypergraphs with a forbidden link.  Proceedings of the London Mathematical Society, 123(4):384–409, 2021.
  * [6] András Gyárfás and Jenő Lehel.  Trees in greedy colorings of hypergraphs.  Discrete Mathematics, 311(2-3):208–209, 2011.
  * [7] Alexandr Kostochka, Dhruv Mubayi, Vojtěch Rödl, and Prasad Tetali.  On the chromatic number of set systems.  Random Structures & Algorithms, 19(2):87–98, 2001.
  * [8] Alexandr Kostochka, Dhruv Mubayi, and Jacques Verstraete.  Hypergraph Ramsey numbers: Triangles versus cliques.  Journal of Combinatorial Theory, Series A, 120(7):1491–1507, 2013\.
  * [9] András Pluhár.  Greedy colorings of uniform hypergraphs.  Random Structures & Algorithms, 35(2):216–221, 2009.
  * [10] Andrei Mikhailovich Raigorodskii and Danila Dmitrievich Cherkashin.  Extremal problems in hypergraph colourings.  Russian Mathematical Surveys, 75(1):89–146, 2020.

##### Danila Cherkashin

Institute of Mathematics and Informatics, Bulgarian Academy of Sciences
Sofia 1113, 8 Acad. G. Bonchev str.
<EMAIL_ADDRESS>
##### Alexey Gordeev and Georgii Strukov

The Euler International Mathematical Institute, St. Petersburg, Russia


# DeepTensor: Low-Rank Tensor Decomposition
with Deep Network Priors

Vishwanath Saragadam, Randall Balestriero, Ashok Veeraraghavan, and Richard G.
Baraniuk, V. Saragadam, R. Balestriero, A. Veeraraghavan, and R. Baraniuk are
with the Department of Electrical and Computer Engineering, Rice University,
Houston, TX, 77005.
E-mail<EMAIL_ADDRESS>
###### Abstract

DeepTensor is a computationally efficient framework for low-rank decomposition
of matrices and tensors using deep generative networks. We decompose a tensor
as the product of low-rank tensor factors (e.g., a matrix as the outer product
of two vectors), where each low-rank tensor is generated by a deep network
(DN) that is trained in a _self-supervised_ manner to minimize the mean-square
approximation error. Our key observation is that the implicit regularization
inherent in DNs enables them to capture nonlinear signal structures (e.g.,
manifolds) that are out of the reach of classical linear methods like the
singular value decomposition (SVD) and principal components analysis (PCA).
Furthermore, in contrast to the SVD and PCA, whose performance deteriorates
when the tensor’s entries deviate from additive white Gaussian noise, we
demonstrate that the performance of DeepTensor is robust to a wide range of
distributions. We validate that DeepTensor is a robust and computationally
efficient drop-in replacement for the SVD, PCA, nonnegative matrix
factorization (NMF), and similar decompositions by exploring a range of real-
world applications, including hyperspectral image denoising, 3D MRI
tomography, and image classification. In particular, DeepTensor offers a 6dB
signal-to-noise ratio improvement over standard denoising methods for signal
corrupted by Poisson noise and learns to decompose 3D tensors 60 times faster
than a single DN equipped with 3D convolutions.

###### Index Terms:

Tensor Decomposition, Matrix Factorization, Low-Rank Completion, Deep Network,
Self-Supervised Learning.

##  1 Introduction

Low-rank representations of matrices and tensors are truly ubiquitous and
applied across all fields of science and engineering, from statistics [1, 2,
3, 4, 5] to control systems [6, 7] to computer vision [8, 9, 10], and beyond.
Low-rank representations seek to represent a large matrix/tensor as a product
of smaller (and hence lower rank) matrices/fibers. For instance, the classical
approach to representing matrices in a low-rank manner is via the singular
value decomposition (SVD), which expresses a matrix as a product of two
smaller orthonormal matrices (containing the singular vectors) and a diagonal
matrix (containing the singular values). Thresholding the singular values
creates a matrix that inhabits a lower dimensional subspace. The SVD is a
pervasive technique for data preprocessing and dimensionality reduction across
a wide entire range of machine learning (ML) applications, including principal
component analysis (PCA) and data whitening.

No matter how powerful or pervasive, however, the SVD and PCA are not without
their shortcomings. SVD/PCA is an optimal low-rank decomposition technique
only under a narrow set of assumptions on the statistics of the signal and
noise in the task at hand [11]. When the signal or noise is non-Gaussian, the
resulting decomposition is not optimal and results in a subspace that differs
from the true low-rank approximation of the underlying matrix. These issues
have been addressed somewhat successfully in the past with several signal- and
application-specific regularizers that include sparsity on error [12, 13, 14],
total variation penalty [15, 16, 17], and data-driven approaches [18, 19]. The
key observation is that a good signal model can act as a strong regularizer
for estimating the low-rank factors. Unfortunately, finding a useful signal
model/regularizer for a new application can be a daunting task. Does there
exist a generalized regularizer that can encompass a large class of signals
and applications? We found the answer to be hidden implicitly in deep networks
(DNs).

(a) Low-rank representation via SVD

(b) Low-rank representation via DeepTensor

Figure 1: DeepTensor is a new a low-rank decomposition technique that exploits
the implicit regularization capabilities of DNs. Conventional low-rank
factorization such as (a) SVD relies on linear factors to represent the
matrix. DeepTensor represents via factor matrices that are outputs of DNs.
Factorization is then achieved by learning parameters of the network in a
self-supervised manner that reduces the ($\ell_{2}$) loss between the factor
and input matrix. Figure 2: DeepTensor eigenfaces. DeepTensor is a drop-in
replacement for most dimensionality reduction techniques and is robust to a
wide range of signal and noise models. Here we show an “eigenface”
decomposition with facial data corrupted by Poisson noise. The top twelve
bases vectors visualized above at 15 dB input PSNR show that DeepTensor learns
principal components that are significantly lower in noise levels compared to
ICA or PCA. This in turn affects the classification accuracy (bottom right)
that involves taking projection of input data on the principal components
followed by a linear SVM classifier.

In this paper, we propose DeepTensor, a new approach for low-rank
matrix/tensor decomposition that is robust to a wide class of signal and noise
models. Our core enabling observation is that DNs produce signals that are
implicitly regularized due to the networks’ inherent inductive bias. We
exploit DNs as priors by representing a matrix/tensor in terms of factors
output from a set of untrained generative networks (see Fig. 1). The
parameters of the networks are learned in a self-supervised manner for each
matrix/tensor using a simple MSE loss between the matrix/tensor and the
product of the deeply generated factors. The inductive bias of the generative
networks enables DeepTensor to better identify the underlying low-dimensional
subspace while rejecting noise, resulting in a more accurate estimate of the
noise-free matrix/tensor.

DeepTensor is a computationally efficient, drop-in replacement for many
existing matrix/tensor factorization approaches that combines the simplicity
of low-rank decomposition with the power of deep generative networks. Further,
DeepTensor can significantly improve the performance of downstream tasks, such
as image classification, that rely on low dimensional representation. We
empirically back these claims via experiments on a wide variety of real-world
tasks, including denoising with low-rank approximation, “eigenfaces" [20] for
facial recognition (see Fig. 2), solving linear inverse problems with
compressively sensed videos, tensor denoising, and recovery of 3D volumes from
computed tomographic (CT) measurements. We also highlight DeepTensor’s
computational efficiency and scalability for large and higher-order tensor
decomposition by demonstrating that it offers a $60\times$ or more speedup for
decomposing 3D tensors as compared to a single generative network equipped
with full 3D convolutions.

##  2 Background and Prior Work

DeepTensor leverages classical work on low-rank approximation and recent self-
supervised learning techniques with DNs [21, 22]. We provide a brief overview
of these topics to introduce our notation and intuition and to set context for
our work.

Low-rank approximation. Low-rank approximation seeks to represent a matrix
$X\in\mathbb{R}^{M\times N}$ of rank $R=\min(M,N)$ as a product of two smaller
matrices, $U\in\mathbb{R}^{M\times k},V\in\mathbb{R}^{N\times k}$ where $k$ is
generally taken to be smaller than $R$. The specific constraints on $U,V$, and
the desired objective give rise to different types of low-rank approximation
algorithms. For example, one recovers PCA [23], nonnegative matrix
factorization (NMF) [24] and $k$-means [25] via

$\displaystyle\min_{U,V}\|X-UV^{T}\|_{F}\text{~{}~{}s.t.~{}~{} $U=V^{T}$}$
(PCA/SVD) (1) $\displaystyle\min_{U,V}\|X-UV^{T}\|_{F}\text{~{}~{}s.t.~{}~{}
$U\geq 0,V\geq 0$}$ (NMF) (2)
$\displaystyle\min_{U,V}\|X-UV^{T}\|_{F}\text{~{}~{}s.t.~{}~{}
$[V]_{.,k}\in\\{e_{1},\dots,e_{n}\\}$}$ ($k$-means) (3)

where $e_{k}$ is the $k^{\rm th}$ Euclidean canonical basis vector, and
$[V]_{.,k}$ is the $k^{\rm th}$ column of $V$. Applications of low-rank
approximation are extremely diverse ranging from denoising [26, 27],
compression [28], clustering for anomaly detection [29], and forecasting [30].

The Achilles’ heel of low-rank approximation is non-Gaussian signal and/or
noise statistics. There are been many extensions and variants of the SVD
algorithms, such as Robust PCA [12] that improves robustness in learning the
low-rank matrices against outliers in the data. Similarly, other non-Gaussian
noise settings, different metrics and constraints could be employed to obtain
the most adapted $U,V$ decomposition to solve the task at hand. This can be
well understood based on the generative models corresponding to low-rank
approximation techniques such as Probabilistic PCA [31] from which it is clear
that PCA is optimal under a Gaussian noise model, and in the presence of say a
Laplacian noise, an $\ell_{1}$ reconstruction loss should be used instead.
Prior work identified approaches to tackling tensor decomposition with unknown
noise statistics via Bayesian optimization [32, 33], modeling noise
distribution as a mixture of Gaussian [34], and using a decomposition inspired
by Kronecker product [35, 36]. While the approaches are promising for several
tensor decomposition applications, none of the previous works leverage
inductive bias of DNs.

There has been some research in exploiting trained DNs for matrix
factorization especially in the settings of nonnegative matrix factorization
[37], magnetic resonance imaging (MRI) denoising [19], and tensor completion
[18]. The key idea is that the statistics of training data can help regularize
the inverse problem of matrix factorization. Such techniques however suffer
from dataset biases, and require very large pools of data to be effective.

Deep networks as implicit regularizers. DNs have emerged very rapidly from
classification and regression applications where they have reached superhuman
performance across a wide range of datasets and tasks [38]. More recently, the
use of DNs has diversified – an illustrative and important example for this
paper is the Deep Image Prior (DIP) model [21]. In this setting, a DN $f$ is
used as a constrained projection of a random noise vector $z$ to fit a target
sample $x$ as follows

$\displaystyle\min_{\Theta}\|f_{\Theta}(z)-x\|_{2}^{2}.$ (4)

When the architecture of the DN is carefully picked, the estimation of the
input $x$ is denoised, and well reconstructed even in the presence of missing
values. From the implicit regularization field it is understood that the above
problem is equivalent to some problem

$\displaystyle\min_{W}\|Wz-x\|_{2}^{2}+R(W),$ (5)

where $R(W)$ is a regularization term that directly depends on the choice of
the DN architecture [39]. The key result that we will leverage throughout this
paper is that searching for the DN parameters producing the desired result in
(4) is equivalent to searching in the space of regularizers in (5).

Related work combining DNs and low-rank decomposition. Applying DNs in a self-
supervised manner for matrix decomposition has received surprisingly little
attention. The closest work is by Aittala et al. [40], which regularized a
matrix factorization for a specific video imaging problem using generative
networks. The video sequence was represented by a generative network equipped
with 3D convolutional kernels, while the light transport matrix was
represented as a linear combination of the input video sequence multiplied by
another generative network equipped by 2D convolutional kernels. DeepTensor is
in many ways inspired by the factorization idea proposed by Aittala et al.
[40] but goes beyond light transport matrices and can be applied to a wide
variety of problem settings.

A related but different approach to DeepTensor is the work by Bacca et al.
[41], who identified that hyperspectral images (which are modeled as 3D
tensors) can be represented as the output of a single generative network
equipped with 3D convolutional kernels. The work by Bacca et al. [41] is a
promising framework for solving inverse problems in hyperspectral imaging, but
are not aimed at low-rank matrix factorization – which is the focus of this
paper. The key difference between their work and DeepTensor is that the input
to their 3D network is a low-rank Tucker tensor; in contrast we _output_ a
low-rank Tucker tensor.

##  3 DeepTensor Decomposition

###  3.1 Low-rank decomposition with deep network prior

Matrix decomposition. Consider the low-rank decomposition in (1). If we
include regularizers for $U$ and $V$, we obtain the following optimization
function

$\displaystyle\min_{U,v}\|X-UV^{\top}\|^{2}+R(U,V),$ (6)

where $R(U,V)$ is a regularizer for $U,V$. Instead of having explicit
regularizers on the left and right matrices, we model $U,V$ as the outputs of
generative networks $f_{U},f_{V}$, which yields

$\displaystyle\min_{\theta_{U},\theta_{V}}\|X-f_{U}(z_{U})f_{V}(z_{V})^{\top}\|^{2},$
(7)

where $z_{U}$ and $z_{V}$ are randomly initialized inputs to the networks
$f_{U},f_{V}$ respectively that have parameters $\theta_{U},\theta_{V}$. The
networks’output are of the same shape as the desired $U$ and $V$ matrices from
(6). We note here that there is no further regularizer on the matrices – any
regularization comes from the implicit prior of the DN itself, which makes it
an appealing choice to solve a diverse type of signals and noise settings.
Figure 3 visualizes the regularization offered by DNs for the task of rank-20
decomposition. Over 100 iterations, the error for signal reduces by two orders
of magnitude, while the error reduces by less than one order for noise. This
slow fitting to noise is a result of implicit bias of DNs which is leveraged
by DeepTensor.

Figure 3: Implicit bias of DeepTensor rejects noise. The inductive bias due to
the network architecture fits better to signal and rejects noise. To test
this, we performed a rank-20 decomposition of a hyperspectral image [42], iid
Gaussian noise with a standard deviation of 0.01 units, and a noisy signal
obtained by adding the hyperspectral image and the Gaussian noise. We observe
that through the training epochs, the signal is better fit by the network,
while the noise has a slower fit.

Tensor decomposition. The task of tensor decomposition finds numerous
applications and is an active area of research, where the major difficulty
rises from defining an appropriate regularizer/basis constraint (recall (3)).
Any constraint on the factor matrices can be expressed as regularization
functions. Hence, given the following general decomposition problem

$\min_{U,V,\dots,W}\|X-\underbrace{U\otimes V\otimes\dots\otimes W}_{k\text{
times}}\|^{2}+R(U,V,\dots,W),$

with $X$ a $k$-dimensional tensor, one needs to specify the correct
regularizer ($R$) such that the produced decomposition is adapted for the task
at hand. This search is mostly understood in narrowly defined settings such as
Gaussian noise and Gaussian latent space factors. Instead, DeepTensor seeks to
solve the the following optimization to compute the decomposition

$\displaystyle\min_{\theta_{U},\theta_{V},\dots,\theta_{W}}\|X-\underbrace{f_{U}(z_{U})\otimes
f_{V}(z_{V})\otimes\dots\otimes f_{W}(z_{W})}_{k\text{times}}\|^{2},$ (8)

where $f_{U},f_{V},\dots,f_{W}$ are $k$ DNs that are fed with input vectors
$z_{U},z_{V},\times,z_{W}$ with parameters $\theta_{U},\theta_{V},\theta_{W}$
respectively. Note that this decomposition closely resembles the parallel
factor analysis (PARAFAC); one can instead formulate a Tucker representation
which includes an extra core tensor.

Figure 4: Separable convolutions leads to speedup. An added benefit of deep
low rank decomposition is that the convolutions are separated. Hence for a 3D
volume, we can exploit one 2D and one 1D network for factorization instead of
a 3D network – resulting in two orders of magnitude speed up.

Dimensionality splitting brings tractability without sacrificing performance.
While it is possible to represent the matrix itself via a DN prior, doing so
will require a 2D network instead of two 1D networks. The goal of this section
is to study the exponential computational time gain offered by separating the
dimensionality of the tensor and doing the tensor products of multiple
independent DN outputs as per (8) versus doing the tensor product in the
latent space and then using as done for the $2$-dimensional case in [21] and
that naturally generalizes to

$f_{U,V,\dots,W}(z_{U}\otimes z_{V}\otimes\dots\otimes z_{W}).$ (9)

To understand the benefits of those two different cases we approximate a 3D
magnetic resonance imaging (MRI) volume of size $128\times 128\times 150$ with
three types of networks — one 2D and 1D that is a natural parametrization that
captures the dependence of the first two dimensions $f_{U,V}(z_{U,V})\otimes
f_{W}(z_{W})$, three 1D (8), and one 3D networks (9). Figure 4 shows the plot
of mean squared error (MSE) as a function of time for the three approaches. We
note that using three 1D networks is faster than using a 2D and 1D network,
and both are two orders of magnitude faster than using one 3D network.
Additionally, our (separate) parametrization has the benefit of keeping
interpretability since one has access to each generated low-rank matrix that
combine to form the observed data matrix $X$. The choice between using
networks equipped with 2D and 1D convolutions, and networks equipped with 1D
convolutions is specific to the task at hand. Tensors such as videos and
hyperspectral images benefit from networks equipped with 2D and 1D
convolutions. In contrast, tensors from multi-dimensional face databases [43]
or computed tomographic (CT) images benefit from a full tensor decomposition.

Figure 5: Architectures for various experiments in the paper. We used modified
2 dimensional (top) and 1 dimensional (bottom) versions of the networks
proposed in Deep Image Prior [21].

Unless explicitly specificed, we utilize overparameterized networks for the
factor matrices, similar to DIP [21] (see Fig. 5). However, it is possible to
use underparameterized networks instead, similar to the deep decoder
architecture [22]. The advantage of the latter is that the learned parameters
can be used as the compressed version of the tensor being decomposed. In
contrast, for pure data imputation and denoising the DIP version should be
preferred. We compare the two choices in the upcoming section.

Gaussian matrix with Gaussian noise

Piecewise constant matrix with Poisson noise

Piecewise constant matrix with Rician noise

Figure 6: DeepTensor is robust to a range of signal and noise distributions.
We generated low-rank matrices with various signal and noise distributions and
then performed a low-rank decomposition via SVD And DeepTensor. We observe
that DeepTensor has similar performance to SVD under Gaussian noise settings.
When the noise is non-Gaussian, such as Poisson or Rician, DeepTensor has
significantly higher accuracy across all ranks.

PCA with 32 data samples

PCA with 1024 data samples

PSNR vs. sample size

Figure 7: DeepTensor is a more robust for PCA under low SNR or small sample
size. The SVD is the core computation of PCA. We generated data with varying
number of samples drawn from a Gaussian distribution with varying standard
deviation. We then computed PCA components via SVD and DeepTensor
decomposition. We observe that DeepTensor is particularly advantageous when
the data is corrupted by a large noise, or the number of samples are limited.

Optimization procedure. We optimized for the parameters of the networks that
output the factor matrices using stochastic gradient descent. Specifically, we
employed the ADAM optimizer [44] and implemented the optimization using
PyTorch framework [45]. For all experiments, we optimized an $\ell_{2}$ loss
function between the data and the product of outputs of DNs. The primary
purpose of choosing a simple loss function was to emphasize on the
regularization capabilities of the DNs. In practice, it is possible to choose
a more appropriate loss function for each specific problem.

###  3.2 Validation experiments

Low-rank completion. We generated random $64\times 64$ dimensional matrices
with rank varying from 10 to 60. The left and right matrices were generated as
either iid Gaussian values (with a standard deviation of 1 unit), or random,
piecewise constant signals, emulating visual signals. We then added one of the
three types of noise:

  * •

iid Gaussian noise with standard deviation of 0.1 units:
$Y=X+\mathcal{N}(0,0.1)$

  * •

Poisson noise with mean at each entry of the matrix lying in the range
$[0,1000]$: $Y=\mathcal{P}(1000X)$, which is common in visual signals

  * •

Rician noise with standard deviation of 0.02 units:
$Y=\sqrt{(X+\mathcal{N}(0,0.02))^{2}+\mathcal{N}(0,0.02)^{2}}$ that is common
in MRI measurements.

Figure 6 shows a plot of peak signal-to-noise ratio (PSNR) as a function of
rank for various signal and noise types averaged over 10 realizations. We make
two observations. First, when the noise is Gaussian, DeepTensor has similar
performance to SVD/PCA. This is expected, since SVD/PCA is known to be the
optimal low-rank decomposition for white Gaussian matrices [11]. Second, for
other noise settings, such as Poisson or Rician, DeepTensor has a far superior
performance across all rank values. This empirically establishes that
DeepTensor is well suited for a range of non-Gaussian noise models.

TABLE I: Effect of learning rate schedule. The table presents the best achievable learning rate for low-rank approximation of a toy matrix. We repeated each experiment five times. SVD accuracy was $14.4$ dB. The choice affects the final achievable accuracy – fixed scheduling with a high learning rate performs better than other choices. Max learning rate Scheduler | Fixed | Step | Exponential | Cosine annealing
---|---|---|---|---
$10^{-2}$ | $17.6\pm 0.7$ | $17.1\pm 0.4$ | $16.6\pm 0.4$ | $16.5\pm 0.3$
$10^{-3}$ | $17.5\pm 0.6$ | $17.1\pm 0.5$ | $16.6\pm 0.4$ | $16.6\pm 0.3$
$10^{-4}$ | $17.6\pm 0.6$ | $17.1\pm 0.4$ | $16.6\pm 0.4$ | $16.5\pm 0.3$
$10^{-5}$ | $16.5\pm 0.3$ | $16.5\pm 0.2$ | $16.5\pm 0.4$ | $16.6\pm 0.3$

Principal Component Analysis. The performance of SVD-based PCA degrades under
noisy conditions or when samples are limited. To verify how DeepTensor can
benefits PCA, we generated variable number of data points with a known
intrinsic matrix generated as iid Gaussian random variables with mean 0 and
standard deviation of 1. The feature dimension was 64 and the intrinsic
dimension (rank) was 10. We generated data via a linear combination of the
columns where the weights were drawn from an iid Gaussian distribution with
mean 0 and standard devation. We then added iid Gaussian noise to the data
matrix with varying levels of standard deviation. Figure 7 plots the accuracy
of estimating the PCA components for varying noise levels and number of
samples averaged over 10 realizations. We observe that with low noise or a
large number of samples, SVD-based PCA and DeepTensor have similar
performance. However, with high noise or a limited number of samples,
DeepTensor significantly outperforms SVD-based PCA.

###  3.3 Sensitivity to learning parameters and architectures

We now discuss how the choice of learning rate scheduling and the network
architecture affect the final accuracy obtained by DeepTensor.

Learning rate scheduling. The choice of learning rate and its scheduling
directly affects the maximum achievable accuracy. To gain empirical insight
into how the rate and its scheduling affect the training process, we performed
a rank-16 low-rank decomposition of a $64\times 64$ matrix. The entries of the
matrix were drawn from iid Gaussian distribution. We then varied the learning
rates from $10^{-5}$ to $10^{-2}$, and chose four learning rate schedulers,
namely fixed with no change in learning rate, step scheduler where the
learning rate was multiplied by $0.99$ after every 2,000 epochs, exponential
scheduler with a multiplication factor of $0.9999$, and cosine annealing-based
scheduling [46].

Table I shows results for varying learning rate and its schedule. We note that
a fixed scheduler results in higher PSNR across all learning rates. Moreover,
learning rates ranging from $10^{-4}$ to $10^{-2}$ are equivalent choices – a
very low learning rate of $10^{-5}$ resulted in poorer PSNR. The two
observations above imply that DeepTensor does not require complex learning
rate scheduling and is robust to the learning rates.

Stopping criterion. The stopping criterion for optimal approximation accuracy
is a function of input noise distribution and network architecture. To
demonstrate this dependence, we performed a rank-16 low-rank decomposition of
$64\times 64$ matrices with entries drawn from iid Gaussian distribution. We
then utilized an under-parameterized, and over-parameterized network to
estimate the left and right factor matrices with varying levels of noise.
Figure 8 compares the results with the two types of networks. We note in Fig.
8(a) that both networks require fewer iterations with increasing noise level
for least approximation error. Fig. 8(b) shows approximation error over
epochs. Over-parameterized networks achieve lower approximation error than
under-parameterized networks. However,the error for over-parameterized
networks increases rapidly after optimal stopping epoch (100), whereas the
error increases more gently for under-parameterized networks after the optimal
stopping epoch (500). Ultimately, the stopping criteria and the network
architecture depend on the exact application and prior knowledge about noise
levels in the signal.

(a) Best stopping epoch as a function of input noise level

(b) Training epochs for over and under-parameterized networks.

Figure 8: Stopping criterion depends on input noise level and network
architecture. The optimal stopping epoch (a) reduces with increasing noise
standard deviation. (b) shows the approximation error when the noise standard
deviation is 0.2. The exact stopping epoch is less important for under-
parameterized networks [22], whereas over-parameterized networks [21] are more
sensitive to the stopping epoch, but achieve lower approximation error.

###  3.4 Modeling Known Decomposition Constraints with the Last Layer
Activation

Different constraints on $U$ and/or $V$ lead to different known low-rank
decompositions such as nonnegativity on $U$ and $V$ leads to NMF and
nonnegativity on $U$ alone leads to semi-NMF [47], which is an ubiquitous form
of clustering [48]. In our case, $U$ and $V$ are outputs of a DN (recall Sec.
8) and are thus without range constraints. Hence we need to impose
nonnegativity constraints on the output.

Nonnegativity can be achieved with various activation functions including
ReLU, softplus, and element-wise absolute value, and the exact choice affects
the achievable accuracy. To gain an empirical insight into the the effect of
the activation function, we considered NMF on MNIST [49] and CIFAR [50]
datasets. In both cases, we used 2048 images for training. We added a rician
noise to the images of the form ${\bf n}=0.3(0.3{\bf z}_{1}+{\bf z}_{2}^{2})$
where ${\bf z}_{1}$ and ${\bf z}_{2}$ are iid Gaussian random variables with
zero mean and unit variance. The input PSNR was evaluated to be $4.8$ dB. We
then performed NMF on the resultant images with various techniques.
Comparisons are tabulated in Table II. We employed a combination of $\ell_{2}$
loss for data fidelity, and $\ell_{1}$ penalty for the factor matrices output
from the DNs. DeepTensor, particularly when combined with the ReLU activation
function achieves higher approximation accuracy compared to baseline NMF
algorithm [51].

TABLE II: DeepTensor is a robust alternative to NMF. We performed NMF on MNIST
and CIFAR10 datasets by enforcing nonnegativity on $U,V$ through different
activation functions. The table below shows the average PSNR over 10 runs.
DeepTensor with ReLU as the final activation function outperformed standard
NMF [51], underscoring the efficacy for matrix factorization with positivity
constraints.

| MNIST
---|---
Act. func. | softplus | abs. value | ReLU
DeepTensor | 7.4 $\pm$0.03 | 7.3$\pm$0.01 | $\mathbf{7.6\pm 0.15}$
NMF [51] | 7.5

| CIFAR10
---|---
Act. func. | softplus | abs. value | ReLU
DeepTensor | 8.4 $\pm$0.08 | 8.3$\pm$0.06 | $\mathbf{8.8\pm 0.17}$
NMF [51] | 8.2

##  4 Applications

We now showcase the breadth of DeepTensor’s applicability in several real-
world applications.

Training details. Unless otherwise specified, we used overparameterized
networks with skip connections (similar to DIP [21]), and trained with a
learning rate of $10^{-3}$. We implemented our training process in Python
using the Pytorch framework [45]. All our experiments were run on a Linux
machine equipped with a hexa-core Intel Core i7-6850K CPU, 128GB RAM, and
three NVIDIA GeForce GTX 1080 Ti. The network architectures were a modified
version of the one used by Ulyanov et al. [21]. Specifically, we changed the
number of output channels to be equal to the rank for all factor matrices. For
tensor decomposition with 1D fibers, we changed the 2D convolutional
architecture in [21] to a 1D architecture. We optimized for both inputs and
network parameters, which provided faster convergence; however, there was no
other significant difference if we did not optimize for the inputs.

###  4.1 Linear inverse problems in computer vision

Low-rank model finds use in numerous applications in computer vision including
sensing of light transport matrices [52], hyperspectral imaging [53], video
compressive sensing [54], magnetic resonance imaging (MRI), and positron
emission tomography (PET). Most inverse problems involve collection of limited
data samples and/or highly noisy samples. In both cases, we expect the
DeepTensor to be very effective. We showcase three specific examples here.

Hyperspectral image denoising. Low-rank models offer a concise representation
of hyperspectral images (HSI) and are used in compression, sensing [53], and
dimensionality reduction. HSIs involve imaging the scene across several
hundreds of spectral bands, resulting in high photon noise (highly non-
Gaussian). Typically, a HSI of dimension $N_{x}\times N_{y}\times N_{\lambda}$
is converted to a matrix of dimension $N_{x}N_{y}\times N_{\lambda}$ which is
then approximated using a low-rank model. We denoised a $348\times 327\times
260$ HSI from Arad and Ben-Shahar [42] by simulating Poisson noise equivalent
to a maximum of 100 photons per spatio-spectral voxel, and a readout noise of
2 photons – settings corresponding to a dull overcast outdoor scene. We then
performed a rank-20 decomposition with SVD and DeepTensor. We also compared
DeepTensor against the BM3D denoising algorithm [55]. We ran the DeepTensor
optimization process for a total of 5000 iterations. Figure 6 shows the
results with both techniques. DeepTensor outperforms SVD by 6dB, and BM3D by
3dB and produces visually pleasing results.

Figure 9: Hyperspectral denoising. Low-rank models are often used for
representing hyperspectral images. We simulated noisy hyperspectral images by
adding Poisson noise with a maximum mean of 100 counts and then denoised using
a rank-20 model. DeepTensor has approximately 6dB increase in performance over
SVD and 3dB over BM3D [55].  Figure 10: Tensor denoising. DeepTensor enables
denoising via low-rank tensor representation that is often better than state-
of-the-art denoising techniques [35]. Figure 11: Video compressive sensing.
DeepTensor can be used for solving linear inverse problems with compressed
measurements. We simulated video CS following the setup by [54] to combine 32
frames into a single coded image frame. We then recovered with DeepTensor at
full rank, and with 2D TV. DeepTensor produced significantly higher quality of
results. Figure 12: Reconstruction from 3D CT measurements. We utilized
DeepTensor to recover 3D PET volume from limited, noisy CT images. We
expressed the 3D volume as a rank-1000 PARAFAC tensor and then computed CT
images per each slice along 40 angles. DeepTensor resulted in higher SSIM
compared to other approaches.

Tensor denoising. Low dimensional tensor decomposition is a promising approach
to tensor denoising, especially with gross outliers such as salt and pepper
noise. We performed a 3-way PARAFAC decomposition of a subset of faces from
the Yale face database (B) [56] consisting of 160, $192\times 168$-dimensional
images. We then added $30\%$, and $60\%$ salt and pepper noise for a fair
comparison against the Kronecker Decomposition-based approach (KDRSDL) which
is the state-of-the-art in tensor decomposition [35]. We found that an
$\ell_{1}$ penalty worked better than $\ell_{2}$ for DeepTensor, as the noise
was spatially sparse. In both cases, we picked a rank of 2000 for PARAFAC
decomposition. Results are shown in Fig. 10. Evidently, DeepTensor outperforms
KDRSDL, especially in extremely noisy settings.

Video compressive sensing. DeepTensor can also be used for full-rank
decomposition, which is apt for signals such as videos. To test this, we used
our framework on recovery of video frames from spatially multiplexed images.
We relied on the setup from Hitomi et al. [54] where each pixel was sampled at
an arbitrary time frame across multiple frames. We combined 8 frames into one
single coded image and then used DeepTensor to solve the linear inverse
problem. For comparison, we recovered video by solving the linear inverse
problem with a 2D TV over spatial images as a regularizer. We trained
DeepTensor for a total of 10,000 epochs. Figure 11 shows coded image as well
as the 8 recovered images for an example video. DeepTensor not only has higher
accuracy than TV, but the recovered images look visibly similar to ground
truth.

3D reconstruction from CT images. DeepTensor is well suited for tasks such as
recovery of 3D volume from CT scans. To demonstrate the advantages of using a
tensor representation, we rely on PARAFAC decomposition. We approximated a
$256\times 256\times 56$ PET CT scan from Clark et al. [57] with a rank-1000
PARAFAC tensor. Note that although the rank is much larger than any single
dimension, the effective number of parameters are only $15\%$ of the number of
elements in the 3D volume. We added Poisson and readout noise of maximum of
100 photons per voxel and 2 photons respectively. We then simulated 40
tomographic measurements for each slice. 2D TV results were obtained by a TV
penalty on each slice along z-direction. Bacca et al. [41] results were
obtained by representing input as a rank-1000 PARAFAC tensor and using an
untrained 2D network which output 56 channels. 2D TV + PARAFAC results were
obtained with self-supervised learning by representing the volume via
rank-1000 PARAFAC decomposition, and a TV penalty on each slice along z-axis.
Algorithmic reconstruction results were obtained by solving the linear inverse
problem without any other priors. FBPConvNet [58] results were obtained by
using the output of algorithmic reconstruction and then denoising with a pre-
trained model. Finally, the results by [59] were obtained with a self-
supervised learning by using a 3D convolutional neural network. While [59]
utilized an MRI image as input for the network, we used uniform random noise.
Results are visualized in Fig. 12. DeepTensor achieves better reconstruction
accuracy than other approaches in both PSNR and SSIM. We note that pre-trained
approaches such as FBPConvNet Jin et al. [58] can outperform DeepTensor if
trained with the appropriate data.

###  4.2 Classification via low-dimensional projection

A robust low-rank approximation also affects downstream tasks such as
classification. To test this, we worked with an Eigenfaces [20] example for
facial classification. We took 840 images across 28 subjects from the Weizmann
dataset [60]. We used $25\%$ of the data for training an 84-dimensional
subspace via PCA, Independent Component Analysis (ICA) [61], and running
DeepTensor on the sample covariance matrix. To emulate noisy conditions, we
added poisson noise with variable amounts of noise. We then converted the
images to the 84-dimensional space and trained linear and kernel support
vector machine with radial basis function. We cross-validated to choose
penalty that maximized classification accuracy for each individual classifier.
Finally, we evaluated the resultant linear subspace along with SVM on the test
data to compute average accuracy. Figure 2 visualizes the learned basis
vectors with the three approaches, and the average classification accuracy as
a function of input data PSNR. We notice that the basis learned from
DeepTensor is smoother and better representative of the underlying data. In
contrast, PCA and ICA overfit to the noise in data, resulting in a reduction
in classification accuracy.

###  4.3 Time-frequency decomposition

As discussed in section 3.4, DeepTensor can be combined with additional
constraints such as nonnegativity on $U,V$. We validated the advantages of
DeepTensor by performing an NMF on speech data obtained from the
GOOGLECOMMANDS dataset [62]. We first computed spectrograms on all speech data
with a window size of $1024$ samples and a hop size of $32$, resulting in a
$512\times 512$ dimensional time-frequency image. We then added noise as
described in section 3.4, resulting in an input SNR of $4.6$ dB. The
approximation accuracies with DeepTensor, and a baseline NMF [47] NMF
algorithm in Table III. DeepTensor performs significantly better than the
baseline. This ability of DeepTensor to perform better in high noise settings
is of particular significance when speech is recorded in noisy environments.

###  4.4 Choice of rank

As with all matrix and tensor decomposition approaches, the rank of the
decomposition is an important parameter for DeepTensor. However, we now
demonstrate that DeepTensor is less sensitive to the choice of rank than the
SVD in two different settings. In the first experiment, we truncated a
hyperspectral image [63] to rank-20 and swept the rank from 1 to 30. In the
second experiment, we truncated a subset of the Yale-B dataset [56] using
rank-1000 PARAFAC decomposition and then swept the decomposition rank from 10
to 4000. In both cases, we added Poisson ($\lambda_{\text{max}}=100$) and
Gaussian noise ($\sigma=2$) equivalent to a 25 dB measurement PSNR. Figure 13
shows plots of PSNR as a function of rank for both the cases. When the rank is
under-estimated, DeepTensor and SVD achievely similarly low accuracy. However,
when the rank is _over-estimated_ , the achievable accuracy with SVD reduces,
while the accuracy with DeepTensor stays approximately the same. The exact
choice of rank is less important for DeepTensor compared to the SVD, which is
significantly advantageous when the appropriate rank to use is unknown.

TABLE III: NMF on speech data. Average and standard deviation (over $10$ runs) of the PSNR (dB) for GOOGLECOMMANDS [62] in the NMF (nonnegativity of $U,V$) and semi-NMF (nonnegativity of $U$ alone) low-rank decomposition setting for different activation functions enforcing nonnegativity. DeepTensor with ReLU performs better than standard NMF [51]. | GOOGLECOMMANDS NMF | GOOGLECOMMANDS SEMI-NMF
---|---|---
Act. func. | softplus | abs. value | ReLU | softplus | abs. value | ReLU
DeepTensor | 9.0 $\pm$0.03 | 8.7$\pm$0.01 | 8.7$\pm$0.03 | 8.7$\pm$0.09 | 8.8$\pm$0.02 | 8.8$\pm$0.02
baseline ( [51, 47]) | 4.6 | 4.7

(a) Matrix decomposition

(b) PARAFAC tensor decomposition

Figure 13: Effect of choice of rank. We truncated a hyperspectral image to
rank-20 and a tensor to rank-1000 (PARAFAC) and added shot noise. We then
swept rank of decomposition. We observe that DeepTensor is less sensitive to
rank compared to SVD and PARAFAC.

##  5 Conclusions

Discussion. We have demonstrated that self-supervised learning is effective
for solving low-rank tensor and matrix decomposition. Across the board, we see
that DeepTensor is a superior option compared to SVD/PCA when the input SNR is
low, the matrix/tensor values are non-Gaussian distributed, or the inverse
problem is ill-conditioned such as in the case of PCA with limited samples, or
linear inverse problems. Moreover, our separable approximation approach
results in faster approximation of 3D tensors compared to DNs with 3D
convolutional filters.

Future directions. Our experiments relied mostly on 1D or 2D convolutional
filters, whose inductive biases are better suited for signals such as time
series and images. However, the DNs can be chosen specific to the task at
hand, such as fully connected or recurrent networks. DeepTensor can also be
used in non-linear representations, such as local low-rank, or even non-local
low-rank. Such settings increase the range of problems that can be tackled
effectively and are exciting future directions.

Limitations. The current bottleneck of DeepTensor, as opposed to techniques
such as SVD, lies in the training computational complexity. While a single
pass through a DN is much faster than the training of SVD or NMF, the need to
repeatedly iterate between the forward passes and back propagation inherent to
gradient based learning slows DeepTensor training. This opens up interesting
research directions aimed at discovering simpler networks that are faster to
train yet maintain high performance and developing specialized training
algorithms that leverage the low-rank decomposition structure.

##  6 Acknowledgments

This work was supported by NSF grants CCF-1911094, IIS-1838177, and
IIS-1730574; ONR grants N00014-18-12571, N00014-20-1-2534, and MURI
N00014-20-1-2787; AFOSR grant FA9550-22-1-0060; and a Vannevar Bush Faculty
Fellowship, ONR grant N00014-18-1-2047

## References

  * Schönemann [1966] P. H. Schönemann, “A generalized solution of the orthogonal Procrustes problem,” _Psychometrika_ , vol. 31, no. 1, pp. 1–10, 1966.
  * Wold et al. [1987] S. Wold, K. Esbensen, and P. Geladi, “Principal component analysis,” _Chemometrics and Intelligent Laboratory Systems_ , vol. 2, no. 1-3, pp. 37–52, 1987.
  * Jain et al. [2013] P. Jain, P. Netrapalli, and S. Sanghavi, “Low-rank matrix completion using alternating minimization,” in _ACM Symposium on Theory of Computing_ , 2013, pp. 665–674.
  * Candes and Recht [2008] E. J. Candes and B. Recht, “Exact low-rank matrix completion via convex optimization,” in _Allerton Conf. Communication, Control, and Computing_ , 2008.
  * Drineas et al. [2004] P. Drineas, A. Frieze, R. Kannan, S. Vempala, and V. Vinay, “Clustering large graphs via the singular value decomposition,” _Machine Learning_ , vol. 56, no. 1, pp. 9–33, 2004.
  * Zecevic and Siljak [2005] A. I. Zecevic and D. D. Siljak, “Global low-rank enhancement of decentralized control for large-scale systems,” _IEEE Trans. Automatic Control_ , vol. 50, no. 5, pp. 740–744, 2005.
  * Benner and Breiten [2013] P. Benner and T. Breiten, “Low-rank methods for a class of generalized lyapunov equations and related issues,” _Numerische Mathematik_ , vol. 124, no. 3, pp. 441–470, 2013.
  * Liang et al. [2012] X. Liang, X. Ren, Z. Zhang, and Y. Ma, “Repairing sparse low-rank texture,” in _IEEE European Conf. Computer Vision (ECCV)_ , 2012.
  * Ji et al. [2010] H. Ji, C. Liu, Z. Shen, and Y. Xu, “Robust video denoising using low-rank matrix completion,” in _IEEE Comp. Vision and Pattern Recognition (CVPR)_ , 2010.
  * Zhang et al. [2013] H. Zhang, W. He, L. Zhang, H. Shen, and Q. Yuan, “Hyperspectral image restoration using low-rank matrix recovery,” _IEEE Trans. Geoscience and Remote Sensing_ , vol. 52, no. 8, pp. 4729–4743, 2013.
  * Eckart and Young [1936] C. Eckart and G. Young, “The approximation of one matrix by another of lower rank,” _Psychometrika_ , vol. 1, no. 3, pp. 211–218, 1936.
  * Xu et al. [2010] H. Xu, C. Caramanis, and S. Sanghavi, “Robust pca via outlier pursuit,” _arXiv preprint arXiv:1010.4237_ , 2010.
  * Goldfarb and Qin [2014] D. Goldfarb and Z. Qin, “Robust low-rank tensor recovery: Models and algorithms,” _SIAM J. Matrix Analysis and Applications_ , vol. 35, no. 1, pp. 225–253, 2014.
  * Waters et al. [2011] A. E. Waters, A. C. Sankaranarayanan, and R. G. Baraniuk, “SpaRCS: Recovering low-rank and sparse matrices from compressive measurements.” in _Adv. Neural Info. Processing Systems_ , 2011.
  * Ji et al. [2016] T.-Y. Ji, T.-Z. Huang, X.-L. Zhao, T.-H. Ma, and G. Liu, “Tensor completion using total variation and low-rank matrix factorization,” _Info. Sciences_ , vol. 326, pp. 243–257, 2016.
  * He et al. [2015] W. He, H. Zhang, L. Zhang, and H. Shen, “Total-variation-regularized low-rank matrix factorization for hyperspectral image restoration,” _IEEE Trans. Geoscience and Remote Sensing_ , vol. 54, no. 1, pp. 178–188, 2015.
  * Wang et al. [2017] Y. Wang, J. Peng, Q. Zhao, Y. Leung, X.-L. Zhao, and D. Meng, “Hyperspectral image restoration via total variation regularized low-rank tensor decomposition,” _IEEE J. Selected Topics in Appl. Earth Observations and Remote Sensing_ , vol. 11, no. 4, pp. 1227–1243, 2017.
  * Zhao et al. [2020] X.-L. Zhao, W.-H. Xu, T.-X. Jiang, Y. Wang, and M. K. Ng, “Deep plug-and-play prior for low-rank tensor completion,” _Neurocomputing_ , vol. 400, pp. 137–149, 2020.
  * Ke et al. [2020] Z. Ke, W. Huang, J. Cheng, Z. Cui, S. Jia, H. Wang, X. Liu, H. Zheng, L. Ying, Y. Zhu _et al._ , “Deep low-rank prior in dynamic mr imaging,” _arXiv preprint arXiv:2006.12090_ , 2020.
  * Turk and Pentland [1991] M. Turk and A. Pentland, “Eigenfaces for recognition,” _J. Cognitive Neuroscience_ , vol. 3, no. 1, pp. 71–86, 1991.
  * Ulyanov et al. [2018] D. Ulyanov, A. Vedaldi, and V. Lempitsky, “Deep image prior,” in _IEEE Comp. Vision and Pattern Recognition (CVPR)_ , 2018.
  * Heckel and Hand [2018] R. Heckel and P. Hand, “Deep decoder: Concise image representations from untrained non-convolutional networks,” _arXiv preprint arXiv:1810.03982_ , 2018.
  * Pearson [1901] K. Pearson, “Liii. on lines and planes of closest fit to systems of points in space,” _The London, Edinburgh, and Dublin Philosophical Magazine and J. Science_ , vol. 2, no. 11, pp. 559–572, 1901.
  * Lawton and Sylvestre [1971] W. H. Lawton and E. A. Sylvestre, “Self modeling curve resolution,” _Technometrics_ , vol. 13, no. 3, pp. 617–633, 1971.
  * MacQueen et al. [1967] J. MacQueen _et al._ , “Some methods for classification and analysis of multivariate observations,” in _Proc. Fifth Berkeley Symposium on Mathematical Statistics and Probability_ , vol. 1, no. 14, 1967, pp. 281–297.
  * Tufts and Shah [1993] D. W. Tufts and A. A. Shah, “Estimation of a signal waveform from noisy data using low-rank approximation to a data matrix,” _IEEE Trans. Signal Processing_ , vol. 41, no. 4, pp. 1716–1721, 1993.
  * Zhuang and Bioucas-Dias [2016] L. Zhuang and J. M. Bioucas-Dias, “Fast hyperspectral image denoising based on low-rank and sparse representations,” in _IEEE Intl. Geoscience and Remote Sensing Symposium (IGARSS)_ , 2016.
  * Yuan and Oja [2005] Z. Yuan and E. Oja, “Projective nonnegative matrix factorization for image compression and feature extraction,” in _Scandinavian Conf. Image Analysis_ , 2005.
  * Xu et al. [2015] Y. Xu, Z. Wu, J. Li, A. Plaza, and Z. Wei, “Anomaly detection in hyperspectral images based on low-rank and sparse representation,” _IEEE Trans. Geoscience and Remote Sensing_ , vol. 54, no. 4, pp. 1990–2000, 2015.
  * Barratt et al. [2021] S. Barratt, Y. Dong, and S. Boyd, “Low-rank forecasting,” _arXiv preprint arXiv:2101.12414_ , 2021.
  * Tipping and Bishop [1999] M. E. Tipping and C. M. Bishop, “Probabilistic principal component analysis,” _J. Royal Statistical Society: Series B (Statistical Methodology)_ , vol. 61, no. 3, pp. 611–622, 1999.
  * Zhao et al. [2015a] Q. Zhao, L. Zhang, and A. Cichocki, “Bayesian cp factorization of incomplete tensors with automatic rank determination,” _IEEE Trans. Pattern Analysis and Machine Intelligence_ , vol. 37, no. 9, pp. 1751–1763, 2015.
  * Zhao et al. [2015b] Q. Zhao, G. Zhou, L. Zhang, A. Cichocki, and S.-I. Amari, “Bayesian robust tensor factorization for incomplete multiway data,” _IEEE Trans. Neural Networks and Learning Systems_ , vol. 27, no. 4, pp. 736–748, 2015.
  * Chen et al. [2016] X. Chen, Z. Han, Y. Wang, Q. Zhao, D. Meng, and Y. Tang, “Robust tensor factorization with unknown noise,” in _IEEE Comp. Vision and Pattern Recognition (CVPR)_ , 2016.
  * Bahri et al. [2018] M. Bahri, Y. Panagakis, and S. Zafeiriou, “Robust kronecker component analysis,” _IEEE Trans. Pattern Analysis and Machine Intelligence_ , vol. 41, no. 10, pp. 2365–2379, 2018.
  * Xie et al. [2017] Q. Xie, Q. Zhao, D. Meng, and Z. Xu, “Kronecker-basis-representation based tensor sparsity and its applications to tensor recovery,” _IEEE Trans. Pattern Analysis and Machine Intelligence_ , vol. 40, no. 8, pp. 1888–1902, 2017\.
  * Trigeorgis et al. [2014] G. Trigeorgis, K. Bousmalis, S. Zafeiriou, and B. Schuller, “A deep semi-nmf model for learning hidden representations,” in _Intl. Conf. Machine Learning_ , 2014.
  * LeCun et al. [2015] Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” _Nature_ , vol. 521, no. 7553, pp. 436–444, 2015.
  * Gunasekar et al. [2018] S. Gunasekar, J. Lee, D. Soudry, and N. Srebro, “Implicit bias of gradient descent on linear convolutional networks,” _arXiv preprint arXiv:1806.00468_ , 2018.
  * Aittala et al. [2019] M. Aittala, P. Sharma, A. Yedidia, L. Murmann, W. Freeman, G. Wornell, and F. Durand, “Computational mirrors: Blind inverse light transport by deep matrix factorization,” in _Adv. Neural Info. Processing Systems_ , 2019.
  * Bacca et al. [2021] J. Bacca, Y. Fonseca, and H. Arguello, “Compressive spectral image reconstruction using deep prior and low-rank tensor representation,” _Appl. Optics_ , vol. 60, no. 14, pp. 4197–4207, 2021.
  * Arad and Ben-Shahar [2016] B. Arad and O. Ben-Shahar, “Sparse recovery of hyperspectral signal from natural rgb images,” in _IEEE European Conf. Computer Vision (ECCV)_ , 2016\.
  * Vasilescu and Terzopoulos [2002] M. A. O. Vasilescu and D. Terzopoulos, “Multilinear analysis of image ensembles: Tensorfaces,” in _IEEE European Conf. Computer Vision (ECCV)_ , 2002.
  * Kingma and Ba [2015] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in _Intl. Conf. Learning Representations_ , 2015.
  * Paszke et al. [2019] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, “Pytorch: An imperative style, high-performance deep learning library,” in _Adv. Neural Info. Processing Systems_ , 2019.
  * Huang et al. [2017] G. Huang, Y. Li, G. Pleiss, Z. Liu, J. E. Hopcroft, and K. Q. Weinberger, “Snapshot ensembles: Train 1, get M for free,” _arXiv preprint arXiv:1704.00109_ , 2017.
  * Ding et al. [2008] C. H. Ding, T. Li, and M. I. Jordan, “Convex and semi-nonnegative matrix factorizations,” _IEEE Trans. Pattern Analysis and Machine Intelligence_ , vol. 32, no. 1, pp. 45–55, 2008.
  * Ding et al. [2005] C. Ding, X. He, and H. D. Simon, “On the equivalence of nonnegative matrix factorization and spectral clustering,” in _SIAM Intl. Conf. Data Mining_ , 2005.
  * LeCun et al. [1998] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” _Proc. IEEE_ , vol. 86, no. 11, pp. 2278–2324, 1998.
  * Krizhevsky et al. [2009] A. Krizhevsky, G. Hinton _et al._ , “Learning multiple layers of features from tiny images,” 2009.
  * Cichocki and Phan [2009] A. Cichocki and A.-H. Phan, “Fast local algorithms for large scale nonnegative matrix and tensor factorizations,” _IEICE Trans. Fundamentals of Electronics, Communications and Comp. Sciences_ , vol. 92, no. 3, pp. 708–721, 2009.
  * O’Toole and Kutulakos [2010] M. O’Toole and K. N. Kutulakos, “Optical computing for fast light transport analysis.” _ACM Trans. Graphics_ , vol. 29, no. 6, pp. 164:1–12, 2010.
  * Saragadam and Sankaranarayanan [2019] V. Saragadam and A. Sankaranarayanan, “KRISM—Krylov subspace-based optical computing of hyperspectral images,” _ACM Trans. Graphics_ , vol. 38, no. 5, pp. 148:1–14, 2019.
  * Hitomi et al. [2011] Y. Hitomi, J. Gu, M. Gupta, T. Mitsunaga, and S. K. Nayar, “Video from a single coded exposure photograph using a learned over-complete dictionary,” in _IEEE Intl. Conf. Computer Vision (ICCV)_ , 2011.
  * Dabov et al. [2007] K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian, “Image denoising by sparse 3-d transform-domain collaborative filtering,” _IEEE Trans. Image Processing_ , vol. 16, no. 8, pp. 2080–2095, 2007.
  * Belhumeur et al. [1997] P. N. Belhumeur, J. P. Hespanha, and D. J. Kriegman, “Eigenfaces vs. fisherfaces: Recognition using class specific linear projection,” _IEEE Trans. Pattern Analysis and Machine Intelligence_ , vol. 19, no. 7, pp. 711–720, 1997.
  * Clark et al. [2013] K. Clark, B. Vendt, K. Smith, J. Freymann, J. Kirby, P. Koppel, S. Moore, S. Phillips, D. Maffitt, M. Pringle _et al._ , “The cancer imaging archive (tcia): maintaining and operating a public information repository,” _J. Digital Imaging_ , vol. 26, no. 6, pp. 1045–1057, 2013.
  * Jin et al. [2017] K. H. Jin, M. T. McCann, E. Froustey, and M. Unser, “Deep convolutional neural network for inverse problems in imaging,” _IEEE Trans. Image Processing_ , vol. 26, no. 9, pp. 4509–4522, 2017.
  * Gong et al. [2018] K. Gong, C. Catana, J. Qi, and Q. Li, “PET image reconstruction using deep image prior,” _IEEE Trans. Medical Imaging_ , vol. 38, no. 7, pp. 1655–1665, 2018.
  * [60] W. I. of Sciences, “Computer vision databases,” http://www.wisdom.weizmann.ac.il/~vision/FaceBase/.
  * Comon [1994] P. Comon, “Independent component analysis, a new concept?” _Signal Processing_ , vol. 36, no. 3, pp. 287–314, 1994.
  * Warden [2018] P. Warden, “Speech commands: A dataset for limited-vocabulary speech recognition,” _arXiv preprint arXiv:1804.03209_ , 2018.
  * Choi et al. [2017] I. Choi, D. S. Jeon, G. Nam, D. Gutierrez, and M. H. Kim, “High-quality hyperspectral reconstruction using a spectral prior,” _ACM Trans. Graphics_ , vol. 36, no. 6, pp. 218:1–13, 2017.