# A Dataset of Multi-Illumination Images in the Wild

Lukas Murmann1 Michaël Gharbi1, 2 Miika Aittala1 Frédo Durand1 MIT CSAIL1
Adobe Research2

###### Abstract

Collections of images under a single, uncontrolled illumination [42] have
enabled the rapid advancement of core computer vision tasks like
classification, detection, and segmentation [26, 43, 18]. But even with modern
learning techniques, many inverse problems involving lighting and material
understanding remain too severely ill-posed to be solved with single-
illumination datasets. The data simply does not contain the necessary
supervisory signals. Multi-illumination datasets are notoriously hard to
capture, so the data is typically collected at small scale, in controlled
environments, either using multiple light sources [10, 53], or robotic
gantries [8, 20]. This leads to image collections that are not representative
of the variety and complexity of real-world scenes. We introduce a new multi-
illumination dataset of more than 1000 real scenes, each captured in high
dynamic range and high resolution, under 25 lighting conditions. We
demonstrate the richness of this dataset by training state-of-the-art models
for three challenging applications: single-image illumination estimation,
image relighting, and mixed-illuminant white balance.

Figure 1: Using our multi-illumination image dataset of over 1000 scenes, we
can train neural networks to solve challenging vision tasks. For instance, one
of our models can relight an input image to a novel light direction. Specular
highlights pose a significant challenge for many relighting algorithms, but
are handled gracefully by our network. Further analysis is presented in
Section 4.2.

##  1 Introduction

The complex interplay of materials and light is central to the appearance of
objects and to many areas of computer vision, such as inverse problems and
relighting. We argue that research in this area is limited by the scarcity of
datasets — the current data is often limited to individual samples captured in
a lab setting, e.g. [8, 20], or to 2D photographs that do not encode the
variation of appearance with respect to light [42]. While setups such as light
stages, e.g. [10], can capture objects under varying illumination, they are
hard to move and require the acquired object to be fully enclosed within the
stage. This makes it difficult to capture everyday objects in their real
environment.

In this paper, we introduce a new dataset of photographs of indoor surfaces
under varying illumination. Our goal was to capture small scenes at scale (at
least 1,000 scenes). We wanted to be able to bring the capture equipment to
any house, apartment or office and record a scene in minutes. For this, we
needed a compact setup. This appears to be at odds with the requirement that
scenes be illuminated from different directions, since designs such as the
light stage [10] have required a large number of individual lights placed
around the scene. We resolved this dilemma by using indirect illumination and
an electronic flash mounted on servos so that we can control its direction. As
the flash gets rotated, it points to a wall or ceiling near the scene, which
forms an indirect “bounce” light source. The reflected light becomes the
primary illumination for the scene. We also place a chrome and a gray sphere
in the scene as ground truth measurements of the incoming illumination.

Our capture process takes about five minutes per scene and is fully automatic.
We have captured over a thousand scenes, each under 25 different illuminations
for a total of 25,000 HDR images. Each picture comes segmented and labeled
according to material. To the best of our knowledge, this is the first dataset
of its kind: offering both everyday objects in context and lighting
variations.

In Section 4, we demonstrate the generality and usefulness of our dataset with
three learning-based applications: predicting the environment illumination,
relighting single images, and correcting inconsistent white balance in
photographs lit by multiple colored light sources.

We release the full dataset, along with our set of tools for processing and
browsing the data, as well as training code and models.

##  2 Related Work

###  2.1 Multi-Illumination Image Sets

Outdoors, the sky and sun are natural sources of illumination varying over
time. Timelapse datasets have been harvested both “in the wild” from web
cameras [50, 46] or video collections [44], or using controlled camera setups
[45, 29, 27].

Indoor scenes generally lack readily-available sources of illumination that
exhibit significant variations. Some of the most common multi-illumination
image sets are collections of flash/no-flash pairs [39, 12, 2]. These image
pairs can be captured relatively easily in a brief two-image burst and enable
useful applications like denoising, mixed-lighting white balance [22], or even
BRDF capture [1]. Other applications, such as photometric stereo [51] or image
relighting [10, 53], require more than two images for reliable results.

Datasets with more than two light directions are often acquired using complex
hardware setups and multiple light sources [10, 20]. A notable exception,
Mohan  _et al_. [34] proposed a user-guided lighting design system that
combines several illuminations of a single object. Like us, they acquire their
images using a stationary motor-controlled light source and indirect bounce
illumination, although within a more restrictive setup, and at a much smaller
scale. For their work on user-assisted image compositing Boyadzhiev  _et al_.
[7] use a remote-controlled camera and manually shine a hand-held flash at the
scene. This approach ties down the operator and makes acquisition times
prohibitive (they report 20 minutes per scene). Further, hand-holding the
light source makes multi-exposure HDR capture difficult. In contrast, our
system, inspired by work of Murmann  _et al_. [35], uses a motor-controlled
bounce flash, which automates the sampling of lighting directions and makes
multi-exposure HDR capture straightforward.

###  2.2 Material Databases

To faithfully acquire the reflectance of a real-world surface, one typically
needs to observe the surface under multiple lighting conditions. The gold
standard in appearance capture for materials is to exhaustively illuminate the
material sample and photograph it under every pair of viewpoint and light
direction, tabulating the result in a Bidirectional Texture Function (BTF).
The reflectance values can then be read off this large table at render-time
[8].

A variety of BTF datasets have been published [8, 30, 48], but the total
number of samples falls far short of what is typically required by
contemporary learning-based algorithms. A rich literature exists on simple,
light-weight hardware capture systems [17], but the corresponding public
datasets also typically contain less than a few dozen examples. Additionally,
the scope, quality and format of these scattered and small datasets varies
wildly, making it difficult to use them in a unified manner. Our portable
capture device enables us to capture orders of magnitude more surfaces than
existing databases and we record entire scenes at once —rather than single
objects— “in the wild”, outside the laboratory.

Bell  _et al_. [5, 6] collected a large dataset of very loosely controlled
photographs of materials from the Internet, enriched with crowd-sourced
annotations on material class, estimated reflectance, planarity and other
properties. Inspired by their approach, we collect semantic material class
segmentations for our data, which we detail in section 3.3. Unlike ours, their
dataset does not contain lighting variations.

Previous works have investigated the use of synthetic image datasets for
material estimation [37, 49]. But even carefully crafted synthetic datasets
typically do not transfer well to real scenes due remaining differences in
scene complexity, object appearance, and image formation [40].

##  3 Dataset

Our dataset consists of 1016 interior scenes, each photographed under 25
predetermined lighting directions, sampled over the upper hemisphere relative
to the camera. The scenes depict typical domestic and office environments. To
maximize surface and material diversity, we fill the scenes with miscellaneous
objects and clutter found in our capture locations. A selection of scenes is
presented in Figure 2.

Figure 2: Eight representative scenes from our dataset. Each scene is captured
under 25 unique light directions, 4 of which are shown in the figure. We
strived to include a variety of room and material types in the dataset.
Material types are annotated using dense segmentation masks which we show on
the right.

In the spirit of previous works [34, 35], our lighting variations are achieved
by directing a concentrated flash beam towards the walls and ceiling of the
room. The bright spot of light that bounces off the wall becomes a virtual
light source that is the dominant source of illumination for the scene in
front of the camera.

We can rapidly and automatically control the approximate position of the
bounce light simply by rotating the flash head over a standardized set of
directions (Figure 3). This alleviates the need to re-position a physical
light source manually between each exposure [7, 32]. Our camera and flash
system is more portable than dedicated light sources, which simplifies its
deployment “in the wild”.

Figure 3: a) Most of our photographs are lit by pointing a flash unit towards
the walls and the ceiling, creating a virtual bounce light source that
illuminates the scene directionally. b) Some of the photographs are captured
under direct flash illumination, where the beam of light intersects the field
of view of the camera. c) The flash directions used in our dataset, relative
to the camera viewing direction and frustum (black). The directions where
direct flash illumination is seen in the view are shown in red, and the fully
indirect ones in blue.

The precise intensity, sharpness and direction of the illumination resulting
from the bounced flash depends on the room geometry and its materials. We
record these lighting conditions by inserting a pair of light probes, a
reflective chrome sphere and a plastic gray sphere, at the bottom edge of
every image [9]. In order to preserve the full dynamic range of the light
probes and the viewed scene, all our photographs are taken with bracketed
exposures.

As a post-process, we annotate the light probes, and collect dense material
labels for every scene using crowd-sourcing, as described in Section 3.3.

###  3.1 Image Capture

Our capture device consists of a mirrorless camera (_Sony $\alpha$6500_), and
an external flash unit (_Sony HVL-F60M_) which we equipped with two servo
motors. The servos and camera are connected to a laptop, which automatically
aims the flash and fires the exposures in a pre-programmed sequence. The 24mm
lens provides a $52^{\circ}$ horizontal and $36^{\circ}$ vertical field of
view.

At capture time, we rotate the flash in the 25 directions depicted in Figure
3, and capture a 3-image exposure stack for each flash direction. We switch
off any room lights and shut window blinds, which brings the average intensity
of the ambient light to less than 1% of the intensity of the flash
illumination. For completeness, we capture an extra, ambient-only, exposure
stack with the flash turned off.

The 25 flash directions are evenly spaced over the upper hemisphere. In 18 of
these directions, the cone of the flash beam falls outside the view of the
camera, and consequently, the image is only lit by the secondary illumination
from the bounce. In the remaining 7 directions, part or all of the image is
lit by the flash directly. In particular, one of the directions corresponds to
a typical frontal flash illumination condition.

Capturing a single set (78 exposures) takes about five minutes with our
current setup. The capture speed is mostly constrained by the flash’s
recycling time (around 3.5 seconds at full power). Additional battery extender
packs or high-voltage batteries can reduce this delay for short bursts. We
found them less useful when capturing many image sets in a single session,
where heat dissipation becomes the limiting factor.

###  3.2 HDR processing

The three exposures for each light direction are bracketed in 5-stops
increments to avoid clipped highlights and excessive noise in the shadows. The
darkest frame is exposed at $f/22$ ISO100, the middle exposure is $f/5.6$
ISO200, and the brightest image is recorded at $f/5.6$ ISO6400. The shutter
speed is kept at the camera’s fastest flash sync time, $1/160^{\text{th}}$
second to minimize ambient light. The camera sensor has 13 bits of useful
dynamic range at ISO100 (9 bits at ISO6400). Overall, our capture strategy
allows us to reconstruct HDR images with at least 20 bits of dynamic range.

Using the aperture setting to control exposure bracketing could lead to
artifacts from varying defocus blur. We limit this effect by manually focusing
the camera to the optimal depth, and by avoiding viewpoints with depth
complexity beyond the depth-of-field that is achieved at $f/5.6$.

After merging exposures, we normalize the brightness of the HDR image by
matching the intensity of the diffuse gray sphere. The gray sphere also serves
as a reference point for white balance. This is especially useful in brightly-
colored rooms that could otherwise cause color shifts.

###  3.3 Dataset Statistics

To ensure our data is representative of many real-world scenes, we collected
images in 95 different rooms throughout 12 residential and office buildings,
which allowed us to capture a variety of materials and room shapes.

In order to analyze the materials found throughout our dataset, we obtain
dense material labels segmented by crowd workers, as shown in Figure 2 and 4.
These annotations are inspired by the material annotations collected by Bell
_et al_. [5], whose publicly available source code forms the basis of our
annotation pipeline.

Figure 4 shows the distribution of materials in our data set. Specific room
types have material distributions that differ markedly from the unconditioned
distribution. For example, in kitchens we frequently find metal and wooden
surfaces, but few fabrics (less than 5% of pixels). Bedrooms scenes on the
other hand show fabrics in 38% of the pixels, but contain almost no metal
surfaces (less than 4%).

Figure 4: Crowd-sourced material annotations show that painted surfaces,
fabrics, wood, and metal are the most frequently occurring materials in our
dataset, covering more than 60% of all pixels. For some room types, the
material distribution is markedly different from the average. For example, in
kitchens we frequently encounter wood (shelves) and metal (appliances),
bedroom scenes show a high frequency of fabrics, and the material distribution
of bathrooms is skewed towards tiles and ceramics.

##  4 Applications

In this section we present learning-based solutions to three long-standing
vision problems: single-image lighting estimation, single-image relighting and
mixed-illuminant white-balance. Our models are based on standard convolutional
architectures, such as the U-net [41]. For all experiments, we normalize the
exposure and white balance of our input images with respect to the gray
sphere. We also mask out the chrome and gray spheres with black squares both
at training and test time to prevent the networks from using this information
directly.

###  4.1 Predicting Illumination from a Single Image

Single-frame illumination estimation is a challenging problem that arises e.g.
when one wishes to composite a computer-generated object into a real-world
image [9]. Given sufficient planning (as is common for visual effects in
movies), illumination can be recorded at the same time the backdrop is
photographed (e.g. by using a light probe). This is rarely the case for a
posteriori applications. In particular, with the growing interest in augmented
reality and mixed reality, the problem of estimating the illumination in
uncontrolled scenes has received increased attention.

Several methods have explored this problem for outdoor images [28, 14, 15, 19,
31] as well as indoor environments [13]. Noting the lack of viable training
data for indoor scenes, Gardner  _et al_. explicitly detect light sources in
LDR panoramas [52]. Our proposed dataset includes HDR light probes in every
scene which makes it uniquely suitable for illumination prediction and other
inverse rendering tasks [4] in indoor environments.

####  4.1.1 Model

We approach the single image illumination prediction problem by training a
convolutional network on $256\times 256$ image crops from our dataset. We ask
the network to predict a $16\times 16$ RGB chrome sphere, that we compare to
our ground truth probe using an $L_{2}$ loss. The $256\times 256$ input patch
is processed by a sequence of convolution, ReLU, and Max-pooling layers, where
we halve the spatial resolution and double the number of feature maps after
each convolution. When the spatial resolution reaches $1\times 1$ pixel, we
apply a final, fully-connected layer to predict 768 numbers: these are
reshaped into a $16\times 16$ RGB light probe image. Exponentiating this
images yields the final, predicted environment map. We provide the network
details in supplemental material.

####  4.1.2 Compositing synthetic objects

Figure 5 shows some compositing results on a held-out test set. While our
model does not always capture the finer color variations of the diffuse global
illumination, its prediction of the dominant light source is accurate. Figure
7 shows one of the test scenes, with synthetic objects composited. The
synthetic geometry is illuminated by our predicted environment maps and
rendered with a path-tracer. Note that the ground truth light probes visible
in the figure were masked during inference, and therefore _not_ seen by our
network.

Figure 5: As the first application of our dataset, we train a deep network to
predict environment maps from single input images. Our model consistently
predicts the dominant light direction of the ground truth environment map. The
model successfully estimates illumination based on shiny objects (a and g) and
diffuse reflectors (e.g. row f). Rows h) and i) show failure cases where the
network predicts low-confidence outputs close to the mean direction. We
compare to Gardner  _et al._ ’s algorithm [13] which, while predicting
visually plausible environment maps, lacks the precise localization of
highlights shown by our technique. (Please ignore the vertical seam in Gardner
_et al_.’s result. Their model uses a differing spherical parametrization,
which we remap to our coordinate system for display.)

####  4.1.3 Evaluation

We evaluated our model on a held-out test subset of our data and compared it
to a state-of-the-art illumination prediction algorithm by Gardner  _et al_.
[13]. Compared to their technique, our model more accurately predicts the
direction of the bounce light source (see Figure 5). In comparison, Gardner
_et al_.’s model favors smoother environment maps and is less likely to
predict the directional component of the illumination. For visual comparison,
we warp the $360^{\circ}$ panoramas produced by their technique to the chrome
sphere parameterization that is used throughout our paper.

In order to quantify the performance of the chrome sphere predictor, we
analyzed the angular distance between the predicted and true center of the
light source for 30 test scenes. Our technique achieves a mean angular error
of $26.6^{\circ}$ (std. dev. $10.8^{\circ}$), significantly outperforming
Gardner  _et al_.’s method, which achieves a mean error of $68.5^{\circ}$
(std. dev. $38.4^{\circ}$). Visual inspection suggests that the remaining
failure cases of our technique are due to left/right symmetry of the scene
geometry, mirrors, or simply lack of context in the randomly chosen input
crops (see Figure 5 bottom).

We verified that our model generalizes beyond bounce flash light sources using
a small test set of pictures taken under general non-bounce flash
illumination. The results of this experiment are presented in Figure 6.

Figure 6: We validate our model’s ability to generalize beyond bounce flash
illumination. The top row show an office scene with regular room lights. The
bottom two rows show a scene illuminated by softboxes, first lit from the
right and then from the left. The second set of results suggests that our
model can aggregate information from shadows to infer the light source
position. Figure 7: We use the environment maps predicted by our model to
illuminate virtual objects and composite them onto one of our test scenes. The
light probe in the bottom of the frame shows the ground truth lighting. (Note
that these probes are masked out before feeding the image to the network).

###  4.2 Relighting

A robust and straightforward method to obtain a relightable model of a scene
is to capture a large number of basis images under varying illumination, and
render new images as linear combinations of the basis elements. Light stages
[10] work according to this principle. With finitely many basis images,
representing the high frequency content of a scene’s light transport operator
(specular highlights, sharp shadow boundaries, etc.) is difficult. Despite
this fundamental challenge, prior work has successfully exploited the
regularity of light transport in natural scenes to estimate the transport
operator from sparse samples [36, 38, 47]. Recent approaches have employed
convolutional neural networks for the task, effectively learning the
regularities of light transport from synthetic training data and reducing the
number of images required for relighting to just a handful [53].

In our work, we demonstrate relighting results from a _single input image_ on
real-world scenes that exhibit challenging phenomena, such as specular
highlights, self-shadowing, and interreflections.

####  4.2.1 Model

We cast single-image relighting as an image-to-image translation problem. We
use a convolutional neural network based on the U-net [41] architecture to map
from images illuminated from the left side of the camera, to images lit from
the right (see supplemental material for details). Like in Section 4.1, we
work in the log-domain to limit the dynamic range of the network’s internal
activations. We use an $L_{1}$ loss to compare the _spatial gradients_ of our
relit output to those of the reference image, lit from the right. We found
this gradient-domain loss to yield sharper results. It also allows the network
to focus more on fine details without being overly penalized for low-frequency
shifts due to the global intensity scaling ambiguity (the left- and right-lit
images might not have the same average brightness, depending on room
geometry).

Figure 8:  The second application of our data is learning image relighting
using a single input image. The trained model synthesizes moving specular
highlights (a, b, c) and diffuse shading (b, d), and correctly renders shadows
behind occluders (d). For the baseline result, we first estimate normals and
diffuse albedo using published models, and then re-render the image as lit by
the target environment map.

####  4.2.2 Evaluation

Our model faithfully synthesizes specular highlights, self- and cast-shadows,
as well as plausible shading variations. Without a large-scale training
dataset for an end-to-end solution, a valid straw man approach would be to use
existing techniques and decompose the input into components that can be
manipulated for relighting (e.g. normals and albedo). We provide such a
baseline for comparison. It uses a combination of deep single-image normal
estimation [54] and learned intrinsic image decomposition [24] (see Figure 8).
Both components are state-of-the-art in their respective fields and have
source code and trained models publicly available.

This baseline illustrates the challenges in decomposing the single-image
relighting problem into separate inverse rendering sub-problems. Specifically,
major sources of artifacts include: incorrect or blurry normals, and incorrect
surface albedo due to the overly simplistic Lambertian shading model. The
normals and reflectance estimation networks were independently trained to
solve two very difficult problems. This is a arguably more challenging than
our end-to-end relighting application and, also unnecessary for plausible
relighting.

Our end-to-end solution does not enforce this explicit geometry/material
decomposition and yields far superior results. More relighting outputs
produced by our model are shown in Figure 1 and in the supplemental material.

###  4.3 Mixed-Illumination White-Balance

White-balancing an image consists in neutralizing the color cast caused by
non-standard illuminants, so that the photograph appears lit by a standardized
(typically white) light source. White-balance is under-constrained, and is
often solved by modeling and exploiting the statistical regularities in the
colors of lights and objects. The most common automatic white balance
algorithms make the simplifying assumption that the entire scene is lit by a
single illuminant. See [16] for a survey. This assumption rarely holds in
practice. For instance, an interior scene might exhibit a mix of bluish light
(e.g. from sky illuminating the scene through a window) and warmer tones (e.g.
from the room’s artificial tungsten light bulbs). Prior work has formulated a
local gray-world assumption to generalize white balance to the mixed-lighting
case [11], exploiting the difference in light colors in shadowed vs. sunlit
areas for outdoor scenes [25], or flash/no-flash image pairs [33, 21, 23].

Here again, we approach white-balancing as a supervised learning problem.
Because our dataset contains high-dynamic range linear images with multiple
lighting conditions, it can be used to simulate a wide range of new mixed-
color illuminations by linear combinations. We exploit this property to
generate a training dataset for a neural network that removes inconsistent
color casts from mixed-illumination photographs.

####  4.3.1 Mixed-illuminant data generation

To create a training set of input/output pairs, we extract $256\times 256$
patches from our scenes at multiple scales. For each patch, we choose a random
number of light sources $n\in\\{1,\ldots,4\\}$. Each light index corresponds
to one of 25 available flash directions, selected uniformly at random without
replacement. We denote by $I_{1},\ldots,I_{n}$ the corresponding images.

For each light $i$, we sample its color with hue in $[0,360]$, and saturation
in $[0.5,1]$, represented as a positive RGB gain vector $\alpha_{i}$,
normalized such that $||\alpha_{i}||_{1}$ = 1. We randomize the relative power
of the light sources by sampling a scalar exposure gain $g_{i}$ uniformly (in
the log domain) between $-3$ and $+2$ stops. We finally assemble our mixed-
colored input patch as the linear combination:
$I=\frac{1}{n}\sum_{i=1}^{n}\alpha_{i}g_{i}I_{i}$.

We define the color-corrected target similarly, but without the color gains:
$O=\frac{1}{n}\sum_{i=1}^{n}g_{i}I_{i}$.

Figure 9: The first row shows a mixed white-balance result on an image from a
held-out test set. The input (left) is a linear combination of several (two
here) illuminations of the same scene under varied color and intensity. The
reference image (right) has the same energy but no color cast. Our output
(middle) successfully removes the green and magenta shifts. The simple model
we trained on our dataset, generalizes well to unseen, real RAW images (second
row). The most noticeable failure case are skin tones (third row), which are
entirely absent from our data set of static scenes.

####  4.3.2 Model

Like for the relighting problem, we use a simple convolutional network based
on a U-net [41] to predict white-balanced images from mixed-lighting inputs
(details in the supplemental).

To reduce the number of unknowns and alleviate the global scale ambiguity, we
take the log transform of the input and target images, and decompose them in 2
chrominance $u$, $v$, and a luminance component $l$ [3]:

$\displaystyle u$ $\displaystyle=\log(I^{r}+\epsilon)-\log(I^{g}+\epsilon),$
(1) $\displaystyle v$
$\displaystyle=\log(I^{b}+\epsilon)-\log(I^{g}+\epsilon),$ (2) $\displaystyle
l$ $\displaystyle=\log(I^{g}+\epsilon),$ (3)

where $\epsilon=10^{-4}$, and the superscripts stand for the RGB color
channels.

Our network takes as input $u,v,l$ and outputs two correctly white-balanced
chroma components. We assemble the final RGB output from $l$ and the predicted
chroma, using the reverse transform. Our model is trained to minimize an
$L_{2}$ loss over the chroma difference.

####  4.3.3 Results

Our model successfully removes the mixed color cast on our test set and
generalizes beyond, to real-world images. The main limitation of our technique
is its poor generalization to skin tones, to which the human eye is
particularly sensitive, but which are absent from our dataset of static indoor
scenes. We present qualitative results in Figure 9 and in the supplemental
video.

##  5 Limitations

A limitation of our capture methodology is that it requires good bounce
surfaces placed not too far from the scene. This precludes most outdoor scenes
and large indoor rooms like auditoriums. Our capture process requires the
scene to remain static for several minutes, which keeps us from capturing
human subjects. Compared to light stages or robotic gantries, the placement of
our bounce light sources has more variability due to room geometry, and the
bounce light is softer than hard lighting from point light sources. Finally,
we only capture 25 different illuminations, which is sufficient for diffuse
materials but under-samples highly specular ones.

##  6 Conclusions

We have introduced a new dataset of indoor object appearance under varying
illumination. We have described a novel capture methodology based on an
indirect bounce flash which enables, in a compact setup, the creation of
virtual light sources. Our automated capture protocol allowed us to acquire
over a thousand scenes, each under 25 different illuminations. We presented
applications in environment map estimation, single-image relighting, and mixed
white balance that can be trained from scratch using our dataset. We will
release the code and data.

## Acknowledgments

This work was supported in part by the DARPA REVEAL Program under Contract No.
HR0011- 16-C-0030.

## References

  * [1] Miika Aittala, Tim Weyrich, and Jaakko Lehtinen.  Two-shot svbrdf capture for stationary materials.  ACM SIGGRAPH, 2015.
  * [2] Yağız Aksoy, Changil Kim, Petr Kellnhofer, Sylvain Paris, Mohamed Elgharib, Marc Pollefeys, and Wojciech Matusik.  A dataset of flash and ambient illumination pairs from the crowd.  ECCV, 2018.
  * [3] Jonathan T. Barron.  Convolutional color constancy.  ICCV, 2015.
  * [4] Jonathan T. Barron and Jitendra Malik.  Shape, illumination, and reflectance from shading.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(8):1670–1687, Aug 2015.
  * [5] Sean Bell, Paul Upchurch, Noah Snavely, and Kavita Bala.  OpenSurfaces: A richly annotated catalog of surface appearance.  ACM SIGGRAPH, 2013.
  * [6] Sean Bell, Paul Upchurch, Noah Snavely, and Kavita Bala.  Material recognition in the wild with the materials in context database.  CVPR, 2015.
  * [7] Ivaylo Boyadzhiev, Sylvain Paris, and Kavita Bala.  User-assisted image compositing for photographic lighting.  ACM SIGGRAPH, 2013.
  * [8] Kristin J. Dana, Bram van Ginneken, Shree K. Nayar, and Jan J. Koenderink.  Reflectance and texture of real-world surfaces.  ACM Transactions on Graphics, 1999.
  * [9] Paul Debevec.  Rendering synthetic objects into real scenes: Bridging traditional and image-based graphics with global illumination and high dynamic range photography.  ACM SIGGRAPH, 1998.
  * [10] Paul Debevec, Tim Hawkins, Chris Tchou, Haarm-Pieter Duiker, Westley Sarokin, and Mark Sagar.  Acquiring the reflectance field of a human face.  ACM SIGGRAPH, 2000.
  * [11] Marc Ebner.  Combining white-patch retinex and the gray world assumption to achieve color constancy for multiple illuminants.  In Joint Pattern Recognition Symposium, pages 60–67. Springer, 2003\.
  * [12] Elmar Eisemann and Frédo Durand.  Flash photography enhancement via intrinsic relighting.  ACM SIGGRAPH, 2004.
  * [13] Marc-André Gardner, Kalyan Sunkavalli, Ersin Yumer, Xiaohui Shen, Emiliano Gambaretto, Christian Gagné, and Jean-François Lalonde.  Learning to predict indoor illumination from a single image.  ACM SIGGRAPH Asia, 2017.
  * [14] Stamatios Georgoulis, Konstantinos Rematas, Tobias Ritschel, Mario Fritz, Tinne Tuytelaars, and Luc Van Gool.  Natural illumination from multiple materials using deep learning.  CoRR, 2016.
  * [15] Stamatios Georgoulis, Konstantinos Rematas, Tobias Ritschel, Efstratios Gavves, Mario Fritz, Luc Van Gool, and Tinne Tuytelaars.  Reflectance and natural illumination from single-material specular objects using deep learning.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017\.
  * [16] Arjan Gijsenij, Theo Gevers, and Joost Van De Weijer.  Computational color constancy: Survey and experiments.  IEEE Transactions on Image Processing, 2011.
  * [17] Dar’ya Guarnera, Giuseppe Claudio Guarnera, Abhijeet Ghosh, Cornelia Denk, and Mashhuda Glencross.  BRDF Representation and Acquisition.  Computer Graphics Forum, 2016.
  * [18] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross B. Girshick.  Mask R-CNN.  ICCV, 2017.
  * [19] Yannick Hold-Geoffroy, Kalyan Sunkavalli, Sunil Hadap, Emiliano Gambaretto, and Jean-François Lalonde.  Deep outdoor illumination estimation.  CVPR, 2017.
  * [20] Michael Holroyd, Jason Lawrence, and Todd Zickler.  A coaxial optical scanner for synchronous acquisition of 3D geometry and surface reflectance.  ACM SIGGRAPH, 2010.
  * [21] Zhuo Hui, Aswin C Sankaranarayanan, Kalyan Sunkavalli, and Sunil Hadap.  White balance under mixed illumination using flash photography.  IEEE International Conference on Computational Photography, 2016\.
  * [22] Zhuo Hui, Kalyan Sunkavalli, Sunil Hadap, and Aswin C. Sankaranarayanan.  Post-capture lighting manipulation using flash photography.  CoRR, 2017.
  * [23] Zhuo Hui, Kalyan Sunkavalli, Sunil Hadap, and Aswin C Sankaranarayanan.  Illuminant spectra-based source separation using flash photography.  CVPR, 2018.
  * [24] Carlo Innamorati, Tobias Ritschel, Tim Weyrich, and Niloy J. Mitra.  Decomposing single images for layered photo retouching.  Computer Graphics Forum, 2017.
  * [25] Rei Kawakami, Katsushi Ikeuchi, and Robby T Tan.  Consistent surface color for texturing large objects in outdoor scenes.  ICCV, 2005.
  * [26] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton.  Imagenet classification with deep convolutional neural networks.  NIPS, 2012.
  * [27] Pierre-Yves Laffont, Zhile Ren, Xiaofeng Tao, Chao Qian, and James Hays.  Transient attributes for high-level understanding and editing of outdoor scenes.  ACM SIGGRAPH, 2014.
  * [28] Jean-François Lalonde, Alexei A. Efros, and Srinivasa G. Narasimhan.  Estimating the natural illumination conditions from a single outdoor image.  International Journal of Computer Vision, 2011.
  * [29] Jean-François Lalonde and Iain Matthews.  Lighting estimation in outdoor image collections.  International Conference on 3D Vision, 2014.
  * [30] Jason Lawrence, Aner Ben-Artzi, Christopher DeCoro, Wojciech Matusik, Hanspeter Pfister, Ravi Ramamoorthi, and Szymon Rusinkiewicz.  Inverse shade trees for non-parametric material representation and editing.  ACM SIGGRAPH, 2006.
  * [31] Stephen Lombardi and Ko Nishino.  Reflectance and illumination recovery in the wild.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016\.
  * [32] Vincent Masselus, Philip Dutré, and Frederik Anrys.  The free-form light stage.  Technical report, Departement of Computer Science, KU Leuven, 2002.
  * [33] Ryo Matsuoka, Tatsuya Baba, Mia Rizkinia, and Masahiro Okuda.  White balancing by using multiple images via intrinsic image decomposition.  IEICE Transactions on Information and Systems, 2015.
  * [34] Ankit Mohan, Reynold Bailey, Jonathan Waite, Jack Tumblin, Cindy Grimm, and Bobby Bodenheimer.  Tabletop computed lighting for practical digital photography.  IEEE Transactions on Visualization and Computer Graphics, 2007.
  * [35] Lukas Murmann, Abe Davis, Jan Kautz, and Frédo Durand.  Computational bounce flash for indoor portraits.  ACM SIGGRAPH Asia, 2016.
  * [36] Shree K. Nayar, Peter N. Belhumeur, and Terry E. Boult.  Lighting sensitive display.  ACM Transactions on Graphics, 2004.
  * [37] Keunhong Park, Konstantinos Rematas, Ali Farhadi, and Steven M Seitz.  Photoshape: photorealistic materials for large-scale shape collections.  ACM SIGGRAPH Asia, 2018.
  * [38] Pieter Peers, Dhruv K. Mahajan, Bruce Lamond, Abhijeet Ghosh, Wojciech Matusik, Ravi Ramamoorthi, and Paul Debevec.  Compressive light transport sensing.  ACM Transactions on Graphics, 2009.
  * [39] Georg Petschnigg, Richard Szeliski, Maneesh Agrawala, Michael Cohen, Hugues Hoppe, and Kentaro Toyama.  Digital photography with flash and no-flash image pairs.  ACM SIGGRAPH, 2004.
  * [40] Stephan R Richter, Vibhav Vineet, Stefan Roth, and Vladlen Koltun.  Playing for data: Ground truth from computer games.  ECCV, 2016.
  * [41] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  International Conference on Medical image computing and computer-assisted intervention, 2015.
  * [42] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.  ImageNet Large Scale Visual Recognition Challenge.  International Journal of Computer Vision, 2015.
  * [43] Pierre Sermanet, David Eigen, Xiang Zhang, Michaël Mathieu, Rob Fergus, and Yann LeCun.  Overfeat: Integrated recognition, localization and detection using convolutional networks.  CoRR, 2013.
  * [44] Yichang Shih, Sylvain Paris, Frédo Durand, and William T Freeman.  Data-driven hallucination of different times of day from a single outdoor photo.  ACM SIGGRAPH Asia 2013, 2013.
  * [45] Jessi Stumpfel, Chris Tchou, Andrew Jones, Tim Hawkins, Andreas Wenger, and Paul Debevec.  Direct hdr capture of the sun and sky.  International Conference on Computer Graphics, Virtual Reality, Visualisation and Interaction in Africa, 2004.
  * [46] Kalyan Sunkavalli, Fabiano Romeiro, Wojciech Matusik, Todd Zickler, and Hanspeter Pfister.  What do color changes reveal about an outdoor scene?  CVPR, 2008.
  * [47] Jiaping Wang, Yue Dong, Xin Tong, Zhouchen Lin, and Baining Guo.  Kernel nyström method for light transport.  ACM SIGGRAPH, 2009.
  * [48] Michael Weinmann, Juergen Gall, and Reinhard Klein.  Material classification based on training data synthesized using a btf database.  In European Conference on Computer Vision (ECCV), pages 156–171, 2014.
  * [49] Michael Weinmann, Juergen Gall, and Reinhard Klein.  Material classification based on training data synthesized using a btf database.  ECCV, 2014.
  * [50] Yair Weiss.  Deriving intrinsic images from image sequences.  ICCV, 2001.
  * [51] Robert J. Woodham.  Photometric method for determining surface orientation from multiple images.  Optical Engineering, 1980.
  * [52] Jianxiong Xiao, Krista A. Ehinger, Aude Oliva, and Antonio Torralba.  Recognizing scene viewpoint using panoramic place representation.  CVPR, 2012.
  * [53] Zexiang Xu, Kalyan Sunkavalli, Sunil Hadap, and Ravi Ramamoorthi.  Deep image-based relighting from optimal sparse samples.  ACM Transactions on Graphics, 2018.
  * [54] Yinda Zhang, Shuran Song, Ersin Yumer, Manolis Savva, Joon-Young Lee, Hailin Jin, and Thomas Funkhouser.  Physically-based rendering for indoor scene understanding using convolutional neural networks.  CVPR, 2017.


# The slice rank of a direct sum

###### Abstract

We show that the slice rank of the direct sum of two tensors is equal to the
sum of their slice ranks. This result generalizes the fact, shown by Tao, that
the slice rank of a diagonal tensor is equal to the number of non-zero entries
of that tensor. The proof uses the duality method of Sawin and Tao in a
straightforward way.

##  1 Introduction

By a $d$-_tensor_ over a field $\mathbb{F}$, we shall mean a function of the
form $T:X_{1}\times\dots\times X_{d}\to\mathbb{F}$, where $X_{1},\dots,X_{d}$
are finite sets. When $d=2$, we can think of $T$ as an $|X_{1}|\times|X_{2}|$
matrix, and an important invariant associated with it is its rank. It is
natural to try to generalize the notion of rank to higher-order tensors, but
it turns out that there are several competing generalizations, each with
different advantages and disadvantages, more than one of which is genuinely
useful.

If $u_{i}:X_{i}\to\mathbb{F}$ for $i=1,\dots,d$, write
$u_{1}\otimes\dots\otimes u_{d}$ for the tensor $T$ given by

$T(x_{1},\dots,x_{d})=u_{1}(x_{1})u_{2}(x_{2})\dots u_{d}(x_{d}).$

Tensors of this form are said to have tensor rank equal to 1. Then the _tensor
rank_ of $T$ is the smallest $r$ such $T$ is a sum of $r$ tensors of tensor
rank 1. Note that when $d=2$ this definition is one of the standard ways of
defining the rank of a matrix.

A second definition of rank can be obtained by changing what we count as a
rank-1 tensor. Let us say that a tensor has partition rank 1 if there is a
partition of $\\{1,\dots,d\\}$ into non-empty sets $S_{1}$ and $S_{2}$ and $T$
splits up as a product $T=T_{1}T_{2}$, where each $T_{i}$ depends only on the
variables $x_{j}$ such that $j\in S_{i}$. Note that for $d\geq 2$ a tensor of
tensor rank 1 has partition rank 1 and that any partition of $\\{1,\dots,d\\}$
into two disjoint sets can be used. In general, the _partition rank_ of a
tensor $T$ is the smallest $r$ such that $T$ is a sum of $r$ tensors of
partition rank 1.

An intermediate definition is that of slice rank. Here, the tensors of rank 1
are defined as for partition rank except that we insist that $S_{1}$ is a
singleton. So for instance if $d=4$, then a tensor of the form
$u(x_{1},x_{2})v(x_{3},x_{4})$ has partition rank 1 but does not necessarily
have slice rank 1, whereas a tensor of the form $u(x_{3})v(x_{1},x_{2},x_{4})$
has slice rank 1 and partition rank 1. As one would expect, the _slice rank_
of a tensor $T$ is the smallest $r$ such that $T$ is a sum of $r$ tensors of
slice rank 1.

Since a tensor of tensor rank 1 has slice rank 1 and a tensor of slice rank 1
has partition rank 1, we find that the tensor rank is at least as big as the
slice rank, which is at least as big as the partition rank.

In a remarkable and very quick sequence of developments in 2016, Croot, Lev
and Pach proved that subsets of $\mathbb{Z}_{4}^{n}$ that do not contain an
arithmetic progression of length 3 have exponentially small density [2], and
then Ellenberg and Gijswijt proved the same for subsets of
$\mathbb{F}_{3}^{n}$, thereby solving the famous cap-set problem in additive
combinatorics [4]. Soon after that, Tao gave a more conceptual reformulation
of the argument [9], in which the following lemma (in the case $d=3$) played a
crucial role.

######  Lemma 1.1 (Tao).

Let $T:X^{d}\to\mathbb{F}$ be a $d$-tensor and suppose that
$T(x_{1},\dots,x_{d})=0$ except if $x_{1}=x_{2}=\dots=x_{d}$. Then the slice
rank of $T$ is equal to the number of non-zero entries of $T$.

We briefly sketch his proof in the case $d=3$. Suppose that one has a
decomposition

$T(x,y,z)=\sum_{i=1}^{r}a_{i}(x)b_{i}(y,z)+\sum_{j=1}^{s}c_{j}(y)d_{j}(x,z)+\sum_{k=1}^{t}e_{k}(z)f_{k}(x,y).$

Then a simple linear algebra argument shows that there is a function
$h:X\to\mathbb{F}$ such that $\sum_{x}h(x)a_{i}(x)=0$ for $i=1,\dots,r$ and
such that $h(x)=0$ for at most $r$ values of $x$. Take such an $h$ and
consider the matrix $M(y,z)=\sum_{x}h(x)T(x,y,z)$. Then $M$ is diagonal, and
$M(y,y)=h(y)T(y,y,y)$. If the number of non-zero entries of $T$ is $m$, then
the number of non-zero entries of $M$ is at least $m-r$, so $M$ has rank at
least $m-r$.

On the other hand, $M$ has a decomposition

$M(y,z)=\sum_{j=1}^{s}c_{j}(y)u_{j}(z)+\sum_{k=1}^{t}v_{k}(y)e_{k}(z),$

where $u_{j}(z)=\sum_{x}h(x)d_{j}(x,z)$ and $v_{k}(y)=\sum_{x}h(x)f_{k}(x,y)$
for each $j,k$. It follows that $M$ has rank at most $s+t$.

Putting these two estimates together, we deduce that $m-r\leq s+t$. Since the
initial decomposition of $T$ was arbitrary, this proves that the slice rank of
$T$ is at least $m$, as we wanted.

In this paper, we shall prove the following result. Suppose we have finite
sets $X_{1},\dots,X_{d}$ and for each $i$ let $X_{i}=X_{i}^{1}\cup X_{i}^{2}$,
where this is a disjoint union. Given two tensors
$T_{i}:X_{1}^{i}\times\dots\times X_{d}^{i}\to\mathbb{F}$, $i=1,2$, their
_direct sum_ $T_{1}\oplus T_{2}$ is the tensor that takes the value
$T_{1}(x_{1},\dots,x_{d})$ if $x_{i}\in X_{i}^{1}$ for each $i$,
$T_{2}(x_{1},\dots,x_{d})$ if $x_{i}\in X_{i}^{2}$ for each $i$, and 0
otherwise.

Let us write $\sigma(T)$ for the slice rank of $T$.

######  Theorem 1.2.

For any two tensors, we have $\sigma(T_{1}\oplus
T_{2})=\sigma(T_{1})+\sigma(T_{2})$.

Note that this immediately implies that $\sigma(T_{1}\oplus\dots\oplus
T_{m})=\sigma(T_{1})+\dots+\sigma(T_{m})$ (where the definition of
$T_{1}\oplus\dots\oplus T_{m}$ is obvious), and hence Tao’s lemma, which is
the special case where each $T_{i}$ is a $1\times\dots\times 1$ tensor.

To prove the theorem, it is tempting to try to modify Tao’s argument, but the
following example, with $d=3$, seems to indicate that that cannot be done
straightforwardly.

######  Example.

Let $\epsilon$ be the $3\times 3\times 3$ Levi-Civita symbol. That is, it is
defined on $\\{1,2,3\\}^{3}$, and $\epsilon(x,y,z)=0$ if any two of $x,y,z$
are equal, and otherwise $\epsilon(x,y,z)=1$ if $(x,y,z)$ is an even
permutation of $(1,2,3)$ and $-1$ if it is an odd permutation. (It would more
normally be written $\epsilon_{ijk}$, but we write it $\epsilon(x,y,z)$ for
consistency with our earlier notation.) This tensor is supported on an
antichain, meaning that if $x\leq x^{\prime},y\leq y^{\prime},z\leq
z^{\prime}$, and both $(x,y,z)$ and $(x^{\prime},y^{\prime},z^{\prime})$
belong to the support, then $(x,y,z)=(x^{\prime},y^{\prime},z^{\prime})$. If
we define a _slice_ to be a subset of $\\{1,2,3\\}^{3}$ defined by holding one
of the coordinates constant, then the number of slices needed to cover the
support of $\epsilon$ is 3, since each slice contains two points of the
support. A result of Sawin and Tao [7] states that if a tensor is supported on
an antichain, then its slice rank is equal to the number of slices needed to
cover the support, which implies that $\epsilon$ has slice rank 3.

If, however, $h$ is any function from $\\{1,2,3\\}$ to $\mathbb{F}$, then the
$3\times 3$ matrix

$M(y,z)=\sum_{x}h(x)\epsilon(x,y,z)$

is antisymmetric, and therefore has rank at most 2.

To see why this is a problem, let $T=\epsilon\oplus\dots\oplus\epsilon$, where
we take $m$ copies, and suppose we have a decomposition

$T(x,y,z)=\sum_{i=1}^{r}a_{i}(x)b_{i}(y,z)+\sum_{j=1}^{s}c_{j}(y)d_{j}(x,z)+\sum_{k=1}^{t}e_{k}(z)f_{k}(x,y).$

We can find $h$ with at most $r$ zeros such that $\sum_{x}h(x)a_{i}(x)=0$ for
$i=1,2,\dots,r$, and the matrix

$M(y,z)=\sum_{x}h(x)T(x,y,z)$

has rank at most $s+t$.

However, in the other direction all we know is that the rank of $M$ is twice
the number of copies of $\epsilon$ that are not projected to zero – that is,
twice the number of $q$ such that at least one of $h(3q-2),h(3q-1)$ and
$h(3q)$ is non-zero. The number of such $q$ is at least $m-\lfloor
r/3\rfloor$, but can in principle be that low. For example, if for each $i\leq
r$, $a_{i}$ is the $i$th standard basis vector, then $h(i)$ is forced to be
zero for $i=1,\dots,r$, so for $q\leq r/3$ we have that $h(3q-2),h(3q-1)$ and
$h(3q)$ are all zero. So the best lower bound we can obtain in general is that
$2\lfloor r/3\rfloor+s+t\geq 2m$. By symmetry we obtain similar estimates with
the role of $r$ played by $s$ and $t$. But if $r,s$ and $t$ are all equal and
are multiples of 3, then we find that $8(r+s+t)/9\geq 2m$, from which we can
conclude only that $r+s+t\geq 9m/4$.

Note that the result of Sawin and Tao that shows that $\sigma(\epsilon)=3$
also shows that $\sigma(\epsilon\oplus\dots\oplus\epsilon)=3m$ (where there
are still $m$ copies of $\epsilon$), but there are tensors for which their
method does not give optimal estimates, so this argument will only work for
special cases of the problem.

######  Remark.

The example just presented relied on a “non-trivial” space of low-rank
matrices, namely the $3\times 3$ antisymmetric matrices. We regard a space $Z$
of matrices of rank at most $r$ as trivial if there are spaces $U$ and $V$ of
dimensions $s$ and $t$ with $s+t\leq r$ such that $Z$ is the sum of the space
of matrices with rows in $U$ and the space of matrices with columns in $V$. It
is not a straightforward problem to understand spaces of low-rank matrices in
general. See for example a paper of Eisenbud and Harris [3], which was what
led us to think of the example above, and which can probably be used to
construct other examples of a similar type.

An earlier version of this note contained a more complicated argument. I would
like to thank Thomas Karam for pointing out that certain parts of that
argument were imprecise to the point of not being obviously correct. Although
it turned out that the argument could be rescued in the case $d=3$ (and
probably also for general $d$ but that is trickier), during subsequent
conversations with Thomas Karam a simpler proof emerged, after which it became
clear that the result could in fact be proved using a simple modification of
the argument of Sawin and Tao just mentioned, a possibility that I had
previously considered but, as a result of an incorrect heuristic argument,
discounted. While this makes the result not interesting enough to publish
formally, it still seems worth keeping it as an arXiv preprint, since at some
point it may save somebody some time if it can be readily found online. As
this document is not intended for publication, we include the modified old
argument for the case $d=3$, just in case elements of the proof are of use to
anyone.

##  2 Proof of Theorem 1.2

For the convenience of the reader, we begin by recalling one or two facts from
a blog post of Sawin and Tao [7]. The first is that we can think of tensors in
two different ways – either in “matrix form” as functions
$T:X_{1}\times\dots\times X_{d}\to\mathbb{F}$ or as elements of a tensor
product $V_{1}\otimes\dots\otimes V_{d}$. Given a function
$T:X_{1}\otimes\dots\otimes X_{d}\to\mathbb{F}$, the corresponding element of
the tensor product $\mathbb{F}^{X_{1}}\otimes\dots\otimes\mathbb{F}^{X_{d}}$
is the sum

$\sum_{x_{1},\dots,x_{d}}T(x_{1},\dots,x_{d})e_{x_{1}}\otimes\dots\otimes
e_{x_{d}},$

where, given $x_{i}\in X_{i}$, the vector $e_{x_{i}}$ is the standard basis
vector in $\mathbb{F}^{X_{i}}$ that takes the value 1 at $x_{i}$ and 0
everywhere else. In the other direction, given an element $\tau$ of a tensor
product $V_{1}\otimes\dots\otimes V_{d}$ of finite-dimensional vector spaces,
take a basis $\\{e_{i1},\dots,e_{ir_{i}}\\}$ of each $V_{i}$, write $\tau$ in
the unique way possible as

$\tau=\sum_{j_{1},\dots,j_{d}}\lambda(j_{1},\dots,j_{d})e_{1j_{1}}\otimes\dots\otimes
e_{dj_{d}},$

let $X_{i}=\\{1,2,\dots,r_{i}\\}$, and set $T=\lambda$.

In the tensor-product formulation, the slice rank of a tensor $T\in
V_{1}\otimes\dots\otimes V_{d}$ is the smallest $r$ such that it is possible
to write $T$ in the form

$\sum_{i=1}^{d}\sum_{j=1}^{r_{i}}u_{ij}\otimes v_{ij},$

with $r_{1}+\dots+r_{d}=r$, where for each $i$, $u_{ij}\in V_{i}$ and
$v_{ij}\in V_{1}\otimes\dots\otimes V_{i-1}\otimes V_{i+1}\otimes\dots\otimes
V_{d}$. (This is a slight abuse of notation because what we are really doing
is “inserting” $u_{i,j}$ into $v_{i,j}$. More precisely, if $v$ is a pure
tensor $w_{1}\otimes\dots\otimes w_{i-1}\otimes w_{i+1}\otimes\dots\otimes
w_{d}$ and $u\in V_{i}$, then by $u\otimes v$ we mean the tensor
$w_{1}\otimes\dots\otimes w_{i-1}\otimes u\otimes w_{i+1}\otimes\dots\otimes
w_{d}$, and then this map can be extended linearly.)

It is simple to check that this tensor-product definition of slice rank agrees
with the definition given earlier. We shall therefore pass freely between the
two, using whichever formulation is more convenient at any one moment.

######  Lemma 2.1.

Let $V_{1},\dots,V_{d}$ be finite-dimensional vector spaces over a field
$\mathbb{F}$ and let $T\in V_{1}\otimes\dots\otimes V_{d}$. Then $T$ has slice
rank at most $r$ if and only if there exist subspaces $U_{i}\subset V_{i}^{*}$
with $\sum_{i}\mathop{\mathrm{codim}}(U_{i})\leq r$ such that $\langle
T,u\rangle=0$ for every $u\in U_{1}\otimes\dots\otimes U_{d}$.

###### Proof.

Suppose first that $T$ has slice rank at most $r$. Then we can write $T$ as a
sum $\sum_{i=1}^{d}\sum_{j=1}^{r_{i}}v_{ij}\otimes w_{ij}$, where for each $i$
and $j$, $v_{ij}\in V_{i}$ and $w_{ij}\in V_{1}\otimes\dots\otimes
V_{i-1}\otimes V_{i+1}\otimes\dots\otimes V_{d}$, and $\sum_{i=1}^{d}r_{i}\leq
r$.

For each $i$ let $U_{i}$ be the set of all $u\in V_{i}^{*}$ such that $\langle
v_{ij},u\rangle=0$ for $j=1,\dots,r_{i}$. Then $U_{i}$ is a subspace of
codimension at most $r_{i}$. Moreover, if $u_{i}\in U_{i}$ for $i=1,\dots,d$,
then $\langle\sum_{i=1}^{d}\sum_{j=1}^{r_{i}}v_{ij}\otimes
w_{ij},u_{1}\otimes\dots\otimes u_{d}\rangle=0$, since for each $i,j$ we have
that $\langle v_{ij},u_{i}\rangle=0$. Extending linearly we find that $\langle
T,u\rangle=0$ for every $u\in U_{1}\otimes\dots\otimes U_{d}$, and we also
have that $\sum_{i}\mathop{\mathrm{codim}}(U_{i})\leq r$.

In the reverse direction, suppose that such subspaces $U_{i}$ exist. For each
$i$ choose a basis of $U_{i}$ and extend it to a basis of $V_{i}^{*}$. By
considering the expansion of $T$ with respect to the dual bases of these
bases, we see that $T$ must be contained in the subspace
$\sum_{i=1}^{d}V_{1}\otimes\dots\otimes V_{i-1}\otimes U_{i}^{\perp}\otimes
V_{i+1}\otimes\dots\otimes V_{d}$ of $V_{1}\otimes\dots\otimes V_{d}$. Since
$U_{i}^{\perp}$ has a basis of size $r_{i}$, this yields a decomposition of
$T$ of the required form. ∎

###### Proof of Theorem 1.2.

Let $V_{1},\dots,V_{d}$ be finite-dimensional vector spaces with
$V_{i}=V_{i}^{1}\oplus V_{i}^{2}$, and let $T=T_{1}+T_{2}$, where $T^{1}\in
V_{1}^{1}\otimes\dots\otimes V_{d}^{1}$ and $T^{2}\in
V_{1}^{2}\otimes\dots\otimes V_{d}^{2}$. We would like to show that
$\sigma(T_{1})+\sigma(T_{2})\leq\sigma(T)$, the reverse inequality being
trivial.

Let $r=\sigma(T)$ and choose subspaces $U_{i}\subset V_{i}^{*}$ with
$\mathop{\mathrm{codim}}(U_{i})=r_{i}$ and $\sum_{i}r_{i}=r$ such that
$\langle T,u\rangle=0$ for every $u\in U_{1}\otimes\dots\otimes U_{d}$.

For each $i$, choose a basis $v_{i1},\dots,v_{in_{i}}$ of $V_{i}$ that starts
with a basis of $V_{i}^{1}$ and ends with a basis of $V_{i}^{2}$. Let
$v_{i1}^{*},\dots,v_{in_{i}}^{*}$ be the dual basis, and let
$u_{i1},\dots,u_{im_{i}}$ be a basis of $U_{i}$, where $m_{i}=n_{i}-r_{i}$.
Each $u_{ij}$ can be expanded in terms of the dual basis. Let us write
$u_{ij}(h)$ for the $h$th coefficient of $u_{ij}$ with respect to this basis:
that is,

$u_{ij}=\sum_{h=1}^{n_{i}}u_{ij}(h)v_{ih}.$

By applying Gaussian elimination, we may assume for any given $i$ that the
first $h$ for which $u_{ij}(h)$ is non-zero is a strictly increasing function
of $j$. Alternatively, we may assume for any given $i$ that the last $h$ for
which $u_{ij}(h)$ is non-zero is a strictly decreasing function of $i$. (That
is, for each $i$ we may assume one or the other of these two statements: we do
not claim that both can be assumed at once.)

Suppose that for a particular $i$ we have chosen the first option: that is,
the first $h$ for which $u_{ij}(h)\neq 0$ is strictly increasing with $j$. If
$\dim(V_{i}^{1})=s_{i}$, then for every $j$ such that the first such $h$ is
greater than $s_{i}$, we have that $u_{ij}$ vanishes on $V_{i}^{1}$. We now
define a sequence $w_{i1},\dots,w_{im_{i}}$ as follows. For every $j$ such
that the first $h$ is less than $s_{i}$, we let $w_{ij}$ be the projection of
$u_{ij}$ on to the first $s_{i}$ coordinates, and note that $w_{ij}$ and
$u_{ij}$ agree on $V_{i}^{1}$. Let the number of such $j$ be $k_{i}$. For
every $j>k_{i}$, we let $w_{ij}=u_{ij}$, and as just mentioned we have that
$w_{ij}$ vanishes on $V_{i}^{1}$.

Similarly, if we have chosen the second option, then we can define a sequence
$w_{i1},\dots,w_{im_{i}}$ and $k_{i}$ such that for $j\leq k_{i}$ we have that
$w_{ij}$ vanishes on $V_{i}^{2}$ and for $j>k_{i}$ we have that $w_{ij}$
agrees with $u_{ij}$ on $V_{i}^{2}$.

In both cases we start with the vectors $u_{i1},\dots,u_{im_{i}}$ and obtain a
sequence $w_{i1},\dots,w_{im_{i}}$ and some $k_{i}$ such that
$w_{i1},\dots,w_{ik_{i}}\in(V_{i}^{1})^{*}$ and
$w_{i,k_{i}+1},\dots,w_{im_{i}}\in(V_{i}^{2})^{*}$. For each $i$ let
$U_{i}^{1}$ be the span of $w_{i1},\dots,w_{ik_{i}}$ and let $U_{i}^{2}$ be
the span of $w_{i,k_{i}+1},\dots,w_{im_{i}}$. Since
$\dim(U_{i}^{1})+\dim(U_{i}^{2})=m_{i}$, we have that
$\mathop{\mathrm{codim}}(U_{i}^{1})+\mathop{\mathrm{codim}}(U_{i}^{2})=n_{i}-m_{i}=r_{i}$.
(Here by the codimension of $U_{i}^{1}$ we mean its codimension as a subspace
of $(V_{i}^{1})^{*}$, and similarly for $U_{i}^{2}$.)

Assume now that there exists $i_{0}$ such that the second option is chosen. We
claim that if $u\in U_{1}^{1}\otimes\dots\otimes U_{d}^{1}$, then $\langle
T^{1},u\rangle=0$. It is enough to prove this when $u=u_{1}\otimes\dots\otimes
u_{d}$ with $u_{i}\in U_{i}^{1}$. Furthermore, it is enough to prove it when
each $u_{i}$ is equal to $w_{ij}$ for some $j\leq k_{i}$.

If $i$ is such that the first option is chosen, and $j\leq k_{i}$, then
$w_{ij}$ agrees with $u_{ij}$ on $V_{i}^{1}$. If $i$ is such that the second
option is chosen, and $j\leq k_{i}$, then $w_{ij}=u_{ij}$ and therefore also
agrees with $u_{ij}$ on $V_{i}^{1}$. Since $T^{1}\in
V_{1}^{1}\otimes\dots\otimes V_{d}^{1}$, it follows that $\langle
T^{1},u\rangle$ does not change if we replace each $w_{ij}$ by $u_{ij}$. But
if each $u_{i}$ is one of the vectors $u_{ij}$, then $\langle T,u\rangle=0$,
by hypothesis. Also, since the second option is chosen for $i_{0}$,
$u_{i_{0}}$ vanishes on $V_{i_{0}}^{2}$. It follows that $\langle
T^{2},u\rangle=0$, and therefore that $\langle T^{1},u\rangle=0$.

Similarly, if $u\in U_{1}^{2}\otimes\dots\otimes U_{d}^{2}$ and we choose the
first option for at least one $i$, then $\langle T^{2},u\rangle=0$.

Since $d\geq 2$, we can choose the first option for at least one $i$ and the
second option for at least one $i$, so the result is proved. ∎

An examination of the above argument shows that it can be used to prove
stronger statements as well. Suppose, for instance, that $T$ is of the form
$T^{1}+T^{2}$ where $T^{1}$, as before, belongs to
$V_{1}^{1}\otimes\dots\otimes V_{d}^{1}$, but all we assume about $T^{2}$ is
that it belongs to $V_{1}\otimes\dots\otimes V_{d-1}\otimes V_{d}^{2}$. We now
run the proof, choosing the first option for $i=1,2,\dots,d-1$ and the second
option for $i=d$.

Suppose that $w=w_{1}\otimes\dots\otimes w_{d}$, where each $w_{i}$ is equal
to $w_{ij}$ for some $j\leq k_{i}$. For $i=1,2,3,\dots,d-1$ let us replace
$w_{i}$ by some $u_{i}\in U_{i}^{1}$ that agrees with $w_{i}$ on $V_{i}^{1}$.
Letting $u=u_{1}\otimes\dots\otimes u_{d-1}\otimes w_{d}$, we then have that
$\langle T^{1},w\rangle=\langle T^{1},u\rangle$. Because we chose the second
option for $i=d$, $w_{d}$ vanishes on $V_{d}^{2}$, and therefore $\langle
T^{2},u\rangle=0$. It follows that $\langle T^{1},u\rangle=\langle
T,u\rangle=0$, where the last equality holds by hypothesis.

Now suppose that $w=w_{1}\otimes\dots\otimes w_{d}$, where this time each
$w_{i}$ is equal to $w_{ij}$ for some $j>k_{i}$. Then there exists $u_{d}\in
U_{d}^{2}$ that agrees with $w_{d}$ on $V_{d}^{2}$, while for
$i=1,2,\dots,d-1$ we have that $w_{i}$ vanishes on $V_{i}^{1}$. Let
$u=w_{1}\otimes\dots\otimes w_{d-1}\otimes u_{d}\in
U_{1}^{2}\otimes\dots\otimes U_{d}^{2}$ and note that $\langle
T^{1},u\rangle=0$.

Given $\alpha\in\\{1,2\\}^{d}$, let $T^{\alpha}$ stand for the projection of
$T$ to $V_{1}^{\alpha_{1}}\otimes\dots\otimes V_{d}^{\alpha_{d}}$. (To be more
explicit, given $v_{i}\in V_{i}$ we can write it uniquely as
$v_{i}^{1}+v_{i}^{2}$ with $v_{i}^{1}\in V_{i}^{1}$ and $v_{i}^{2}\in
V_{i}^{2}$. This allows us to decompose $v_{1}\otimes\dots\otimes v_{d}\in
V_{1}\otimes\dots\otimes V_{d}$ into $2^{d}$ parts
$v_{1}^{\alpha_{1}}\otimes\dots\otimes v_{d}^{\alpha_{d}}$, one for each
$\alpha$.) Then $T=\sum_{\alpha}T^{\alpha}$.

If any of $\alpha_{1},\dots,\alpha_{d-1}$ is equal to $1$, then because
$w_{i}$ vanishes on $V_{i}^{1}$ for $i\leq d-1$, we have that $\langle
T^{\alpha},w\rangle=0$. Also, when $\alpha=(2,2,\dots,2,1)$, we have that
$T^{\alpha}=0$. It follows that

$\langle T^{22\dots 2},w\rangle=\langle T^{2},w\rangle=\langle
T^{2},u\rangle=\langle T,u\rangle=0,$

where again the last equality holds by hypothesis.

This proves the following statement.

######  Theorem 2.2.

Let $V_{1},\dots,V_{d}$ be finite-dimensional vector spaces with
$V_{i}=V_{i}^{1}\oplus V_{i}^{2}$ for each $i$. Let $T\in
V_{1}\otimes\dots\otimes V_{d}$ and suppose that the component $T^{\alpha}$
(see just above for the definition) is zero unless either $\alpha_{d}=2$ or
$\alpha_{1}=\dots=\alpha_{d}=1$. Then

$\sigma(T)\geq\sigma(T^{11\dots 1})+\sigma(T^{22\dots 2}).$

Note that the conditions of this theorem are satisfied in particular if
$T^{\alpha}$ is non-zero only for increasing sequences $\alpha$. This gives us
a simple corollary about “block upper triangular” tensors. Here we let $T\in
V_{1}\otimes\dots\otimes V_{d}$ as before, but this time
$V_{i}=V_{i}^{1}\oplus\dots\oplus V_{i}^{k}$ for some $k$. We call a tensor
block upper triangular (with respect to the given decompositions) if the
component $T^{\alpha}$ (defined in the obvious way for each
$\alpha\in[k]^{d}$) is non-zero only for increasing sequences $\alpha$.

######  Corollary 2.3.

Let $V_{1},\dots,V_{d}$ be as above and let $T\in V_{1}\otimes\dots\otimes
V_{d}$ be upper triangular. Then

$\sigma(T)\geq\sigma(T^{11\dots 1})+\dots+\sigma(T^{kk\dots k}).$

###### Proof.

For each $i$ let $W_{i}^{1}=V_{i}^{1}\oplus\dots\oplus V_{i}^{k-1}$ and let
$W_{i}^{2}=V_{i}^{k}$. Then $V_{i}=W_{i}^{1}\oplus W_{i}^{2}$. For
$\alpha\in\\{1,2\\}^{d}$ let $S^{\alpha}$ be the component of $T$ in
$W_{1}^{\alpha_{1}}\otimes\dots\otimes W_{d}^{\alpha_{d}}$. Then $T$ is block
upper triangular with respect to the decompositions $V_{i}=W_{i}^{1}\oplus
W_{i}^{2}$, from which it follows, using the theorem just proved, that
$\sigma(T)\geq\sigma(S^{11\dots 1})+\sigma(S^{22\dots 2})$.

But $S^{22\dots 2}=T^{22\dots 2}$, and $S^{11\dots 1}\in
W_{1}^{1}\otimes\dots\otimes W_{d}^{1}$ is block upper triangular with respect
to the decompositions $W_{i}^{1}=V_{i}^{1}\oplus\dots\oplus V_{i}^{k-1}$. By
induction on $k$ we have that

$\sigma(S^{11\dots 1})\geq\sigma(T^{11\dots
1})+\dots+\sigma(T^{k-1,k-1,\dots,k-1}),$

and the proof is complete. ∎

##  3 An alternative proof of Theorem 1.2 for 3-tensors

There seems no harm in including the argument mentioned earlier that works
when $d=3$, even though it is a little more complicated, as the lemmas along
the way may be of some interest. However, the reader just interested in
obtaining some proof of Theorem 1.2 can safely skip this section.

For this proof we shall use the more “matrix-like” conception of tensors.

######  Lemma 3.1.

Let $V$ and $W$ be two vector spaces with $V\cap W=\\{0\\}$, let
$v_{1},\dots,v_{n}\in V$ and $w_{1},\dots,w_{n}\in W$ be two sequences of
vectors, and let $U\subset V+W$ be the subspace generated by the vectors
$v_{i}+w_{i}$. Then there exists a sequence
$v_{1}^{\prime\prime}+w_{1}^{\prime\prime},\dots,v_{n}^{\prime\prime}+w_{n}^{\prime\prime}$
that generates $U$ with each $v_{i}^{\prime\prime}$ in $V$ and each
$w_{i}^{\prime\prime}$ in $W$, such that the non-zero $v_{i}^{\prime\prime}$
are linearly independent and the non-zero $w_{i}^{\prime\prime}$ are linearly
independent.

###### Proof.

Without loss of generality $v_{1},\dots,v_{m}$ is a maximal linearly
independent subset of $v_{1},\dots,v_{n}$. Then for each $j>m$ we can write

$v_{j}=\sum_{i=1}^{m}\lambda_{ji}v_{i}$

For $j>m$ let $w_{j}^{\prime}=w_{j}-\sum_{i=1}^{r}\lambda_{ji}w_{i}$ and let
$v_{j}^{\prime}=0$, and observe that the $v_{i}^{\prime}+w_{i}^{\prime}$
generate the same subspace as the $v_{i}+w_{i}$. (We let
$v_{i}^{\prime}=v_{i}$ and $w_{i}^{\prime}=w_{i}$ when $i\leq m$.) We also
have that the non-zero $v_{i}$ are linearly independent.

Now let us choose $v_{1}^{\prime\prime},\dots,v_{n}^{\prime\prime}$ and
$w_{1}^{\prime\prime},w_{2}^{\prime\prime},\dots,w_{n}^{\prime\prime}$ as
follows, with the aim of ensuring that for every $s$ we have that

$\langle
w_{s}^{\prime\prime},w_{s+1}^{\prime\prime},\dots,w_{n}^{\prime\prime}\rangle=\langle
w_{s}^{\prime},w_{s+1}^{\prime},\dots,w_{n}^{\prime}\rangle.$

We start by setting $w_{n}^{\prime\prime}=w_{n}^{\prime}$. Once we have chosen
$w_{s+1}^{\prime\prime},\dots,w_{n}^{\prime\prime}$ with the desired property,
if

$w_{s}^{\prime}=\sum_{s+1}^{n}\mu_{si}w_{i}^{\prime\prime}$

then we set $w_{s}^{\prime\prime}=0$ and
$v_{s}^{\prime\prime}=v_{s}^{\prime}-\sum_{s+1}^{n}\mu_{si}v_{i}^{\prime\prime}$.
Otherwise – that is, if $w_{s}^{\prime}$ is not a linear combination of
$w_{s+1}^{\prime\prime},\dots,w_{n}^{\prime\prime}$ – we set
$w_{s}^{\prime\prime}=w_{s}^{\prime}$ and
$v_{s}^{\prime\prime}=v_{s}^{\prime}$.

Since $v_{m+1}^{\prime}=\dots=v_{n}^{\prime}=0$, we find that
$v_{m+1}^{\prime\prime}=\dots=v_{n}^{\prime\prime}=0$ as well. Also, the non-
zero $w_{i}^{\prime\prime}$ are linearly independent, as are the vectors
$v_{1}^{\prime\prime},\dots,v_{m}^{\prime\prime}$, and the vectors
$v_{i}^{\prime\prime}+w_{i}^{\prime\prime}$ generate the same subspace as the
vectors $v_{i}+w_{i}$. ∎

In the next lemma, we write $a\otimes b$ for the function that takes the value
$a(x)b(y,z)$ at $(x,y,z)$. Note that the lemma is really about matrices – the
fact that the $b_{i}$ are functions of two variables is irrelevant, but it is
the case we shall use when we apply the lemma.

######  Lemma 3.2.

If $a_{1},\dots,a_{r}$ and $a_{1}^{\prime},\dots,a_{r}^{\prime}$ generate the
same subspace, then any tensor $\sum_{i}a_{i}(x)b_{i}(y,z)$ is equal to some
tensor $\sum_{j}a_{j}^{\prime}(x)b_{j}^{\prime}(y,z)$.

###### Proof.

Let $a_{i}=\sum_{j=1}^{r}\theta_{ij}a_{j}^{\prime}$ for each $i$, which we can
do because the $a_{j}^{\prime}$ contain the $a_{i}$ in their linear span. Then

$\sum_{i}a_{i}\otimes b_{i}=\sum_{i,j}\theta_{ij}a_{j}^{\prime}\otimes
b_{i}=\sum_{j}a_{j}^{\prime}\otimes(\sum_{i}\theta_{ij}b_{i}),$

so we can take $b_{j}^{\prime}=\sum_{i}\theta_{ij}b_{i}$ for each $j$. ∎

######  Remark.

The lemma just proved highlights the main difference, for this question,
between slice rank and tensor rank, and indeed various other kinds of rank.
Each $b_{j}^{\prime}$ is a linear combination of the $b_{i}$, and is therefore
a function of the same type. But if we were considering tensor rank, then each
$b_{i}$ would be a rank-1 matrix, and we would not be able to conclude that
each $b_{j}^{\prime}$ was a rank-1 matrix. Thus, there is a flexibility
associated with slice-rank decompositions that we do not have with tensor-rank
decompositions.

We now take three finite sets $X$, $Y$, and $Z$, each partitioned into two
subsets, so $X=X^{1}\cup X^{2}$, $Y=Y^{1}\cup Y^{2}$ and $Z=Z^{1}\cup Z^{2}$.
(We shall use superscripts to denote elements of the set $\\{1,2\\}$ and
subscripts to index the functions we use in decompositions.) Given a function
$a:X\to\mathbb{F}$, we define $a^{\alpha}$ to be the projection of $a$ to
$X^{\alpha}$: that is, $a^{\alpha}(x)=a(x)$ if $x\in X^{\alpha}$ and
$a^{\alpha}(x)=0$ otherwise. We do the same for functions defined on $Y$ and
$Z$. Similarly, if $b:Y\times Z\to\mathbb{F}$, then $b^{\beta\gamma}$ is the
projection of $b$ to $Y^{\beta}\times Z^{\gamma}$, and so on. In particular,
if $T:X\times Y\times Z\to\mathbb{F}$ is a tensor, then
$T^{\alpha\beta\gamma}$ is the projection of $T$ to $X^{\alpha}\times
Y^{\beta}\times Z^{\gamma}$.

We shall also sometimes use this notation to refer to restrictions rather than
projections. For example, if we say that $T=T^{111}\oplus T^{222}$, we mean
that $T^{\alpha\beta\gamma}=0$ except if $\alpha=\beta=\gamma$. In other
words, it is sometimes convenient to regard $T^{\alpha\beta\gamma}$ as defined
on $X^{\alpha}\times Y^{\beta}\times Z^{\gamma}$, and it is sometimes
convenient to regard it as defined on all of $X\times Y\times Z$ but supported
on $X^{\alpha}\times Y^{\beta}\times Z^{\gamma}$, and similarly for functions
of fewer variables. We hope that no confusion will arise.

######  Corollary 3.3.

Let $X=X^{1}\cup X^{2}$, $Y=Y^{1}\cup Y^{2}$ and $Z=Z^{1}\cup Z^{2}$ be three
finite sets each partitioned into two subsets, and let $T:X\times Y\times
Z\to\mathbb{F}$ be a tensor. Suppose that $T$ has a decomposition

$\displaystyle
T(x,y,z)=\sum_{i=1}^{r}a_{i}(x)b_{i}(y,z)+\sum_{j=1}^{s}c_{j}(y)d_{j}(x,z)+\sum_{k=1}^{t}e_{k}(z)f_{k}(x,y).$
(1)

Then $T$ has such a decomposition with the additional property that for all
$\alpha,\beta,\gamma\in\\{1,2\\}$ the non-zero $a_{i}^{\alpha}$ are linearly
independent, the non-zero $c_{j}^{\beta}$ are linearly independent, and the
non-zero $e_{k}^{\gamma}$ are linearly independent.

###### Proof.

Applying Lemma 3.1 with $V=\mathbb{F}^{X^{1}}$, $W=\mathbb{F}^{X^{2}}$,
$v_{i}=a_{i}^{1}$, and $w_{i}=a_{i}^{2}$ for each $i$, we obtain a sequence
$a_{1}^{\prime},\dots,a_{r}^{\prime}$ with the same linear span as
$a_{1},\dots,a_{r}$ such that the non-zero vectors $(a_{i}^{\prime})^{1}$ are
linearly independent and the non-zero vectors $(a_{i}^{\prime})^{2}$ are
linearly independent. By Lemma 3.2 we can find functions
$b_{1}^{\prime},\dots,b_{r}^{\prime}:Y\times Z\to\mathbb{F}$ such that
$\sum_{i}a_{i}(x)b_{i}(y,z)=\sum_{i}a_{i}^{\prime}(x)b_{i}^{\prime}(y,z)$ for
every $x,y,z$. By symmetry we can rewrite the other two terms in a similar
way, and the result is proved. ∎

We need one further linear algebra lemma.

######  Lemma 3.4.

Let $U,V,W$ be vector spaces and let $W^{\prime}$ be a subspace of $W$. Let
$u_{1},\dots,u_{r}\in U$ be linearly independent and let $v_{1},\dots,v_{s}\in
V$ be linearly independent. Suppose that we have a linear combination
$\sum_{i=1}^{r}\sum_{j=1}^{s}u_{i}\otimes v_{j}\otimes w_{ij}$ that belongs to
the subspace $U\otimes V\otimes W^{\prime}$. Then all the vectors $w_{ij}$
belong to the subspace $W^{\prime}$.

###### Proof.

Suppose not, and let $\phi:W\to\mathbb{F}$ be a linear functional that
vanishes on $W^{\prime}$ but not on every vector $w_{ij}$. Define
$\psi(u\otimes v\otimes w)$ to be $\phi(w)u\otimes v$ and extend this to a
linear map $\psi:U\otimes V\otimes W\to U\otimes V$. Then $\psi$ vanishes on
$U\otimes V\otimes W^{\prime}$. However, the image of
$\sum_{i=1}^{r}\sum_{j=1}^{s}u_{i}\otimes v_{j}\otimes w_{ij}$ is a non-zero
linear combination of the $u_{i}\otimes v_{j}$, which are linearly
independent, so it is non-zero. This is a contradiction. ∎

Now let us adopt our main hypothesis, namely that we have a tensor $T$ as in
Corollary 3.3 and that $T=T^{111}\oplus T^{222}$. Suppose also that $T$ has a
decomposition as in (1) above, and that the conclusion of Corollary 3.3 holds
for this decomposition. Our hypothesis is equivalent to the statement that
$T^{\alpha\beta\gamma}=0$ except if $\alpha=\beta=\gamma$.

For $\alpha,\beta,\gamma\in\\{1,2\\}$ let $A^{\alpha}=\\{i:a_{i}^{\alpha}\neq
0\\}$, let $C^{\beta}=\\{j:c_{j}^{\beta}\neq 0\\}$, and let
$E^{\gamma}=\\{k:e_{k}^{\gamma}\neq 0\\}$. Then for each
$\alpha,\beta,\gamma,x,y,z$, we have that

$T^{\alpha\beta\gamma}(x,y,z)=\sum_{i\in
A^{\alpha}}a_{i}^{\alpha}(x)b_{i}^{\beta\gamma}(y,z)+\sum_{j\in
C^{\beta}}c_{j}^{\beta}(y)d_{j}^{\alpha\gamma}(x,z)+\sum_{k\in
E^{\gamma}}e_{k}^{\gamma}(z)f_{k}^{\alpha\beta}(x,y).$

In the next lemma, we shall use bracketed superscripts to denote dependencies
and non-bracketed superscripts to denote the parts that a function applies to.
So for example, in the statement, the function $p_{ij}^{(\alpha)\gamma}$ is
defined on $Z^{\gamma}$ and depends on $\alpha$ (because it will be made out
of the functions $d_{j}^{\alpha\gamma}$, which are defined on
$X^{\alpha}\times Z^{\gamma}$).

######  Lemma 3.5.

Let $\alpha,\beta,\gamma$ be not all equal and let $i\in A^{\alpha}$. Then
there exist functions $p_{ij}^{(\alpha)\gamma}:Z^{\gamma}\to\mathbb{F}$ and
$q_{ik}^{(\alpha)\beta}:Y^{\beta}\to\mathbb{F}$ such that

$b_{i}^{\beta\gamma}=\sum_{j\in C^{\beta}}c_{j}^{\beta}\otimes
p_{ij}^{(\alpha)\gamma}+\sum_{k\in E^{\gamma}}q_{ik}^{(\alpha)\beta}\otimes
e_{k}^{\gamma},$

with similar decompositions for $d_{j}^{\alpha\gamma}$ and
$f_{k}^{\alpha\beta}$.

###### Proof.

Since the $a_{i}^{\alpha}$ with $i\in A^{\alpha}$ are linearly independent,
the matrix $(a_{i}^{\alpha}(x))$, where $i$ ranges over $A^{\alpha}$ and $x$
over $X$, has rank $|A^{\alpha}|$. It follows that we can find for each $i$ a
function $h_{i}^{(\alpha)}:X\to\mathbb{F}$ such that
$\sum_{x}h_{i}^{(\alpha)}(x)a_{l}^{\alpha}(x)=\delta_{il}$ for every $l\in
A^{\alpha}$. Then since $T^{\alpha\beta\gamma}=0$, we have that

$0=\sum_{x}h_{i}^{(\alpha)}(x)T^{\alpha\beta\gamma}(x,y,z)=b_{i}^{\beta\gamma}(y,z)-\sum_{j\in
C^{\beta}}c_{j}^{\beta}(y)p_{ij}^{(\alpha)\gamma}(z)-\sum_{k\in
E^{\gamma}}q_{ik}^{(\alpha)\beta}(y)e_{k}^{\gamma}(z),$

where

$p_{ij}^{(\alpha)\gamma}(z)=-\sum_{x}h_{i}^{(\alpha)}(x)d_{j}^{\alpha\gamma}(x,z)$

and

$q_{ik}^{(\alpha)\beta}(y)=-\sum_{x}h_{i}^{(\alpha)}(x)f_{k}^{\alpha\beta}(x,y).$

The corresponding results for the functions $d_{j}^{\alpha\gamma}$ and
$f_{k}^{\alpha\beta}$ are proved in the same way. ∎

Using Lemma 3.5 we can rewrite the decomposition of $T^{\alpha\beta\gamma}$
above in the form

$\displaystyle\sum_{i\in A^{\alpha}}$ $\displaystyle\sum_{j\in
C^{\beta}}a_{i}^{\alpha}\otimes c_{j}^{\beta}\otimes
p_{ij}^{(\alpha)\gamma}+\sum_{i\in A^{\alpha}}\sum_{k\in
E^{\gamma}}a_{i}^{\alpha}\otimes q_{ik}^{(\alpha)\beta}\otimes e_{k}^{\gamma}$
$\displaystyle+\sum_{i\in A^{\alpha}}\sum_{j\in
C^{\beta}}a_{i}^{\alpha}\otimes c_{j}^{\beta}\otimes
g_{ij}^{(\beta)\gamma}+\sum_{j\in C^{\beta}}\sum_{k\in
E^{\gamma}}h_{jk}^{\alpha(\beta)}\otimes c_{j}^{\beta}\otimes e_{k}^{\gamma}$
$\displaystyle+\sum_{i\in A^{\alpha}}\sum_{k\in
E^{\gamma}}a_{i}^{\alpha}\otimes u_{ik}^{\beta(\gamma)}\otimes
e_{k}^{\gamma}+\sum_{j\in C^{\beta}}\sum_{k\in
E^{\gamma}}v_{jk}^{\alpha(\gamma)}\otimes c_{j}^{\beta}\otimes
e_{k}^{\gamma}.$

We are still assuming here that $\alpha,\beta$ and $\gamma$ are not all equal.

Since $T^{\alpha\beta\gamma}$ is also equal to 0 under this assumption, it
follows from Lemma 3.4 that $p_{ij}^{(\alpha)\gamma}+g_{ij}^{(\beta)\gamma}$
is a linear combination of the $e_{k}^{\gamma}$ with $k\in E^{\gamma}$, with
similar statements for $q_{ik}^{(\alpha)\beta}+u_{ik}^{\beta(\gamma)}$ and for
$h_{jk}^{\alpha(\beta)}+v_{jk}^{\alpha(\gamma)}$.

We now show that the result is true in the extreme case that $A^{1}=A^{2}$,
$B^{1}=B^{2}$ and $C^{1}=C^{2}$.

######  Corollary 3.6.

Suppose that $A^{1}=A^{2}=[r]$, $B^{1}=B^{2}=[s]$ and $C^{1}=C^{2}=[t]$. Then
the slice ranks of $T^{111}$ and $T^{222}$ are both at most $\min\\{r,s,t\\}$.

###### Proof.

For this proof, let us adopt the convention that summing over $i$ means
summing over $i\in A^{\alpha}=A^{\beta}$, and similarly for $j$ and $k$.

From what we have just proved, with $(\alpha,\beta,\gamma)=(2,2,1)$, we have
for all $i,j$ that $p_{ij}^{(\alpha=2)1}+g_{ij}^{(\beta=2)1}$ is a linear
combination of the $e_{k}^{1}$, and we have similar conclusions for
$q_{ik}^{(\alpha=2)1}+u_{ik}^{1(\gamma=2)}$ and
$h_{jk}^{1(\beta=2)}+v_{jk}^{1(\gamma=2)}$. Here we are writing
$p_{ij}^{(\alpha=2)1}$ to denote the function $p_{ij}^{(\alpha)1}$ in the case
$\alpha=1$, and so on. (It would be nice to be able to write the simpler
$p_{ij}^{(2)1}$, but then it would not be clear that 2 was the value taken by
$\alpha$.)

Now recall that for all $\alpha,\beta,\gamma$, we have that

$T^{\alpha\beta\gamma}(x,y,z)=\sum_{i}a_{i}^{\alpha}(x)b_{i}^{\beta\gamma}(y,z)+\sum_{j}c_{j}^{\beta}(y)d_{j}^{\alpha\gamma}(x,z)+\sum_{k}e_{k}^{\gamma}(z)f_{k}^{\alpha\beta}(x,y).$

Substituting the formulae obtained in Lemma 3.5 for $b_{i}^{11}$, $d_{j}^{11}$
and $f_{k}^{11}$ by taking $(\alpha,\beta,\gamma)=(2,1,1),(1,2,1)$ and
$(1,1,2)$, respectively, we obtain the formula

$\displaystyle T^{111}$ $\displaystyle=\sum_{i,j}a_{i}^{1}\otimes
c_{j}^{1}\otimes p_{ij}^{(\alpha=2)1}+\sum_{i,k}a_{i}^{1}\otimes
q_{ik}^{(\alpha=2)1}\otimes e_{k}^{1}$
$\displaystyle+\sum_{i,j}a_{i}^{1}\otimes c_{j}^{1}\otimes
g_{ij}^{(\beta=2)1}+\sum_{j,k}h_{jk}^{1(\beta=2)}\otimes c_{j}^{1}\otimes
e_{k}^{1}$ $\displaystyle+\sum_{i,k}a_{i}^{1}\otimes
u_{ik}^{1(\gamma=2)}\otimes e_{k}^{1}+\sum_{j,k}v_{jk}^{1(\gamma=2)}\otimes
c_{j}^{1}\otimes e_{k}^{1}.$

The observations in the second paragraph of this proof imply that the right
hand side belongs to the linear span of the functions $a_{i}^{1}\otimes
c_{j}^{1}\otimes e_{k}^{1}$. From this the result for $T^{111}$ follows. The
proof for $T^{222}$ is similar. ∎

Since $2\min\\{r,s,t\\}\leq r+s+t$, we are done in this case.

To do the general case, we reduce to the case covered by Corollary 3.6 using
an inductive argument.

###### Proof of Theorem 1.2 for 3-tensors.

Suppose now that the hypothesis of Corollary 3.6 does not hold. Then without
loss of generality $a_{1}^{2}=0$. Let $P$ be the matrix of a projection to the
one-dimensional subspace of $\mathbb{F}^{X}$ generated by $a_{1}$ such that
$P$ vanishes on all functions supported in $X^{2}$, and let $Q=I-P$. Then

$T(x,y,z)=\sum_{x^{\prime}}P(x,x^{\prime})T(x^{\prime},y,z)+\sum_{x^{\prime}}Q(x,x^{\prime})T(x^{\prime},y,z).$

For every $y,z$, the sum in the first term is a function of $x$, and that
function is a multiple of $a_{1}^{1}$. Therefore, it can be written in the
form $a_{1}^{1}(x)b(y,z)$. Also, if $(y,z)\notin Y^{1}\times Z^{1}$, then
$T(x^{\prime},y,z)=0$ for every $x^{\prime}\in X^{1}$, and therefore the first
term vanishes, by the condition that $P$ vanishes on functions supported in
$X^{2}$. It follows that $b$ is supported on $Y^{1}\times Z^{1}$.

As for the second term, writing $Qg(x,u_{1},\dots,u_{m})$ as shorthand for the
sum $\sum_{x^{\prime}}Q(x,x^{\prime})g(x^{\prime},u_{1},\dots,u_{m})$, it is
equal to

$\sum_{i=1}^{r}Qa_{i}(x)b_{i}(y,z)+\sum_{j=1}^{s}c_{j}(y)Qd_{j}(x,z)+\sum_{k=1}^{t}e_{k}(z)Qf_{k}(x,y).$

But $Qa_{1}=0$, so this is a decomposition of $QT$ into $(r-1)+s+t$ pieces.
Furthermore, since $PT$ is supported in $X^{1}\times Y^{1}\times Z^{1}$, it
follows that $QT$ is also a direct sum. Therefore, by induction on $r+s+t$,
$\sigma((QT)^{111})+\sigma((QT)^{222})\leq r-1+s+t$. Since
$(PT)^{111}(x,y,z)=a_{1}^{1}(x)b(y,z)$ and $(PT)^{222}=0$, it follows that
$\sigma(T^{111})+\sigma(T^{222})\leq r+s+t$. ∎

##  4 Further remarks and questions

There are other basic statements about matrix rank that do not generalize to
slice rank for higher-degree tensors. For instance, it is not true in general
that $\sigma(S\otimes T)=\sigma(S)\sigma(T)$. Indeed, if one takes three
reasonably generic $n\times n\times n$ slice-rank-1 tensors with slices in
different directions – that is, of the kind $a(x)b(y,z)$, $c(y)d(x,z)$, and
$e(z)f(x,y)$ – then their tensor product will tend to have large slice rank.
For instance, if $a,e$ and $f$ are all equal to the standard basis vector
$e_{1}$ and $b,d$ and $f$ are all equal to the identity matrix, then the
tensor product of the three tensors is equivalent to the so-called matrix
multiplication tensor, which has rank $n^{2}$ (see [1, Remark 4.9]). And for
an example in the other direction, if $T:\mathbb{F}_{3}^{3}\to\mathbb{F}_{3}$
is the characteristic function of the set
$\\{(x,y,z)\in\mathbb{F}_{3}^{3}:x+y+z=0\\}$, then it has slice rank 3. (To
see this, observe that if not, then it has a decomposition into two functions
of slice rank 1, so without loss of generality there is no function of type
$e(z)f(x,y)$ involved in the decomposition. But if we then fix $z$, we obtain
a matrix of rank 2, but it is also a permutation matrix so it has rank 3, a
contradiction.) However, the $n$th tensor power of $T$ can be thought of as
the characteristic function of the set
$\\{(x,y,z)\in(\mathbb{F}_{3}^{n})^{3}:x+y+z=0\\}$, which, as the polynomial
method shows, has slice rank exponentially smaller than $3^{n}$.

A special case of Theorem 1.2 is that $\sigma(S\otimes T)=\sigma(S)\sigma(T)$
when $S$ is a diagonal tensor, so we obtain equality for this case, but we
know in advance that the argument cannot be simple enough to generalize to all
tensor products.

Another related question is a long-standing conjecture of Strassen that tensor
rank was additive for direct sums, which, despite being true in a number of
special cases, was eventually _dis_ proved by Shitov in 2017, who found a
highly non-obvious counterexample [8].

We conclude with three questions. The first is whether there is a simultaneous
generalization of the main theorem of this paper and of the result of Sawin
and Tao mentioned earlier. To make this question more precise, suppose that
$X_{i}$ is partitioned into sets $X_{i1},\dots,X_{ir_{i}}$ for each $i$.
Define the _block support_ of a tensor $T:X_{1}\times\dots\times X_{d}$ to be
the set of $(j_{1},\dots,j_{d})$ such that $T$ restricted to the block
$X_{1j_{1}}\times\dots\times X_{dj_{d}}$ is not identically zero. Define a
_block slice_ of $T$ to be the restriction of $T$ to a set of the form

$X_{1}\times\dots\times X_{h-1}\times X_{hj}\times X_{h+1}\times\dots\times
X_{d}.$

Call a block $X_{1j_{1}}\times\dots\times X_{dj_{d}}$ _maximal_ if
$(j_{1},\dots,j_{d})$ is a maximal element of the block support.

If the non-zero blocks of $T$ are covered by some set of block slices, it is
trivial that the slice rank of $T$ is at most the sum of the slice ranks of
those block slices. However, sometimes we can improve on this bound. For
instance, suppose that the block support of a 3-tensor $T$ is contained in
three planes, and contains the intersection of those three planes. Suppose
also that the block corresponding to that intersection has high slice rank
$r$, and that if that block is removed, then the three block slices have small
slice rank $s$. With a suitable example like this, one can arrange that the
sum of the slice ranks of block slices that cover the non-zero blocks is
minimized in the obvious way, which gives an upper bound of at least $3r$. But
one can obtain a better upper bound of $r+3s$ by first decomposing the block
at the intersection and then decomposing the rest of the slices.

With that example in mind, let us define a _partial block slice_ to be the
restriction of $T$ to a union of blocks that forms a subset of a block slice.

######  Question.

Let $T$ be a $d$-tensor as above and let $S$ be its block support. Does it
follow that the slice rank of $T$ is at least the minimum of the sum of the
slice ranks of a set of partial block slices that cover all the maximal blocks
of $T$?

A positive answer to that question may be too much to hope for, in which case
a much weaker preliminary question one might ask is whether if all non-zero
blocks have slice rank at least $r$, and if $m$ block slices are needed to
cover the maximal blocks, then the slice rank of $T$ is at least $mr$.

Another obvious question is the following.

######  Question.

Is partition rank additive for direct sums?

It seems reasonable to guess that the answer is no, since the proof just given
for slice rank appears to fail quite badly. But that is a pure guess, and it
might not be a simple matter to find a counterexample. Naslund showed that if
an appropriate extra step is added to Tao’s proof of Lemma 1.1, then it can be
made to yield the stronger result that the partition rank of a diagonal tensor
is also equal to the number of non-zero entries [5], so diagonal tensors do
not give counterexamples.

Finally, we ask a more open-ended question.

######  Question.

Does Theorem 1.2 have any interesting combinatorial applications?

The answer to this is not obvious, given that up to now combinatorial
applications have tended to be of the result for diagonal tensors (that is, of
Lemma 1.1).

We do not have a promising suggestion for how to apply the result, but can at
least point out one constraint on what a genuine application would need to
look like. Suppose that $T_{1},\dots,T_{m}$ are tensors and that the result of
Sawin and Tao can be used to show that $\sigma(T_{i})\geq r_{i}$. It then
follows easily that $\sigma(T_{1}\oplus\dots\oplus T_{m})\geq
r_{1}+\dots+r_{m}$. (We observed this in the introduction in the special case
where $T_{1}=\dots=T_{m}=\epsilon$.) Therefore, an application of the main
result of this paper would have to be to tensors $T_{1},\dots,T_{m}$ to which
the approach of Sawin and Tao does not apply, which in practice, given the
current state of knowledge, means tensors for which we probably do not know
how to calculate their slice rank.

That refers to applications that use direct sums of _specific_ tensors.
Another possibility might be an argument in which tensors $T_{1},\dots,T_{m}$
are defined in terms of some unknown objects (such as subsets of a finite
group) that satisfy certain hypotheses that are used to derive lower bounds
for the slice ranks $\sigma(T_{i})$. However, for the result of this paper to
be used in an essential way, there would still be constraints on the nature of
the derivation.

Just before this result was posted, an interesting preprint appeared by
Sauermann, who for the first time proved a combinatorial result using a lower
bound for the slice rank of a non-diagonal tensor [6]: to obtain the lower
bound she relied on the approach of Sawin and Tao. That at least suggests that
there is value in extending the known methods for calculating slice rank.

## References

  * [1] J. Blasiak, T. Church, H. Cohn, J. Grochow, E. Naslund, W. Sawin and C. Umans, _On cap sets and the group-theoretic approach to matrix multiplication_ Discrete Analysis 2017:3, 27 pp.
  * [2] E. Croot, V. Lev and P. Pach, _Progression-free sets in $\mathbb{Z}_{4}^{n}$ are exponentially small_, Ann. of Math. 185 (2017), 331-337.
  * [3] D. Eisenbud and J. Harris, _Vector spaces of matrices of low rank_ , Adv. Math. 70 (1988), 135-155.
  * [4] J. Ellenberg and D. Gijswijt, _On large subsets of $\mathbb{F}_{q}^{n}$ with no three-term arithmetic progression_ Ann. of Math. 185 (2017), 339-343.
  * [5] E. Naslund, _The partition rank of a tensor and $k$-right corners in $\mathbb{F}_{q}^{n}$_, Jour. Combin. Th. A 174 (2020), 105190.
  * [6] L. Sauermann, _Finding solutions with distinct variables to systems of linear equations over $\mathbb{F}_{p}$_, arXiv:2105.06863.
  * [7] W. Sawin and T. Tao, _Notes on the “slice rank” of tensors_ , https://terrytao.wordpress.com/2016/08/24/notes-on-the-slice-rank-of-tensors/.
  * [8] Y. Shitov, _Counterexamples to Strassen’s direct sum conjecture_ , Acta Math. 222 (2019), 363-379.
  * [9] T. Tao, _A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound_ , https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound/