Refining Dual Spectral Sparsity in Transformed Tensor Singular Values

We thank the reviewer for acknowledging the motivation, clarity, and theoretical rigor of our work. We would like to clarify that our main contribution is the formulation and theoretical analysis of a unified dual spectral regularization framework. Our focus is on principled modeling and analysis, rather than on practical tuning or computational aspects. Below, we respond to each concern in detail.

W1&Q1: Selection of $(p,q)$

As $(p, q)$ directly shape the structure of our dual spectral regularizer, we appreciate the opportunity to clarify their role and our selection rationale.

(1) Structural role of $(p, q)$: beyond simple hyperparameters

Unlike scalar weights like $\lambda$, the parameters $(p, q)$ specify the intrinsic geometry of the regularizer—$p$ modulates cross-band sparsity, and $q$ modulates within-band low-rankness. These jointly determine the inductive bias of the model and cannot be reduced to a simple scaling factor or tuned post hoc.

This makes parameter selection fundamentally different from standard regularization tuning. Even in simpler vector or matrix settings, choosing $p < 1$ induces strong nonconvexity and leads to identifiability issues. As emphasized in Xu’s ICM 2010 invited talk [RR1], the superiority of $\ell_{1/2}$ regularization arises from its empirical and structural advantages rather than analytic tractability. Our framework generalizes this modeling challenge to the tensor and spectral domain, where the interaction between $p$ and $q$ further increases complexity.

(2) Statistical–computational challenge

Even if an ideal criterion existed for selecting $(p,q)$, its empirical identification would remain unreliable. Under low sampling ratios (e.g., 5%), holding out additional entries for validation reduces the already limited observations, leading to high variance in parameter estimation. Furthermore, the optimization landscape is nonconvex, amplifying the sensitivity to initialization and local minima. These obstacles reflect a well-known statistical–computational challenge, and to the best of our knowledge, no provably consistent and efficient tuning method exists for such quasi-norms in the tensor setting.

(3) Our strategy: one-time grid search and cross-task generalization

Given these challenges, we adopt a standard strategy in low-rank tensor recovery: a one-time grid search on a representative dataset, with the selected $(p, q) \approx (0.9, 0.9)$ applied uniformly across all experiments. This avoids overfitting and ensures fair cross-method comparison. In our case, this choice led to stable results across six diverse remote sensing datasets (e.g., hyperspectral, thermal; see Table 1), demonstrating cross-dataset robustness under moderate distributional variation without per-task tuning. To further confirm robustness, we plan to include a parameter sensitivity analysis in the final version, although our main focus remains on the theoretical formulation of the regularizer.

(4) Toward adaptive selection

Learning $(p, q)$ from data is a valuable direction. While bilevel optimization may offer a viable approach, such methods are generally nontrivial under low sampling and nonconvexity, and are beyond the scope of this paper, which focuses on the formulation and theory of our regularizer.

[RR1] Xu, Z. Data modeling: Visual psychology approach and $\ell_{1/2}$ regularization theory. International Congress of Mathematicians, 2010.

W2&W4(partial): Gap between true $\ell_p$-Schatten-$q$ norm and reweighted surrogate

Below we explain the computational challenges of directly minimizing the quasi-norm and justify our surrogate approach.

(1) Theoretical intractability of the true quasi-norm

To the best of our knowledge, no polynomial-time algorithm exists for minimizing the $\ell_p$-Schatten-$q$ quasi-norm with $p, q < 1$, even in the matrix case (i.e., single-band tensors). Related problems—such as $\ell_p$ minimization for sparse recovery and Schatten-$q$ norm minimization—are NP-hard in general. Our model generalizes both settings and further introduces spectral coupling across frequency bands, making exact minimization at least as hard and likely intractable unless P = NP.

(2) Our reweighted surrogate: structure-aware design (partially addressing W4)

To this point, we adopt a reweighted $\ell_{1/2}$ surrogate.

Unlike conventional reweighted nuclear norm schemes—where the weight for each singular value depends only on its own magnitude—our method explicitly incorporates spectral structure. Specifically, the weight assigned to $\sigma_i^{(k)}$ (the $i$-th singular value of the $k$-th frequency slice) depends on the entire spectrum $\\{\sigma_j^{(k)}\\}_{j=1}^d$ within that slice.

This design captures intra-frequency low-rankness and inter-frequency sparsity in a coupled manner, aligning with the dual spectral geometry of our quasi-norm and enabling a more faithful approximation of the original $\ell_p$-Schatten-$q$ objective.

(3) Approximation gap and stationarity

We acknowledge that the surrogate does not guarantee global optimality with respect to the original quasi-norm. The optimization remains nonconvex, and the solution corresponds to a stationary point. This is a standard and widely accepted tradeoff in nonconvex sparse and low-rank learning. Our method follows the same practical philosophy as many $\ell_p$-based approaches: using structured surrogates to approximate desirable inductive biases without solving intractable objectives.

We will clarify the distinction between the true quasi-norm and the implemented surrogate in the revision. Importantly, our surrogate retains the core modeling principle—the promotion of dual spectral structure—while offering computational tractability. We view this design as a principled and practical step toward expressive tensor models, and not as a weakness specific to our method.

Q2: Computational complexity

The per-iteration computational complexity is analyzed in Appendix D.2:

• Each iteration consists of (i) a linear transform on $d_1 d_2$ tubes of length $m$ (cost $O(d_1 d_2 m \log m)$ using DCT/FFT), and (ii) $m$ SVDs of $d_1 \times d_2$ matrices (cost $O(m d_1 d_2 \min(d_1, d_2))$).
• Despite nonconvexity, the algorithm converges efficiently in practice (Figure 4).

W3&W4(partial)&Q3: Testing other transforms

We added preliminary experiments using DFT, random orthogonal transforms, and an oracle transform derived from the singular vectors of the mode-3 unfolding of the ground-truth tensor ([R2]).

Table A. PSNR / SSIM for different transforms on Salinas A

These results suggest that the proposed regularizer remains effective under various invertible transforms (e.g., DFT, random orthogonal), as long as $(p,q)$ are appropriately chosen. The consistent advantage over TNN, even without DCT, implies that the improvement may stem from the regularizer rather than the transform. These are preliminary results, and we agree that adaptive or learned transforms are promising for future work.

W4(partial)&Q4: Comparison with stronger baselines

We added comparisons with Framelet TNN [R1] and Adaptive TNN. Following [RR2], the Adaptive TNN constructs the transform matrix at each iteration via the left singular vectors of the current tensor's mode-3 unfolding, thereby avoiding explicit rank selection as in [R2]. We adopt the same adaptive scheme for our method to ensure fair comparison.

Table B. Comparison with Framelet and Adaptive TNN on Salinas A ($(p,q) = (0.8961,0.8966)$)

Our method achieves competitive performance, indicating that the gain arises not only from transform selection but from the joint spectral modeling induced by our regularizer. Furthermore, the framework provides a unified formulation that subsumes both fixed and adaptive transforms, as well as standard low-rank models as special cases.

[RR2] Zhang, X. et al. Low-rank tensor completion with Poisson observations. T-PAMI 2021.

Q5: Noiseless Tensor completion

We conducted preliminary experiments on noiseless tensor completion.

Table C. Tensor completion (noiseless) on Salinas A ($(p,q) = (0.8961,0.8966)$)

These results suggest that our method performs well in the noiseless setting, further supporting its robustness across noise levels. We thank the reviewer for this helpful suggestion and will extend the evaluation to more datasets and tasks in the revision.

Dear Reviewer VURK,

Thank you again for your thoughtful follow-up and for your constructive perspective throughout the review process. We are encouraged by your recognition of the motivation and theoretical novelty of our work, and we appreciate your careful reassessment and clarification of the main issues that remain to be addressed for completeness.

We fully understand and appreciate the importance of incorporating all promised analyses and experiments in the final revision, particularly with respect to parameter sensitivity and surrogate optimization. We would like to emphasize that the remaining work is primarily related to computational time and the organization of results, rather than substantive technical or methodological challenges. All required techniques, algorithms, and implementations are already in place; what remains is largely a matter of executing additional experiments and presenting the results clearly and thoroughly.

1. Parameter Sensitivity Analysis for $p$ and $q$: We have already started comprehensive sensitivity experiments, covering $p, q \in \\{0.05, 0.1, 0.15, 0.2, ..., 1.0\\}$ on representative datasets (Salinas A, Cloth, and OSU Thermal). The main findings and robustness analysis will be presented in a new subsection of Section 4.3, with key plots and heatmaps in the main text, and complete results in the appendix and supplementary materials. Due to computational cost, the full grid may not be available during this discussion phase, but we guarantee that all analyses will be included in the final version.

2. Detailed Justification and Analysis of Surrogate Optimization: Building upon the content from our rebuttal, in Section 3.3 we will further expand and detail the discussion by adding a dedicated subsection addressing the theoretical intractability of optimizing the true $\ell_p$-Schatten-$q$ quasi-norm for $p, q < 1$. We will explicitly state that, even for small-scale problems, global optima and their gap to the surrogate cannot be reliably computed. We will provide a transparent rationale for our structure-aware surrogate, clarify its inductive bias and limitations, and highlight these issues in the main text and appendix to ensure academic transparency and integrity.

3. Additional Experiments and Completeness: All additional experiments discussed in our rebuttal—including transform comparisons, stronger baselines, noiseless completion, and results on the remaining five remote sensing datasets—have been either completed or are in the final stages of preparation. We reiterate that these are purely matters of computation and presentation, and do not involve any unresolved technical challenges. We are fully committed to including all these results, along with detailed tables and analyses, in the main paper and appendices for the final version.

We sincerely appreciate your rigorous review and constructive engagement throughout this process. Please be assured that your recommendations will be comprehensively addressed, and the final version will reflect both the theoretical value and experimental thoroughness expected for a high-quality contribution.

We sincerely thank the reviewer for acknowledging the theoretical contribution of Theorem 4.2 and the dual spectral sparsity framework, and for raising important concerns about the algorithmic aspects of our method. We address each point below.

Weakness & Question 1: Scalability and use of SVD

Response: We agree that computing exact t-SVDs can be computationally intensive, particularly for large tensors with wide frontal slices. In our current implementation, we use full SVDs to ensure clarity and reproducibility. However, the algorithm readily accommodates more scalable SVD variants:

• Truncated SVD can be employed when approximate low-rank structure is sufficient;
• Randomized SVD offers significant reductions in computation while preserving accuracy;
• Subspace parameterization is another promising strategy, as demonstrated in large-scale matrix completion.

We acknowledge that integrating such techniques is essential for scaling to large datasets. Our primary focus in this work is to illustrate the modeling benefits of the proposed dual spectral regularizer, and we plan to incorporate these acceleration strategies in future implementations. Thus, our current algorithm serves as a flexible framework rather than a fixed pipeline.

Question 2: Convergence behavior of the numerical algorithm

Response: We agree with the reviewer that convergence is an important concern in nonconvex optimization. While the proposed ADMM algorithm involves a nonconvex objective due to the reweighted $\ell_{1/2}$-type regularizer, we empirically observe stable and monotonic descent of the objective, as shown in Appendix D.4. In all experiments, the iterates stabilize within a reasonable number of steps, and the PSNR curve flattens out, indicating convergence to a stationary solution.

Each subproblem in the ADMM update—such as spectral thresholding—is solved either in closed form (when possible) or via standard reweighting heuristics. However, due to the nonconvex and adaptive nature of the reweighting scheme, we do not claim convergence to a global minimum, nor do we rely on strong assumptions like the Kurdyka–Łojasiewicz (KL) property, which are often needed for formal guarantees in nonconvex ADMM settings.

We view our current algorithm as a practical and empirically validated heuristic, consistent with other nonconvex regularization methods in the literature. A rigorous convergence analysis, particularly under dual spectral coupling and reweighting, remains an important direction for future theoretical work.

Question 3: Do the algorithms achieve the theoretical minimax bounds in Theorem 4.2?

Response: This is an excellent and deep question. Theorem 4.2 provides an information-theoretic minimax lower bound on the estimation error under dual spectral sparsity. It characterizes the fundamental statistical difficulty of the problem and applies to any estimator, whether efficient or not.

However, we do not claim that our algorithm achieves this minimax rate. Achieving such bounds algorithmically is extremely challenging for several reasons:

• The $\ell_p$-Schatten-$q$ regularizer is nonconvex in both $p$ and $q$;
• The objective involves cross-frequency coupling, preventing separable optimization;
• Existing works on algorithmic minimax optimality focus on convex or separable nonconvex problems (e.g., $\ell_1$, nuclear norm), which do not apply here.

In fact, to our knowledge, no known polynomial-time algorithm achieves the exact minimax rate under dual spectral sparsity in tensors. This reflects a well-known statistical–computational gap, where the optimal statistical rate cannot be efficiently attained due to computational hardness.

Thus, our theoretical and algorithmic contributions are complementary: Theorem 4.2 clarifies what is statistically possible in principle, while our algorithm provides a practical and interpretable way to approximate this structure.

Question 4: Making the transformation matrix $M$ learnable

Response: We thank the reviewer for this insightful suggestion. Indeed, our current work uses a fixed DCT transform to exploit smoothness and compressibility in the spectral domain.

That said, making $M$ learnable is entirely feasible and highly promising:

• One could parameterize $M$ as a convolutional kernel bank, a product of Householder reflections, or a learned framelet dictionary;
• This would enable adaptive regularization tailored to data-specific spectral structures;
• It turns the problem into a bilevel optimization task, where both the transform and the coefficients are jointly optimized.

To this end, we conducted preliminary experiments with an adaptive transform strategy (following [R1]), where the transformation matrix is updated at each iteration using the left singular vectors of the current tensor’s mode-3 unfolding. This method eliminates the need for manual rank selection.

As shown in the table below, the proposed adaptive variant further improves performance:

Table A: Noisy Tensor Completion on Salinas A

Table B: Noiseless Tensor Completion on Salinas A

These results suggest that the benefits of our dual spectral regularizer can be further enhanced by incorporating data-adaptive transforms. We agree this is a very promising direction for future research and thank the reviewer for encouraging it.

[R1] Zhang, X. et al. Low-rank tensor completion with Poisson observations. T-PAMI 2021.

Conclusion

In summary:

• We acknowledge the computational cost of exact SVDs and plan to adopt scalable surrogates such as randomized SVD;
• Our algorithm empirically converges reliably, although a full convergence proof is left for future work;
• Theorem 4.2 provides a fundamental statistical lower bound, which our algorithm approximates but does not provably attain;
• Making the transform learnable improves performance and fits naturally into our framework.

We deeply appreciate the reviewer’s thoughtful and technically engaged comments. These points helped us better articulate the contributions and limitations of our work, and we will incorporate this feedback in the final revision.

Dear Reviewer Tsyi,

Can you clarify whether you have checked and verified the proofs leading to Theorem 4.2 in the supplementary material? As you consider this as the main strength of the paper, it is important for my own assessment to know this, as checking the proof was beyond the scope of my abilities within a reasonable amount of time.

Thank you for the thoughtful question. We fully agree that theoretical results—especially non-asymptotic bounds—can benefit from empirical illustrations of their qualitative behavior.

We conducted preliminary small-scale experiments to explore Part I of Theorem 4.2, focusing on how the estimation error varies with three key structural parameters: spectral rank $r$, spectral sparsity $s$, and noise-to-signal ratio (NSR).

Synthetic Tensor Construction We construct a third-order tensor $\underline{\mathbf{L}} \in \mathbb{R}^{d \times d \times m}$ that is low-rank in a small number of frequency slices and zero elsewhere in the frequency domain:

• Activate $s$ frequency slices (out of $m$), each as a rank-$r$ matrix $\tilde{\underline{\mathbf{L}}}^{(i)} = \mathbf{A}_i \mathbf{B}_i$, where $\mathbf{A}_i \in \mathbb{R}^{d \times r}$ and $\mathbf{B}_i \in \mathbb{R}^{r \times d}$ are drawn from standard Gaussian ensembles.
• Set the remaining $m - s$ slices to zero, inducing spectral sparsity.
• Apply an inverse discrete cosine transform (iDCT) along the third mode of $\tilde{\underline{\mathbf{L}}}$ to return the tensor to the spatial domain.

This yields ground-truth tensors consistent with the assumptions in our analysis.

Observation Model Following the setup in our paper, we normalize $\|\underline{\mathbf{L}}\|_{\mathrm{F}} = 1$ and add isotropic Gaussian noise $\underline{\mathbf{E}} \sim \mathcal{N}(0, \sigma^2 \mathbf{I})$ with variance

The observed tensor is

When one considers the sample mean $\bar{\underline{\mathbf{Y}}}$ over $n$ i.i.d. observations, the aggregated noise $\bar{\underline{\mathbf{E}}}$ has variance $\sigma^2 / n$. In our setup, we treat $\sigma^2 / n$ as a single effective variance parameter so that the noise model remains consistent with the paper’s formulation.

Error Metric We report the squared error (SE) defined as $\mathrm{SE} = \\|\underline{\mathbf{\hat{L}}} - \underline{\mathbf{L}}\\|_{\mathrm{F}}^2,$ where $\underline{\mathbf{\hat{L}}}$ is the recovered tensor. Since $\|\underline{\mathbf{L}}\|_{\mathrm{F}} = 1$, the expected SE scales proportionally to the total noise energy $\sigma^2 d^2 m$, which matches the observed magnitude.

Each reported SE value is the average over 10 independent trials, where in each trial a new ground-truth tensor $\underline{\mathbf{L}}$ and its corresponding Gaussian noise are independently generated.

Preliminary Results (Small-scale: $d=50$, $m=50$)

Table C1. Vary NSR ($r=1$, $s=2$)

Table C2. Vary $r$ (NSR=0.10, $s=2$)

Table C3. Vary $s$ (NSR=0.10, $r=2$)

Observations These results are approximately consistent with the theoretical dependence on $(r, s, \mathrm{NSR})$:

• SE tends to increase with NSR, consistent with the additive Gaussian noise model.
• Larger $r$ is generally associated with higher SE, reflecting the increased complexity of intra-slice low-rank structures.
• Larger $s$ (more active frequency slices) correlates with higher SE, as more independent components need to be recovered.

While this study focuses on a small-scale setting, the results provide preliminary evidence that the method’s behavior is approximately consistent with the predicted qualitative patterns. We appreciate the reviewer’s suggestion and intend to extend these experiments to larger-scale and more realistic scenarios in future work, aiming for a more thorough empirical assessment of the bound.

We sincerely thank the reviewer for carefully reading our submission and recognizing the novelty of the proposed quasi-norm, the structural modeling of dual spectral sparsity, and the theoretical depth of Theorem 4.2. We now respond to the reviewer’s concerns point by point.

Concern 1: On the Scope and Relevance to Machine Learning

We respectfully disagree with the concern that our submission falls outside the scope of a machine learning conference.

• Problem Relevance: The paper addresses a core machine learning challenge—designing expressive, theoretically grounded regularization for high-order structured data. Our dual spectral quasi-norm provides a structured inductive bias, crucial for modern ML settings with limited observations and high-dimensional data. Beyond tensor completion, it has the potential to inspire advancements in tasks like multi-modal representation learning and generative modeling by capturing structured sparsity in complex data, aligning with NeurIPS’s focus on general ML and interdisciplinary methods.

• Theoretical Contributions in ML Venues: Related theoretical works on tensor/matrix low-rank modeling, nonconvex optimization, and information-theoretic analysis have consistently appeared at top machine learning venues such as NeurIPS and ICML (e.g., [R1–R9]). Many of these studies also focus on synthetic or semi-synthetic settings, such as tensor completion, as standard benchmarks for isolating and validating theoretical insights. Our work follows this tradition by proposing a novel regularizer with provable minimax guarantees and a tailored optimization strategy, aiming to advance the theoretical foundations of tensor modeling in machine learning.

• NeurIPS CFP Alignment: Our submission aligns closely with key themes highlighted in the NeurIPS 2025 Call for Papers, including “Optimization (e.g., convex and non-convex, stochastic, robust),” “Theory (e.g., control theory, learning theory, algorithmic game theory),” and “General machine learning (supervised, unsupervised, online, active, etc.).” Moreover, NeurIPS explicitly encourages “interdisciplinary submissions that do not fit neatly into existing categories” and “in-depth analysis of existing methods that provide new insights,” both of which are directly reflected in our work through the development of novel regularization theory and the design of nonconvex algorithms in high-order tensor settings.

• Verification Burden: We appreciate the reviewer’s acknowledgment of the theoretical depth of our work. We understand that verifying complex proofs can be time-consuming within the review timeline. Nevertheless, we believe that the potential value of theoretical contributions should not be discounted solely due to their verification cost. To aid verification, we have carefully structured the supplementary material, organizing the proofs in a modular and transparent manner with clearly stated assumptions and intermediate steps.

We therefore believe that our work sits well within the current scope and direction of the NeurIPS community.

[R1] Karnik et al. Implicit regularization for tubal tensor factorizations via gradient descent. ICML 2025.

[R2] Wang et al. Low-rank tensor transitions (LoRT) for transferable tensor regression. ICML 2025.

[R3] Wang et al. Generalized tensor decomposition for understanding multi-output regression under combinatorial shifts. NeurIPS 2024.

[R4] Swartworth et al. Fast sampling-based sketches for tensors. ICML 2024.

[R5] Ma et al. Algorithmic regularization in tensor optimization: towards a lifted approach in matrix sensing. NeurIPS 2023.

[R6] Sarlos et al. Hardness of low rank approximation of entrywise transformed matrix products. NeurIPS 2023.

[R7] Kacham et al. Lower bounds on adaptive sensing for matrix recovery. NeurIPS 2023.

[R8] Qiu et al. Fast and provable nonconvex tensor RPCA. ICML 2022.

[R9] Qin et al. Error analysis of tensor-train cross approximation. NeurIPS 2022.

Concern 2: On the Global Tuning of $(p, q)$ and Framework Flexibility

We appreciate the reviewer’s observation regarding the practical use of $(p, q)$ and the flexibility of our quasi-norm framework.

• Global Tuning Rationale: While our quasi-norm is theoretically flexible, in this work we chose to fix $(p, q)$ globally—via a single grid search on a representative dataset—across all datasets and sampling ratios. This design choice was made to ensure fair comparison and avoid overfitting, especially under low-sample settings where validation-based tuning is unreliable due to data scarcity. This approach is standard in low-rank tensor learning and leads to stable performance across diverse datasets, as shown in Table 1.

• Flexibility and Practicality: We agree that dataset-adaptive tuning could further leverage the full flexibility of the framework. However, in low-sampling regimes, splitting the data for validation often leads to unstable or even misleading hyperparameter selection, undermining the robustness of the comparison. Therefore, a global fixed configuration strikes a balance between robustness and reproducibility, even if it does not fully exploit all degrees of flexibility in each experiment.

• Empirical Robustness: Despite using a single $(p, q)$ setting, our method demonstrates strong generalization and robustness across six datasets of varying types and distributions (see Table 1). This suggests that the regularizer itself encodes a meaningful inductive bias that works well in practice without per-dataset tuning.

• Future Potential for Adaptive Tuning: We acknowledge that developing data-driven or adaptive strategies to select $(p, q)$ would allow for even more effective exploitation of the framework’s flexibility. Approaches such as bilevel optimization, spectral heuristics, or meta-learning are promising and relevant, but present significant statistical and computational challenges, particularly under nonconvexity and limited data. We see this as an important direction for future work and believe our theoretical framework can provide a foundation for such advances.

Concern 3: On the Use of DCT and Comparison with Other Methods

We thank the reviewer for raising the concern that the observed performance gain may be primarily due to DCT preprocessing. To directly address this, we conducted additional experiments in which we applied DCT preprocessing to several baseline methods, including $k$-Supp, $\ell_{1-2}$, and Schatten-$1/2$, and compared the results with our proposed method.

Table: Effect of DCT Preprocessing on Salinas A (PSNR / SSIM)

These results show that, while DCT preprocessing improves all baselines, our method consistently achieves better performance across all sampling ratios, indicating that the improvement stems from our dual spectral modeling rather than DCT alone. Additional comparisons are provided in Tables A–C of the rebuttal to Reviewer VURK.

Concern 4: On Optimization and ADMM Stability

The reviewer raises concerns about the optimizer’s ability to find good solutions given the nonconvex and reweighted structure.

• Theoretical Gap: We acknowledge that global convergence guarantees are not available, as standard ADMM theory does not cover our reweighted nonconvex setting.
• Empirical Evidence: As shown in Appendix D.4 (Figure 4), our algorithm demonstrates smooth and stable convergence in both the objective value and PSNR.
• Community Practice: Reweighting and thresholding are widely used in nonconvex sparse and low-rank learning, and often yield good empirical performance despite theoretical challenges. We follow this established practice and are transparent about its limitations.

A more rigorous theoretical analysis of convergence is an important direction for future work.

Concern 5: On the Use of Ground Truth in Tuning $(p,q)$

We thank the reviewer for raising this important point. The fixed $(p, q)$ values were chosen by a one-time grid search on a representative dataset with known ground truth and then kept unchanged for all other datasets and sampling ratios; no ground-truth information was used after this initial step.

This approach follows established practice in low-rank tensor recovery, where parameters are typically set using a reference dataset to ensure consistency and reproducibility, especially when low observation ratios make validation-based tuning unreliable. In our experiments, we applied the same fixed $(p, q)$ values across all tested datasets, and observed stable results on six remote sensing datasets with varying characteristics (see Table 1). While these results suggest a degree of robustness to moderate distributional variation, we acknowledge that optimal parameter choices may vary in other settings, and further investigation on broader datasets would be valuable.

The challenge of hyperparameter selection is common in nonconvex regularization methods involving quasi-norms. Our approach—fixing hyperparameters based on a reference dataset—follows standard practice and shows satisfactory robustness in our experiments. Nonetheless, developing adaptive, ground-truth-free strategies remains an open problem, which we plan to pursue. We will also add a sensitivity analysis, though our main focus here is on the theoretical aspects of the regularizer; see also our response to W1&Q1 of Reviewer VURK for more details.

Analysis of these observations

Based on these observations, our interpretation is as follows:

1. Effectiveness with room for improvement

   The gain at $p/q=0.99$ suggests that frequency sparsity has practical value. However, the relatively modest margin implies that our current solver may not yet fully exploit its potential.

2. Why the gain fades as $p \to q$

   In our formulation, the per-band regularization term is typically $F_{q,\tau}^{(k)} = \left( \sum_i (\sigma_i^{(k)})^q \right)^\tau, \quad q<1, \ \tau=p/q<1.$ When $\tau<1$, the problem becomes substantially more non-convex than the widely studied $\tau\ge1$ cases in sparse optimization [RR1]. To our knowledge, most existing bilayer non-convex sparse optimization methods focus on $q<1,\ \tau\ge1$ and are not applicable here. The added difficulty for $\tau<1$ lies in the stronger non-convexity, which increases optimization challenges. To make the problem tractable, let the current iterate be $\\{\sigma_{i,0}^{(k)}\\}_{i=1}^d$. We adopt the heuristic decomposition $x^\tau = x^1 \cdot x^{\tau-1}$, leading to the surrogate

Response to Concern 3: Effect of Dual Spectral Sparsity vs. Iterative Reweighting

What remains unclear from your empirical validations is if indeed the dual spectral modeling is providing the empirical improvement or whether it is rather the reweighing of the singular values without coupling across frontal slices (especially since your optimal p is very close to q, so it is almost distinguishable from $p=q$. Doing an experiment with a reweighed nuclear norm where the weighting factor is tuned to optimizer a Schatten-p (with p=q) tensor quasi-norm would provide insight into this question.

In response to the reviewer’s suggestion, we first conducted a targeted experiment with the reweighted tensor nuclear norm (RWTNN) baseline, which is tailored for the tensor Schatten-$p$ quasi-norm in the special case $p=q$.

The motivation was as follows: if the observed performance gain were driven solely by reweighting singular values, without leveraging frequency–low-rank coupling, then evaluating a RWTNN baseline tuned for the special case $p=q$ (i.e., no inter-slice coupling) should, in principle, remove the performance difference.

Table D3. PSNR and SSIM on Cloth

Table D4. PSNR and SSIM on OSU Thermal

The outcome suggests that our method outperforms RWTNN for Schatten-$p$.

However, this alone does not prove that the improvement stems from frequency–low-rank coupling. A closer look reveals that our formulation uses weighted $\ell_{1/2}$ minimization, which is well known to induce stronger sparsity than the $\ell_1$ weighting used in standard nuclear norm reweighting. This stronger low-rank induction also naturally appears as a special-case of our method when $p = q < 1$, and we believe it is worth noting as part of the overall contribution.

Yet this raises a natural question: if $p$ and $q$ are extremely close, is the cross-band coupling effect even active?

Mathematically, when $p \to q$, the frequency sparsity term and the per-band low-rank term decouple, and for $p=q$ the coupling vanishes entirely. In our original configuration ($p=0.8961$, $q=0.8966$), $p/q \approx 0.999$, suggesting a near-decoupled regime.

To probe this, we fixed $q=0.8966$ and varied $p/q$:

Table D5. PSNR and SSIM on Cloth (fixed $q=0.8966$)

Table D6. PSNR and SSIM on OSU Thermal (fixed $q=0.8966$)

Direct observation from the $p/q$ variation experiments

From Tables D.5 and D.6, we make the following direct observations:

1. Even mild frequency sparsity ($p/q=0.99$) yields measurable and consistent improvements across datasets and sampling rates compared to the $p=q$ case.
2. As $p \to q$, the coupling effect between frequency sparsity and per-band low-rankness fades, and for $p=q$ it disappears entirely. This explains why the performance gain is modest when $p$ and $q$ are nearly equal.

Taken together, these observations suggest that frequency sparsity plays a potentially meaningful role in modeling, and that its empirical advantage appears to be influenced by the degree of coupling with the low-rank component.

We sincerely thank Reviewer u2tt for the careful and principled evaluation of our work, and for highlighting the importance of independent verification of theoretical results. We also appreciate Reviewer VURK’s effort in carefully checking our minimax lower bound proof (Theorem 4.2) and expressing confidence in its rigor. This independent confirmation helps ensure the soundness of our theoretical contributions.

Below we respond to the three main concerns in sequence.

Response to Concern 1: Appropriateness for this Venue & Validity of Theory

I need to rely on the fact that at least one of the reviewers has checked them in detail to be confident in their validity.

We fully understand the need for explicit confirmation. During the discussion, Reviewer VURK stated that they had read our minimax lower bound proof in detail and found the reasoning rigorous. In particular, Lemma C.9 extends the classical packing construction by incorporating per-band spectral rank constraints, which are central to the two-layer structure analyzed in Theorem 4.2.

Theorem 4.2 is proved via a fully constructive information-theoretic approach, establishing minimax risk lower bounds for least-squares estimation under a double-layer frequency-sparse model. The proof strategy:

• Separates frequency sparsity (few active frequency slices) from the intra-slice low-rank or Schatten-$q$ structure,

• Constructs well-separated parameter sets for each part,

• Applies Fano’s inequality to bound the difficulty of support identification and intra-slice content estimation, and

• Combines these via a union bound to yield a lower bound jointly determined by the frequency-support complexity ($s\log(em/s)$) and the intra-slice representation difficulty (e.g., $sr,d$ or $sR(\frac{\sigma^2}{n}d)^{1-\frac{q}{2}}$).

• In the soft-constraint setting ($\ell_0$–$S_q$, $\ell_p$–$S_q$), the proof additionally uses covering-number and entropy-number bounds to manage nonconvexity and nonsparsity.

To improve clarity in the final version, we plan to add a more concise proof-outline in the main text, mapping each logical step to the corresponding lemmas in the appendix.

Response to Concern 2: Tuning of (p,q) Parameters

Can you clarify one which dataset you used to tune the (p,q) parameters? If it is Salinas A, the tables you provide for Salinas A do not represent a fair experiment (see also tables in your reply to reviewer VURK). It would be better if you evaluate the methods on a dataset on which you did not tune those parameters as only this constitutes a fair experiment. For example, I would be curious to see how competitive k-Supp, and Schatten-p if combined with DCT (as it, as you acknowledge, is responsible for a significant amount of the improvement).

We tuned $(p,q)$ only once on Indian Pines using a coarse-to-fine grid search, and fixed this pair for all datasets and sampling ratios. This avoids per-dataset overfitting and is standard when reliable validation splits are unavailable at low sampling rates.

Salinas A was not used for tuning. It was reported because its small size allows quick evaluation within the rebuttal period. In fact, alternative untuned settings $(0.80,0.81)$ and $(0.70,0.71)$ achieve higher mean $(\mathrm{PSNR},\mathrm{SSIM})$ at SR = 5% over 10 trials ($(28.71,0.7451)$ and $(28.72,0.7505)$) than our fixed $(0.8961,0.8966)$ ($(\mathrm{PSNR},\mathrm{SSIM})=(28.43,0.7374)$ in Table 1), suggesting no dataset-specific tuning advantage.

Following the suggestion, we evaluated the fixed $(0.8961,0.8966)$ on two datasets not used in tuning—Cloth and OSU Thermal—under identical DCT preprocessing in the noiseless tensor completion. Cloth was downsampled to $256\times256\times31$ for efficiency.

Table D1. PSNR and SSIM on Cloth (DCT, noiseless)

Table D2. PSNR and SSIM on OSU Thermal (DCT, noiseless)

Since DCT was applied equally to all methods, the consistent advantage of our method reflects the effect of the proposed regularizer rather than a preprocessing artifact. Together with the Salinas A counterexample, this supports both the fairness and the cross-dataset generalization of our chosen $(p,q)$ configuration. See also Tables B and C in our rebuttal to Reviewer VURK for the improvement on adaptive transform in comparison with Adaptive TNN.

We thank Reviewer 6m4n for raising this important point. We agree that there may be more efficient approaches for optimizing the quasi-norm when $\tau<1$, and we see value in exploring such possibilities in future work. We have revised the wording, slightly softening the phrasing around “nontrivial” to “mathematical subtleties” and “technically challenging problem” to better reflect the nuance. While our current focus was on establishing the formulation and its theoretical guarantees, we welcome further discussions or suggestions that could help extend the optimization strategy.

We sincerely thank the reviewer for recognizing both the theoretical rigor and technical novelty of our work. Below, we address the concerns regarding hyperparameter selection, robustness to noise distributions, and convergence behavior of the proposed algorithm.

Concern 1: On the selection and stability of $(p, q)$, especially under high observation ratios

Response: We appreciate this important question. In our implementation, we adopt a simple and reproducible strategy: a one-time coarse-to-fine grid search on a representative dataset with ground truth. The selected $(p, q)$ values are then fixed for all subsequent datasets and sampling ratios. This ensures consistency, prevents overfitting to specific tasks, and is consistent with standard practice in low-sample tensor recovery, where validation-based tuning is often unreliable. See also our response to W1&Q1 of Reviewer VURK for further details on the selection of $(p, q)$.

To address the concern regarding potential overfitting at higher observation ratios, we evaluated our method with the same $(p, q)$ and regularization strength $\lambda = 0.4$ at higher sampling rates. Results on Salinas A and OSU Thermal are shown below.

Table A. Salinas A (higher sampling ratios)

Table B. OSU Thermal (higher sampling ratios)

These results demonstrate that the fixed configuration generalizes well and continues to yield improved reconstruction quality as more data becomes available. We observe no sign of performance collapse or overfitting, even at higher sampling ratios.

While we acknowledge that theoretical understanding of $(p,q)$ tuning under nonconvex regularization remains incomplete, this limitation is shared by many quasi-norm-based frameworks. A deeper analysis of parameter identifiability and data-dependent selection remains a valuable direction for future theoretical work.

Concern 2: Robustness under non-Gaussian noise

Response: We thank the reviewer for this important question. While our theoretical guarantees focus on the Gaussian setting, the proposed framework is not inherently restricted to Gaussian noise. To demonstrate empirical robustness, we conducted preliminary experiments using uniform noise, where each entry is sampled from $[0, u]$ with $u = 0.05 \cdot \\|\underline{\mathbf{L}}\\|_{\text{F}} / \sqrt{d_1 d_2 d_3}$. Results on Salinas A are as follows:

Table C. Salinas A under uniform noise

These results indicate strong resilience to mild non-Gaussian noise.

We emphasize, however, that noise modeling is application-specific. Extending our framework to settings with impulsive (e.g., Laplacian) or signal-dependent (e.g., Poisson) noise would require modifying the loss function (e.g., replacing $\ell_2$ with $\ell_1$ or KL divergence) and incorporating robust optimization strategies, as in prior works [R1, R2]. These extensions represent promising future directions beyond the scope of this work.

[R1] Lu, C. et al. Tensor robust principal component analysis with a new tensor nuclear norm. IEEE TPAMI, 2019.

[R2] Zhang, X. et al. Low-rank tensor completion with Poisson observations. IEEE TPAMI, 2021.

Concern 3: Convergence behavior of the ADMM-based algorithm

Response: We thank the reviewer for the observation regarding the convergence behavior. While the proposed optimization problem is nonconvex due to the reweighted quasi-norm, we observe consistent and stable empirical performance across all datasets. As shown in Appendix D.4, Figure 4, the objective value decreases monotonically, and the PSNR stabilizes within a modest number of iterations.

Each ADMM subproblem admits a closed-form or efficiently solvable update, and the reweighting procedure is applied in a controlled manner, which we believe contributes to the observed stability. Although a formal convergence guarantee is not currently established—as is common in nonconvex reweighted optimization frameworks—our empirical evidence supports the practical reliability of the proposed algorithm.

A more rigorous theoretical analysis of the convergence behavior under the proposed reweighted dual spectral structure is a promising direction for future research.