1- The authors study a nice and timely computational model with statistical physics tools, characterising the phase diagram of several sub-cases, finding first and second order phase transitions, and clarifying why their analysis breaks down if $M$ (tensor rank) is too big.

1- While the presentation is clear and linear, maybe a presentation highlighting more the results would help the reader to parse the long and technical, but standard, computations. See comment below. 2- Lack of code. In this kind of papers, I find publishing code for full reproducibility a must, as the phase diagrams are all coming from numerical solutions of non-trivial equations.

Summary

Model. The authors study a model of rank-M order-p tensor completion, where the observed tensor lives in $R^{N^p}$ and is the sum of M rank-1 spikes. Each spike may be multiplied by a known random observation factor F or not (F=1 case). Only a subset of the tensor is observed (hence the naming "completion" in my review), specifically only $\gamma \times (NM)$, where $NM$ is the total number of scalars to determine, under a uniformity assumption (namely that each of the $N$ tensor dimension is observed uniformly $\alpha M$ times, ensuring that the measurements are distributed uniformly enough). The authors work in the "dense limit" $1 \ll M \ll N$, where the rank of the tensor to retrieve is big, but much smaller than the ambient space dimension $N$.

Results. - The authors fully characterize the Bayes optimal estimation problem for generic priors and observation channels by providing a replica computation and the associated message passing algorithm. - The authors study in detail the phase diagram of the problem in specific settings, finding first and second order phase transitions reminiscent (but not equal) to what happens in rank-1 matrix factorization. - As a more technical remark, the authors argue by a cumulant expansion that some local fields that appear in the computation are Gaussian in the dense limit, and show that this would not be the case if $M = O(N^{p-1})$. They claim (app B, and discussion around eq. 73) that $c$ should be much smaller than any polynomial in $N$.

Comments

Presentation. The paper is quite clearly written, going sequentially first through the derivation and later on to the results. Nonetheless, I think the paper would benefit from a different presentation style. I find: - that the replica computation and message passing derivation are standard for a knowledgeable reader, while very technical for a less knowledgeable one. They could be a bit more "hidden", they do not provide much intuition. - The crucial non-trivial point of the replica computation is the dense limit and the associated cumulant expansion. This should be highlighted much more, and possibly discussed and referenced directly in the introduction when introducing the dense limit itself. - The phase diagrams are the actual main result, and they come only after a lot of technical computations. I do not have a precise suggestion here for the authors, I just wanted to make these points and let them assess whether and how to implement them.

Reproducibility. I think that in papers like this one, access to the code used both to solve the equations and to run AMP is a crucial part of the paper. I strongly encourage the authors to publish the code used both for solving the state equations (and find the subdominant branches / phase transition of the various problems) and for running AMP.

Completion vs factorization. The authors call repeatedly the model they study "tensor factorization", which is fine, but I would suggest the nomenclature "tensor completion". In usual studies of low-rank tensor factorization, the tensor is observed in full (contrary to here where the observation is partial and very sparse) while the spike strength is $O(N^{-1/2})$ (contrary to here where by the lack of observations one needs larger signal-to-noise ratio). This is just nomenclature, let me be clear on this, but I think it would help the reader to frame the results more easily. Additionally, I would invite the authors to: - explore the matrix completion literature and to compare their findings with known results there. A point of entry that I am aware of is [1], but I am sure this is not the only relevant work. - Compare their results in Section 5 with usual tensor factorization. For e.g., the phenomenology of Section 5.2.3 can be observed already in 2+3 rank-1 factorization. I think that heuristically, one could take the limit $\lambda \to 0$ and $\alpha \to \infty$ with appropriate scaling to access the usual tensor factorization regime (still for rank $1 \ll M \ll N$).

Cumulant expansion in BP. In Section 4.9 you say that the cumulant expansion found in replicas is not present. I have a strong feeling that it should be morally the same as the cumulant expansion in 4.2.1, and that while after 142 some terms are dropped as sub-leading, maybe such terms would actually re-sum to $O(1)$ contributions in the message passing scheme. But I do not have a precise argument, just a vibe.

Questions

• A bit after eq 24: it is not clear to me why you say the non-numbered equation is a "generalisation error". Can you explain?

• Eq 46: here you seem to be taking a saddle point over $N$ order parameters $Q_i$ as $M$ goes to infinity, but $M \ll N$. This is ill-posed. I think the computation is still correct under the ansatz eq 55. Could you comment on this?

• Around Eq 73: here you write that $c \ll N$, but say in words and argue in App. B that $c$ should be much smaller than any polynomial in $N$. The notation $c \ll N$ suggests to me that $c = \sqrt{N}$ would be a good choice for $c$, but the argument in words would not allow for this. Can you clarify?

• After Figure 6: "Meanwhile, the possible-to-impossible threshold is αs = 0 since the m= 1 solution always exists at finite" here this is not clear from Figure 6. In Figure 6 the solution m=1 does not appear to exist for lambda 0.5 and any value of alpha. Can you clarify?

• Page 10: "and presumably any polynomial time algorithms" is missing citations to at the very minimum [2].

• Section 5.2.1: is the transition here related to a BBP transition in the spectrum of the observed matrix?

• In Section 3.6 bullet point 1, if I take p=3 and a=1, then the potential is effectively linear. Doe this mean that one has a reduction to low-rank $M$? If not, can you try to explain me what is going on here?

Minor points. - Eq 36: for the non-physicists reading the paper, I find it would be nice to explicitly tell that the identity can be proven by formally expanding the exponential in power series. - Eq 42: here and in surrounding equations pi depends on x and F. It could be stressed, even just in words, to clarify that the averages on x and F are not trivial. - Eq 51: is the differential for M (magnetization) missing? - Remark after Eq 122: this is very opaque for the reader not well-versed in error correcting codes. Maybe you could consider trying to better explain this? - Figure 3 left: maybe an inset zooming around m=1 would help to see that is going on there. - The discussion in Section 3.6 is difficult to follow without knowing very well [11], but seem to be important. It would be very nice if you could make an additional effort to clarify it further. - Figure 3,6,10 have the black lines undefined. I think they are subdominant branches, but that is not super clear, and the caption should probably mention this.

References

[1] A non-backtracking method for long matrix and tensor completion. L Stephan, Y Zhu. 2024 [2] The estimation error of general first order methods. Michael Celentano, Andrea Montanari, Yuchen Wu. 2020

I do not have specific requests for the authors. I just invite them to engage with the points I raised in the Report if they find it useful.

Publish (meets expectations and criteria for this Journal)