Deep Kronecker Network

In plain words

Medical scans such as MRI are large 3D pictures, but a study often has only a few hundred patients. Standard image networks need far more data and are hard to read. This paper proposes a model that stays small enough for such data and shows which parts of the picture drive its prediction.

The model learns a weight map for the scan, the same size as the scan, but builds that map from a few small pieces that are multiplied together in a structured way. Because the pieces are small, far fewer numbers are learned. Because the map is built from blocks, the authors can point to the regions with large weights, and those regions can be checked against known anatomy.

The method works for flat images and for 3D scans, and for both yes/no and numeric outcomes. The authors also show that it can be written as a stack of convolutions without overlap, which links it to both convolutional networks and tensor regression. They test it on Alzheimer's data, where it predicts both a diagnosis and a cognitive score better than the compared methods, and its strongest regions lie around the hippocampus.

TL;DR

• DKN models the coefficient tensor as a sum of R Kronecker products of L factors §2, eq. 3. It is fitted by maximum likelihood, with an alternating minimization over the factors §2 [supp. §S2].
• It is equivalent to a non-overlapping, linear, fully convolutional network §3, Theorem 1. A nonlinear variant is written down but was only tested in simulation [supp. §S4.1].
• The authors prove geometric convergence of the alternating algorithm for rank 1 under a linear model, with RIP and initialization conditions §5 [supp. §S6].
• Author-reported: best results on ADNI (RMSE 0.2258; accuracy 79.25%) and on most simulation settings, with the margin largest at n = 500. Single split, no intervals.
• No official code was found. The card is built from the paper alone.

Problem

Medical imaging datasets are small (hundreds to low thousands of subjects) while each image has millions of voxels §1. Vectorizing images discards spatial structure and yields very high-dimensional predictors §1. CNNs need much more data and are hard to interpret §1. Tensor regression with a CP low-rank structure §1, citing Zhou et al. 2013 reduces parameters but does not exploit the grid structure of images §1. The paper targets a model that adapts to low sample size, is interpretable, and predicts well §1.

Assumptions: the outcome follows a generalized linear model with a known link, and the image enters through the inner product with a coefficient tensor §2, eq. 1–2. Covariates other than the image are omitted §2.

Method

Model. Each subject has an image \mathbf{X}_i of size d \times p \times q and an outcome y_i. The outcome follows an exponential-family GLM with linear predictor \langle \mathbf{X}_i, \mathbf{C} \rangle §2, eq. 1–2. The coefficient tensor is written as a sum of R Kronecker products of L factors §2, eq. 3:

\mathbf{C} = \sum_{r=1}^{R} \mathbf{B}^r_L \otimes \mathbf{B}^r_{L-1} \otimes \cdots \otimes \mathbf{B}^r_1 \qquad \text{[eq. 3]}

Here \mathbf{B}^r_l has size d_l \times p_l \times q_l, with d = \prod_l d_l, p = \prod_l p_l, q = \prod_l q_l §2. The tensor Kronecker product is defined with index grouping [j_k i_k] = j_k + (i_k - 1) q_k §2, Definition 1. The parameter count drops from \prod_l d_l p_l q_l to R \sum_l d_l p_l q_l §2.

Likelihood. Up to a constant, the negative log-likelihood is \sum_i \{\psi(\eta_i) - y_i \eta_i\} with \eta_i = \langle \mathbf{X}_i, \sum_r \bigotimes_l \mathbf{B}^r_l \rangle §2, eq. 4. For a Gaussian outcome this is least squares §2.

Convolutional form. With non-overlapping convolution (stride equal to filter size), g\{\mathbb{E}(y_i)\} = \sum_r \mathbf{X}_i * \mathbf{B}^r_1 * \cdots * \mathbf{B}^r_L §3, Theorem 1. So L is the depth, R the width and the \mathbf{B}^r_l the filters, with no pooling §3. A nonlinear version inserts an activation h between the convolutions §3, eq. 5. The paper says this can be done in standard deep-learning frameworks §3, but only the nonlinear simulations show results [supp. §S4.1].

Relation to tensor regression. Reshape each image with the operator \mathcal{T}, which groups the indices of each factor, into an L-order tensor. The Kronecker structure then becomes a CP structure of rank R on the reshaped image §4, Lemma 1, Theorem 2. Tensor regression on reshaped images therefore solves DKN in a two-step way §4, Remark 2. The authors note that the reshaping step matters for performance §4, Remark 2.

Fitting (alternating minimization). For fixed other layers, layer l's factors enter the predictor linearly through a design built from the reshaped image [supp. §S2, Proposition S1]. The update of layer l is therefore a GLM fit on that design §2 [supp. §S2]. The algorithm alternates layer updates in a forward pass (l = 1..L) and then a backward pass (l = L..1) that rebuilds the partial products [supp. alg. S1].

# Alternating minimization for DKN  [supp. alg. S1]
# Input:  outcomes (n,), images (n, d, p, q), factor sizes per layer, rank R
# Output: layer vectors b_1..b_L, each R stacked factor vectors

def fit_dkn(images, outcomes, factor_sizes, rank, n_iters):
    # Spectral start for the partial products  [supp. §S2, eq. ini2]
    partials = spectral_init(images, outcomes, factor_sizes, rank)
    for t in range(n_iters):
        # Forward pass: refit each layer given the others  [§2, eq. 4]
        for l in range(1, L + 1):
            # Design: image reshaped with the other layers fixed  [supp. §S2]
            design = reshaped_design(images, partials, l)
            # GLM fit for this layer's stacked factors  [§2]
            b_l = glm_fit(design, outcomes, link)
            # Refresh the partial products that depend on this layer
            partials = update_partials(partials, b_l, l)
        # Backward pass: rebuild factor matrices from the layer vectors
        for l in range(L, 0, -1):
            factors = unstack_factors(b_l, rank, factor_sizes[l])
            partials = rebuild_partials(partials, factors, l)
    return b_1, ..., b_L

The pseudocode above is a sketch that follows the update order of the paper's algorithm. It is not the authors' code, and some helper steps are only described in prose in the source.

Regression and classification links. Regression follows the linear model, so the identity link is implied [supp. §S4] §6. Binary classification uses the logit link §6.

Initialization. For l = 2..L, the initial partial products are the top-R left singular vectors of \sum_i y_i \mathcal{R}(\mathbf{X}_i), where \mathcal{R} is a block-reshaping operator that groups the factor sizes of layers l to L [supp. §S2, eq. ini2].

Identifiability. A Kronecker product is unique only up to scaling and permutation [supp. §S6.1]. The normalization fixes \|\mathbf{B}^r_1\|_F = \lambda_r and \|\mathbf{B}^r_l\|_F = 1 for l \geq 2, with \lambda_1 \geq \cdots \geq \lambda_R [supp. §S6.1]. Sufficient and necessary conditions are stated in terms of K-ranks of the stacked factor matrices [supp. §S6.1, Theorem S1]. For L = 2 this reduces to Kronecker-product SVD and orthogonality [supp. §S6.1, Remark].

Structure choice. The paper recommends the deepest model the image size allows: L = log2 of the side length, with 2×2 factors [supp. §S3] §6. It chooses R by BIC, \text{BIC}(R) = 2\ell(\hat{\mathbf{B}}) + (R \sum_l d_l p_l q_l) \log n [supp. §S3]. Low rank R = 1, 2 or 3 often suffices [supp. §S3].

Hyperparameters

Results

Author-reported. Setup: ADNI T1-weighted MRI; four methods; single train/test split §6 [supp. §S5]. Table 1 is in the main text tab. 1.

ADNI (main text, test set). tab. 1

The paper reports DKN as best on both. It does not give intervals or repeated splits for ADNI §6.

Simulation, regression. Mean (sd) over 100 repetitions; estimation is \|\hat{\mathbf{C}} - \mathbf{C}\|_F / \sqrt{dp}, prediction is test RMSE [supp. §S4, tab. S1]. Columns: sparse n=500, sparse n=1000, quasi-sparse n=500, quasi-sparse n=1000.

Bold is added in this card to mark the lowest mean in each column; the paper does not bold these tables. The paper notes TRLasso does best on one-circle prediction at sparse n=1000 [supp. §S4].

Simulation, classification. Mean (sd); estimation is coefficient RMSE; accuracy is on the test set [supp. §S4, tab. S2].

The paper's text says DKN is the strongest in general and especially for quasi-sparse signals and small n [supp. §S4]. The table shows TRLasso higher in accuracy for some sparse cases (for example one-circle, n=1000) [supp. §S4, tab. S2].

Nonlinear DKN vs linear DKN (prediction RMSE, mean (sd)) [supp. §S4.1, tab. S3]:

Algorithm vs Adam (one-circle, sparse; n = 500, 1000, 2000; rank 1; L = 7; 2×2 factors) [supp. §S4.2, tab. S4]:

The time units and hardware are not stated in the table. [supp. §S4.2] says the algorithm converges in about 10 iterations, while Adam may need hundreds of epochs.

Paper vs code

No official code.

Search, in order: the paper's TeX source and the arXiv abstract page list no code or project link. The arXiv page has no comments field. A GitHub repository search for "deep kronecker network" returned four unrelated projects (none by the authors). A search for "kronecker tensor regression feng" returned no results. Nothing by the authors was found, so no code is cited.

Pitfalls

• Test set phase is inconsistent. The main text says ADNI-3 is the test set §6. The supplement says ADNI-2 is the test set, with ADNI-1 and ADNI-GO for training [supp. §S5]. Both give 417 / 241 subjects. Pin down the split before comparing numbers.
• Figure numbering in the main text. The text refers to the coefficient plot as "Fig. 3" §6, but its label is the fourth main figure. Cite the figure by its caption, not its number.
• Citation year for Zhou et al. The arXiv abstract says 2010, while the body and abstract in the TeX cite 2013 §1 §4. Use the body's citation.
• Loss scale. Eq. 4 is "proportional to" the negative log-likelihood, with the constant dropped §2. The BIC in [supp. §S3] uses 2\ell with that same \ell. Use the same convention in both places.
• GLM update not specified. For non-Gaussian outcomes, the paper says each layer is updated by "standard GLM estimation" §2. The solver (IRLS, Newton, or a library call), its convergence rule and any ridge term are not stated.
• Update order is easy to get wrong. The forward pass uses the newest factors for lower layers and previous ones for higher layers. The backward pass rebuilds the partial products [supp. alg. S1]. The paper gives one algorithm with mixed superscripts (t) and (t+1) [supp. alg. S1]; follow the order in that algorithm.
• Kronecker and vector index order. Eq. 3 nests factors from L down to 1 and the index grouping is specified in Definition 1 §2. The vectorization order of tvec and the reshaping operator \mathcal{R} are only partly specified [supp. §S2]. A wrong order gives a permuted coefficient tensor without any error. Check the reconstruction of \mathbf{C} from factors on a small case.
• Initialization uses raw outcomes. The SVD initialization weights images by y_i [supp. §S2, eq. ini2]. For binary outcomes the weights are 0 or 1, and the paper does not say whether outcomes are centred or whether the classification start differs. The effect of this choice is not analysed. The sign of singular vectors is also not fixed in the paper.
• Identifiability normalization is not in the algorithm. The scale and order constraints [supp. §S6.1] are needed to compare factors. They do not change \mathbf{C}. Do not apply them to judge the fit.
• Theory covers a narrow case. The convergence result is for rank 1 under a linear model [supp. §S6.2]. The authors say it extends to general R and to GLMs, but no proof is given. The main text says the same §5.
• Conditions not checkable from data. The RIP constant \delta, the noise bound \|\epsilon\|_2 \le c(1-\delta)\|\mathbf{C}\|_F/2 with unstated c, and the initialization condition on \nu depend on unknowns §5 [supp. §S6.2]. No procedure is given to verify them. The noiseless case reduces the initialization condition to \nu < 2^{1/(L-1)} - 1 [supp. §S6.2, remark].
• Iteration count. T is not stated. [supp. §S4.2] reports about 10 iterations on simulated data. Use a convergence check on the objective.
• Rank grid. The BIC search range for R is not stated. The paper suggests R = 1, 2, 3 first [supp. §S3].
• Simulation parameterization. The quasi-sparse distribution is written \mathcal{N}(1,1) inside the signal and \mathcal{N}(0.1, 0.1) outside [supp. §S4]. The second parameter could be a variance or a standard deviation; the paper does not say which.
• Simulation coefficient is misspecified on purpose. The authors state none of the four true coefficient matrices is exactly of rank 1 to 3 in the Kronecker form [supp. §S4]. This is a deliberate test of robustness, not a sign of a bug.
• CNN details are partial. The optimizer, learning rate, epochs, batch size, pooling size (simulation), width of the fully connected layers and output head for regression are not stated [supp. §S4] [supp. §S5.1]. The CNN numbers are therefore hard to reproduce exactly.
• Nonlinear DKN is preliminary. Its training setup (Adam, learning rate, epochs) is not stated [supp. §S4.1]. The authors describe the study as a future direction [supp. §S4.1].
• Timing comparison has no hardware. The timing table has no hardware or implementation details [supp. §S4.2].
• ADNI data access. ADNI requires a data use agreement. The preprocessing pipeline names operations but not the software or parameters [supp. §S5]. A replication will differ unless the preprocessing is matched.
• Single split. The ADNI results come from one train/test split with no intervals or repeated splits §6. The strong claim "best prediction" should be read with that in mind.
• Hippocampus interpretation. The authors say the regions found agree with prior literature on the hippocampus §6 [supp. §S5]. This is a qualitative check, not a test of the method's accuracy.

Lineage

• Builds on: tensor regression with a CP low-rank structure (Zhou et al. 2013) §1 §4, and its Lasso-penalized variant TRLasso §6 [supp. §S4]. Kronecker-product SVD for L = 2 [supp. §S6.1, citing van 1993]. Reshaping of Kronecker products into CP decompositions (Batselier et al. 2017) §4, Lemma 1.
• Compared against: low-rank matrix regression with a nuclear norm (LRMR, Zhou et al. 2014) [supp. §S4]; CNN as in Hu et al. 2020 for ADNI [supp. §S5]; TR and TRLasso §6.
• Superseded by: not known from this wiki.