- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
The paper concerns many-body approximation (MBA), the recent method for factorization of non-negative tensors, and tackles its structural challenge of dependent factors, induced by the design of the method. This dependence is induced by structure of the MBA method and paper proposes an extension of the method (EMBA), that adds a zero-filled boundary to every tensor mode, applies MBA, and extracts the factors corresponding to the original domain. The authors prove that entries from different extracted factors are not identical functions of the parameters and thus proposed EMBA does not share the 'factor dependency' of the original MBA. Experiments evaluate the resulting representations under factor deletion, recursive approximation, and quantization.
Critical strengths
Paper is well and clearly written, timely and potentially influential in removing the structural gap in recently proposed MBA method for non-negative tensor factorization. Evaluating the usefulness of individual factors beyond complete reconstruction is thus worthwhile and enlightening. The construction is simple to implement, and the theoretical results appear correct.
Empirically, the reported quantization improvements are substantial: at equal stated storage, EMBA reduces COIL100 KL divergence relative to MBA by approximately more that at both, two bits as well as in one bit, quantization regimes (Table 2). Factor-deletion improvements also extend to traffic and EEG data, although the EEG advantage is not uniform across deletion patterns.
Critical weaknesses
- : Proposition 4.3 (and the paper overall) proves a non-inrease of the KL divergence when using EMBA compared to MBA on tensor yet leaves the relation to original MBA, i.e., , where denotes MBA solution to original tensor approximation, unspecified.
This is also stated on lines : "... The proposition does not compare EMBA with MBA fitted directly to the original tensor; this comparison is evaluated empirically in Section 5. ...". Consequently, Proposition 4.3 does not provide a direct guarantee relative to MBA fitted to the original tensor.
It seems that a comparison of the optimal infima might follow by considering zero-extended original MBA distributions as limits of distributions in the extended family. I.e. It directly follows from infimum over the larger set (the zero-extended original MBA distributions can be approached within the extended family). Could the authors clarify this relationship? Formalizing it would clarify whether EMBA changes the factor representation alone or also improves the optimal reconstruction KL.
Anyway, such a comparison of infima would not automatically establish an ordering between the finite numerical solutions returned by the algorithms. So if the above turns useful, the authors should distinguish these two levels of comparison and clarify what guarantees apply to the numerical solutions.
- With all factors retained and un-quantized, MBA and EMBA achieve identical or practically identical reconstruction errors reported in Table 2 and the “no deletion” rows of Tables 6 and 7. On the other hand EMBA demonstrates benefits under factor deletion, recursive approximation, and quantization, including improved compressed reconstruction. Nevertheless, the practical trade-off remains insufficiently characterized: the scalability experiments report up to 6.3x longer fitting time, while real-data quantization is evaluated on a single tensor constructed from ten COIL100 images. Reporting fitting costs alongside compression results on broader datasets would clarify when the additional computation is justified.
The empirical improvements are promising, but the theoretical criterion seems weaker than the interpretation attached to it. I lean toward weak reject pending a clearer treatment of boundary optimization, and stronger evidence connecting factor robustness to the claimed benefits.
Questions for authors
Please address weaknesses 1 and 2 described above.
Additionally, please clarify how exact zero padding is handled in the natural-parameter (information geometric) formulation and its implementation. In particular, how is the logarithm-based initialization described in Appendix D.3 applied to the zero-padded tensor, given that () is undefined? Is any smoothing or special treatment of zero entries used?
4 comments
Thanks to authors for updating their paper and adding the "reconstruction" and "KL infima" equivalence Propositions in response to the raised weaknesses.
I still have some concerns left, however. Firstly, I am not sure the equivalency claim also covers correctly the normalization of the tensor producing EMBA in (7). In particular, in the equivalence proof (Proposition 4.4) reparameterization argument " ... each extended natural parameter contributes to the log reconstruction through cumulative sums ..." in the appendix B both proven inclusions hold, but do not consider Normalization that is a final step when producing EMBA in (7) and thus it is not entirely clear to me that every extended parameterization is admissible ... Similar question arises in the case of proof of Proposition 4.5: how is normalization treated?
As for W2, I appreciate added experiments. They are leveraging COIL 100 dataset again however. Hence an experimental evidence of generalization of the method to other real world datasets stays thin.
I'll keep my score unchanged for now.
Thank you for reading our rebuttal and the new propositions. We agree that explaining how normalization is handled in Eq. (7) more explicitly would make the proofs clearer.
Regarding Proposition 4.4, we have revised the proof to make the role of normalization in Eq. (7) explicit.
For any learned extended-domain parameters , we can construct original-domain MBA parameters using the cumulative-sum structure of MBA. On the original domain, extended parameters whose indices are all at most contribute only a constant. Other parameters contribute to interactions involving only the modes whose extended indices exceed . These contributions can be combined into original-domain MBA parameters, including lower-order interactions. As a result,
e^c P_i(\bar{\theta}),$$ where $c$ is independent of $i$. Since $P(\bar{\theta})$ is normalized, the sum of $P'^{(\mathrm{EMBA})}$ is $e^c$. Normalization in Eq. (7) therefore gives $P^{(\mathrm{EMBA})}=P(\bar{\theta})$. Conversely, any original-domain MBA parameters can be embedded into the extended domain, and normalization of the restriction recovers the original MBA reconstruction. Thus, MBA and EMBA represent the same family of normalized distributions on the original domain. **Regarding Proposition 4.5**, the existing proof accounts for normalization through the identity $$D_{\mathrm{KL}}(T^{(\mathrm{extend})}\Vert P^{(\mathrm{MBA})})= D_{\mathrm{KL}}(T^{(\mathrm{original})}\Vert P^{(\mathrm{EMBA})}) -\log m,$$ where $m$ is the probability mass of the extended MBA reconstruction on the original domain. Since $0<m\leq1$, this identity, together with Proposition 4.4, establishes one direction of the infimum inequality. For the reverse inequality, we show that any original-domain MBA reconstruction can be preserved while making $m$ arbitrarily close to $1$. First, we embed arbitrary original-domain MBA parameters into the extended domain. We then set the one-body parameter at index $2$ to $A>0$ in every mode. By the cumulative-sum structure, this gives every entry in the original domain the same multiplier $e^{AN}$, while entries in the padded region receive smaller multipliers. As a result, the normalized restriction remains the original MBA reconstruction, and the probability mass $m$ on the original domain approaches $1$ as $A\to\infty$. Hence, $-\log m\to0$, giving the reverse inequality and therefore equality of the KL infima. **Regarding the experimental evidence**, as noted in our response to W2, our evaluation also includes real-world datasets other than COIL-100. Specifically, as mentioned in Section 5.1, Appendix F.2 evaluates factor deletion on METR-LA (traffic data) and EEG (brain signals). On both datasets, EMBA achieves lower mean KL divergence and higher mean cosine similarity than MBA for every number of deleted factors (Table 6). In addition, Table 10 in Appendix F.6 includes comparisons between MBA and EMBA on these datasets, including quantization experiments. Thus, our experiments cover multiple real-world datasets from different domains and evaluate EMBA under both factor deletion and quantization, rather than relying solely on COIL-100.Thank you for the clarification and for adding the propositions to paper. This alleviates my W1concerns. And my apologies I missed extended the quantization experiments to EEG and METR-LA. It still keeps the experimental evidence rather narrow, but together with improved theory I will adjust my review score one notch up to 3. Thank you.
We thank the reviewer for the careful reading and constructive feedback.
W1. Relation between EMBA and original-domain MBA
We agree with the reviewer's observation. We have added two propositions establishing that (1) MBA and EMBA represent exactly the same family of normalized distributions on the original domain, and (2) the infima of the reconstruction KL divergences for MBA on the original and zero-extended tensors coincide.
Specifically, let P(θ) denote an MBA reconstruction on the original domain, PMBA(θ) an MBA reconstruction on the zero-extended domain, and PEMBA(θ) its normalized restriction to the original domain. The reconstruction families coincide because extended MBA parameters contributing to the same original-domain interaction can be combined into original MBA parameters, while any original MBA parameterization can also be embedded into the extended domain.
Let m(θ) denote the total probability mass of the extended MBA reconstruction on the original domain. Then
DKL(Textend∥PMBA(θ))=DKL(Toriginal∥PEMBA(θ))−logm(θ).
Since m(θ)≤1, the infimum of the extended-domain KL divergence is at least that of original-domain MBA. Conversely, as the reviewer suggests, any original-domain MBA reconstruction can be extended so that its normalized restriction remains unchanged while the probability mass on the padded entries approaches zero. This establishes the reverse inequality and hence equality of the infima.
Thus, EMBA changes the factor representation without enlarging the reconstruction family or improving the optimal reconstruction KL divergence. As the reviewer notes, equality of the infima does not guarantee an ordering between finite numerical solutions. In our experiments, MBA and EMBA reconstructions agree within the stopping tolerance. We have included the general proofs in the appendix. We have also revised the Introduction, Related Work, and Conclusion to explicitly position EMBA as a method for obtaining structurally distinct factor representations within the same reconstruction model family as MBA.
W2. Computational cost and broader experimental evidence
We agree that the computational cost of EMBA should be evaluated alongside its benefits. To strengthen the empirical evidence, we have added experiments on ten additional COIL-100 tensors constructed using different image selection patterns, evaluating factor deletion and quantization under the same settings as in the paper. We have also extended the quantization experiments to EEG and METR-LA.
The 6.3-fold increase in fitting time is the maximum observed in our scalability experiments. These experiments show that MBA and EMBA exhibit similar scaling trends, with their fitting times differing by an approximately constant factor over the tested tensor sizes. Meanwhile, Figure 6 in Appendix F.3 demonstrates substantial improvements in quantized reconstruction quality relative to storage. Although this figure evaluates the storage–accuracy trade-off rather than the computation–accuracy trade-off, the results suggest that EMBA's additional fitting cost can be worthwhile when quantization robustness is important.
We will include a more detailed comparison of fitting times alongside compression results in the final version to further clarify this trade-off.
Q. Zero padding and initialization, App. D.3
We agree that the treatment of zero entries and boundary solutions requires clarification. Both MBA and EMBA allow zero entries in the input tensor, including Boolean tensors, and evaluate the KL divergence using the convention 0log(0/p)=0 (numerically, ϵ=10−12 is added to both arguments). Since reconstructed distributions are strictly positive for finite natural parameters, a KL infimum may lie on the boundary and need not be attained at finite parameter values. In our experiments, we terminate the optimization when the residual falls below 10−5. Thus, the reported results are obtained from finite numerical solutions rather than assuming that a boundary optimum is attained.
Regarding initialization, the description in Appendix D.3 was incorrect, and we have corrected it. Our implementation does not use the logarithm-based initialization: Newton's method starts from θ=0 (the uniform distribution) for both MBA and EMBA. The input tensor enters the optimization only through its marginals η^, so the logarithm of a zero entry never appears, and no smoothing or other special treatment of zero entries is used.