pith. sign in

arxiv: 1907.04092 · v1 · pith:GJJY4HGWnew · submitted 2019-07-09 · 💻 cs.LG · stat.ML

Tensor p-shrinkage nuclear norm for low-rank tensor completion

Chunsheng Liu , Hong Shan , Chunlei Chen This is my paper

Pith reviewed 2026-05-25 00:25 UTC · model grok-4.3

classification 💻 cs.LG stat.ML
keywords tensor p-shrinkage nuclear normlow-rank tensor completiontensor singular value decompositionnonconvex optimizationrecovery error boundadaptive momentum algorithm
0
0 comments X

The pith

When p is less than one, the tensor p-shrinkage nuclear norm approximates the tensor average rank more closely than the tensor nuclear norm.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proposes a tensor p-shrinkage nuclear norm defined via tensor singular value decomposition. It establishes that this norm approximates the tensor average rank more closely than the ordinary tensor nuclear norm when the power p is below one. The norm is then used to build a model for recovering a tensor from partial observations, together with an upper bound on the recovery error. An algorithm with adaptive momentum solves the resulting nonconvex problem and is shown to converge globally under a smoothness condition. Tests on both synthetic data and real-world examples indicate the new norm produces more accurate completions than prior approaches.

Core claim

The tensor p-shrinkage nuclear norm with p less than 1 is a better approximation of the tensor average rank than the tensor nuclear norm. By employing the p-shrinkage nuclear norm, a novel low-rank tensor completion model is proposed to estimate a tensor from its partial observations. Statistically, the upper bound of recovery error is provided for the LRTC model. An efficient algorithm accelerated by the adaptive momentum scheme is developed to solve the resulting nonconvex optimization problem, and it enjoys a global convergence rate under the smoothness assumption.

What carries the argument

The p-shrinkage nuclear norm formed by raising the singular values from the tensor singular value decomposition to a power p less than one before summation.

If this is right

  • The p-TNN supplies a tighter proxy for tensor average rank in completion problems.
  • An explicit upper bound holds for the error of the resulting low-rank tensor completion model.
  • The momentum-accelerated algorithm reaches global convergence at a stated rate under smoothness.
  • Empirical results on synthetic and real data sets show lower completion error than several existing methods.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same shrinkage construction could be tried on other tensor decompositions to check whether rank approximation improves similarly.
  • An adaptive schedule for p inside the algorithm might trade off approximation tightness against speed in practice.
  • The recovery bound might be tightened further if the tensor is known to obey additional structural constraints such as nonnegativity.

Load-bearing premise

The tensor singular value decomposition and the chosen shrinkage function must produce a quantity that is provably closer to the tensor average rank when p is below one.

What would settle it

A tensor for which the p-TNN value at some p less than 1 lies farther from the average rank than the ordinary tensor nuclear norm does, or a completion experiment in which the observed error exceeds the derived upper bound.

Figures

Figures reproduced from arXiv: 1907.04092 by Chunlei Chen, Chunsheng Liu, Hong Shan.

Figure 1
Figure 1. Figure 1: Several p-shrinkage functions with different p values. Without loss of generality, the µ is fixed at 1. The smaller the p value, the less penalty for large inputs. for large inputs. However, hard thresholding is discontinuous. Moreover, when −∞ < p < 1, the p-shrinkage function satisfies the property that the larger the input, the less penalized it should be. 3 Model In this section, we propose a new defin… view at source ↗
Figure 2
Figure 2. Figure 2: Performance of the proposed method with different selec [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Performance of the proposed method on the synthetic d [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Performance of our method with varying tubal rank and s [PITH_FULL_IMAGE:figures/full_fig_p016_4.png] view at source ↗
read the original abstract

In this paper, a new definition of tensor p-shrinkage nuclear norm (p-TNN) is proposed based on tensor singular value decomposition (t-SVD). In particular, it can be proved that p-TNN is a better approximation of the tensor average rank than the tensor nuclear norm when p < 1. Therefore, by employing the p-shrinkage nuclear norm, a novel low-rank tensor completion (LRTC) model is proposed to estimate a tensor from its partial observations. Statistically, the upper bound of recovery error is provided for the LRTC model. Furthermore, an efficient algorithm, accelerated by the adaptive momentum scheme, is developed to solve the resulting nonconvex optimization problem. It can be further guaranteed that the algorithm enjoys a global convergence rate under the smoothness assumption. Numerical experiments conducted on both synthetic and real-world data sets verify our results and demonstrate the superiority of our p-TNN in LRTC problems over several state-of-the-art methods.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The manuscript defines a tensor p-shrinkage nuclear norm (p-TNN) via t-SVD, asserts that it is a strictly better approximation to tensor average rank than the standard tensor nuclear norm when p < 1, formulates a low-rank tensor completion model using this norm, supplies a statistical upper bound on recovery error, develops an accelerated proximal algorithm with adaptive momentum that is shown to converge globally under a smoothness assumption, and reports numerical superiority on synthetic and real-world data.

Significance. If the approximation property and error bound are rigorously established, the work supplies a non-convex surrogate that can tighten recovery guarantees relative to convex TNN relaxations while retaining an efficient algorithm; the global convergence result and reproducible experiments constitute concrete strengths.

major comments (3)
  1. [Abstract, paragraph 2; approximation theorem section] Abstract (paragraph 2) and the section containing the approximation theorem: the claim that p-TNN is a better approximation to tensor average rank for p < 1 is asserted without exhibiting the explicit inequality relating the p-shrinkage operator to the count of non-zero singular tubes; the manuscript must supply the full derivation, including the precise definition of tensor average rank in the t-SVD basis and verification that the inequality holds for arbitrary singular-value distributions.
  2. [Recovery error bound paragraph] The recovery-error-bound paragraph: the upper bound is stated but the assumptions on the observation model, the choice of p, and any data-exclusion criteria are not listed; without these the bound cannot be checked for validity or compared with existing TNN bounds.
  3. [Algorithm and convergence section] Algorithm section (convergence theorem): the global convergence rate is claimed under a smoothness assumption, yet the precise Lipschitz constant or step-size schedule that guarantees the rate is not derived or referenced to a specific equation.
minor comments (2)
  1. [Definition of p-TNN] Notation for the p-shrinkage function should be introduced once with an explicit formula rather than repeated descriptively.
  2. [Numerical experiments] Figure captions for the synthetic experiments should state the exact values of p, rank, and sampling ratio used in each panel.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive comments. We address each major point below and will incorporate the requested clarifications into the revised manuscript.

read point-by-point responses

  1. Referee: [Abstract, paragraph 2; approximation theorem section] Abstract (paragraph 2) and the section containing the approximation theorem: the claim that p-TNN is a better approximation to tensor average rank for p < 1 is asserted without exhibiting the explicit inequality relating the p-shrinkage operator to the count of non-zero singular tubes; the manuscript must supply the full derivation, including the precise definition of tensor average rank in the t-SVD basis and verification that the inequality holds for arbitrary singular-value distributions.

    Authors: We agree that the approximation property requires a more explicit derivation. In the revised manuscript we will insert the full proof, beginning from the definition of tensor average rank as the number of nonzero singular tubes under t-SVD, deriving the inequality that relates the p-shrinkage operator to this count, and verifying the strict improvement for p < 1 over arbitrary singular-value distributions. revision: yes

  2. Referee: [Recovery error bound paragraph] The recovery-error-bound paragraph: the upper bound is stated but the assumptions on the observation model, the choice of p, and any data-exclusion criteria are not listed; without these the bound cannot be checked for validity or compared with existing TNN bounds.

    Authors: We will expand the recovery-error-bound paragraph to state explicitly the observation model (uniform random sampling of entries), the admissible interval for p, and any data-exclusion conditions. These additions will enable direct verification and comparison with existing TNN recovery bounds. revision: yes

  3. Referee: [Algorithm and convergence section] Algorithm section (convergence theorem): the global convergence rate is claimed under a smoothness assumption, yet the precise Lipschitz constant or step-size schedule that guarantees the rate is not derived or referenced to a specific equation.

    Authors: We will augment the convergence theorem with an explicit derivation (or direct reference to the relevant equation) of the Lipschitz constant of the smooth part of the objective together with the precise step-size schedule employed by the adaptive momentum scheme, thereby justifying the claimed global convergence rate. revision: yes

Circularity Check

0 steps flagged

No circularity: p-TNN defined independently; approximation claim is a separate mathematical proof on t-SVD singular values.

full rationale

The paper introduces p-TNN as a new definition based on t-SVD and the p-shrinkage operator, then separately claims a proof that this yields a better approximation to tensor average rank for p<1. No quoted equation or step reduces the claimed approximation, recovery bound, or algorithm convergence to a quantity that is fitted from the same model or defined in terms of the target result. The derivation chain remains self-contained because the proof relies on algebraic properties of the chosen shrinkage function applied to the t-SVD spectrum (external to any fitted values in the LRTC model), and the algorithm is derived from standard nonconvex optimization techniques. This matches the default case of an independent definition plus a non-tautological proof.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The central claim rests on the t-SVD framework (standard in the field) and the introduction of a tunable shrinkage exponent p; no new entities are postulated.

free parameters (1)
  • p
    Shrinkage exponent chosen less than 1; value is a modeling choice that must be selected or tuned.
axioms (1)
  • standard math Tensor singular value decomposition exists and satisfies the algebraic properties used to define the p-shrinkage operator.
    Invoked in the definition of p-TNN (abstract, sentence 1).

pith-pipeline@v0.9.0 · 5692 in / 1237 out tokens · 24422 ms · 2026-05-25T00:25:16.593852+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages · 1 internal anchor

  1. [1]

    J. Liu, P. Musialski, P. Wonka, J. Ye, Tensor completion for estima ting missing values in visual data, IEEE Trans. Pattern Anal. Mach. Inte ll. 35 (1) (2013) 208220

    work page 2013

  2. [2]

    M. E. Kilmer, K. Braman, N. Hao, and R. C. Hoover, Third-order t ensors as operators on matrices: A theoretical and computational fram ework with applications in imaging, SIAM Journal on Matrix Analysis and Applica- tions, vol. 34, no. 1, pp. 148172, 2013

    work page 2013

  3. [3]

    Y. Wang, J. Peng, Q. Zhao, Y. Leung, X.L. Zhao, D. Meng, Hyper spectral image restoration via total variation regularized low-rank tensor d ecom- position, IEEE J. Sel. Top. Appl. Earth Obs. Remote Sens. 11 (4) (2 018) 12271243

    work page

  4. [4]

    Zhen Long, Yipeng Liu, Longxi Chen, Ce Zhu, low-rank Tensor Completion for Multiway Visual Data, Signal Processing (2018), doi: https://doi.org/10.1016/j.sigpro.2018.09.039

    work page doi:10.1016/j.sigpro.2018.09.039 2018

  5. [5]

    Z. Lai , Y. Xu , Q. Chen , J. Yang , D. Zhang , Multilinear sparse prin cipal component analysis, IEEE Trans. Neural Netw. 25 (10) (2014) 19 421950

    work page 2014

  6. [6]

    Tensor Robust Principal Component Analysis with A New Tensor Nuclear Norm

    Lu, C., Feng, J., Chen, Y., Liu, W., Lin, Z., Yan, S.. Tensor Robust Principal Component Analysis with A New Tensor Nuclear Norm, arXiv: 1804.03728 (2018)

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  7. [7]

    Cichocki , D

    A. Cichocki , D. Mandic , L. De Lathauwer , G. Zhou , Q. Zhao , C. C aiafa , H.A. Phan , Tensor decompositions for signal processing application s: from two-way to multiway component analysis, IEEE Signal Process. Mag . 32 (2) (2015) 145163

    work page 2015

  8. [8]

    Cong, Q.-H

    F. Cong, Q.-H. Lin, L.-D. Kuang, X.-F. Gong, P. Astikainen, T. Rist aniemi, Tensor decomposition of EEG signals: a brief review, Journal of Neu ro- science Methods 248 (2015) 5969

    work page 2015

  9. [9]

    Z. Lai , Y. Xu , J. Yang , J. Tang , D. Zhang , Sparse tensor discr iminant analysis, IEEE Trans. Image Process. 22 (10) (2013) 39043915

    work page 2013

  10. [10]

    Cande` s , T

    E.J. Cande` s , T. Tao , The power of convex relaxation: near-o ptimal matrix completion, IEEE Trans. Inf. Theory 56 (5) (2010) 20532080

    work page 2010

  11. [11]

    T. G. Kolda and B. W. Bader, Tensor decompositions and applicat ions, SIAM review, vol. 51, no. 3, pp. 455500, 2009

    work page 2009

  12. [12]

    J. B. Kruskal, Rank, decomposition, and uniqueness for 3-way and n-way arrays. North-Holland Publishing Co., 1989

    work page 1989

  13. [13]

    L. R. Tucker, Some mathematical notes on three-mode facto r analysis, Psychometrika, vol. 31, no. 3, pp. 279311, 1966. 20

    work page 1966

  14. [14]

    F. L. Hitchcock, The expression of a tensor or a polyadic as a su m of products, Studies in Applied Mathematics, vol. 6, no. 1-4, pp. 1641 89, 1927

    work page 1927

  15. [15]

    H. A. Kiers, Towards a standardized notation and terminology in multiway analysis, Journal of Chemometrics, vol. 14, no. 3, pp. 105122,200 0

    work page

  16. [16]

    I. V. Oseledets, Tensor-train decomposition, SIAM J. Sci. Com put., vol. 33, no. 5, pp. 22952317, Jan. 2011

    work page 2011

  17. [17]

    M. E. Kilmer and C. D. Martin, Factorization strategies for third -order tensors, Linear Algebra and its Applications, vol. 435, no. 3, pp. 64 1 658, 2011

    work page 2011

  18. [18]

    Friedland and L.-H

    S. Friedland and L.-H. Lim, Nuclear norm of higher-order tensor s, Mathe- matics of Computation, vol. 87, no. 311, pp. 12551281, 2018

    work page 2018

  19. [19]

    Yuning Yang, Yunlong Feng, and Johan A. K. Suykens A Rank-On e Tensor Updating Algorithm for Tensor Completion. IEEE SIGNAL PROCESSIN G LETTERS, VOL. 22, NO. 10, OCTOBER 2015 1633

    work page 2015

  20. [20]

    Yuan and C.-H

    M. Yuan and C.-H. Zhang, On tensor completion via nuclear norm minimization, Foundations ofComputational Mathematics, 16(4) (2 016) 10311068

    work page

  21. [21]

    C. J. Hillar and L.-H. Lim, Most tensor problems are NP-hard, J. A CM,vol. 60, no. 6, 2013, Art. no. 45

    work page 2013

  22. [22]

    Gandy, B

    S. Gandy, B. Recht, I. Yamada, Tensor completion and low-n-r ank tensor recovery via convex optimization, Inverse Problems 27 (2) (2011) 119

    work page 2011

  23. [23]

    Marco Signoretto, Quoc Tran Dinh, Lieven De Lathauwer, and J ohan A. K. Suykens. 2014. Learning with tensors: A framework based on c onvex optimization and spectral regularization. Machine Learning 94, 3 (2 014), 303351

    work page 2014

  24. [24]

    Kasai and B

    H. Kasai and B. Mishra, Low-rank tensor completion: a Riemann ian man- ifold preconditioning approach, in International Conference on Ma chine Learning, pp. 10121021, 2016

    work page 2016

  25. [25]

    Chen, C.-T

    Y.-L. Chen, C.-T. Hsu, and H.-Y. M. Liao, Simultaneous tensor de compo- sition and completion using factor priors, IEEE Transactions on Pat tern Analysis and Machine Intelligence, vol. 36, no. 3, pp. 577591, 2014

    work page 2014

  26. [26]

    A., Phien, H

    Bengua, J. A., Phien, H. N., Tuan, H. D., Do, M. N. (2017). Efficien t Tensor Completion for Color Image and Video Recovery: Low-Rank Tensor T rain. IEEE Transactions on Image Processing, 26(5), 24662479

    work page 2017

  27. [27]

    Imaizumi, M., Maehara, T., Hayashi, K. (2017). On Tensor Train R ank Minimization: Statistical Efficiency and Scalable Algorithm. (Nips 2017) . 21

    work page 2017

  28. [28]

    Zhang, G

    Z. Zhang, G. Ely, S. Aeron, N. Hao, and M. Kilmer, Novel method s for mul- tilinear data completion and de-noising based on tensor-SVD, in Proc eed- ings of the IEEE Conference on Computer Vision and Pattern Recog nition, pp. 38423849, 2014

    work page 2014

  29. [29]

    Zhang, and S

    Z. Zhang, and S. Aeron. Exact tensor completion using t-SVD. IEEE Trans- actions on Signal Processing, 65(6): 1511-1526, 2017

    work page 2017

  30. [30]

    P. Zhou, C. Lu, Z. Lin, and C. Zhang, Tensor factorization for low-rank tensor completion, IEEE Transactions on Image Processing, vol. 2 7, no. 3, pp. 11521163, 2018

    work page 2018

  31. [31]

    Kong, H., Xie, X., Lin, Z. (2018). t-Schatten- p Norm for Low-Rank Tensor Recovery. IEEE Journal of Selected Topics in Signal Processing, 1 2(6), 14051419. https://doi.org/10.1109/jstsp.2018.2879185

    work page doi:10.1109/jstsp.2018.2879185 2018

  32. [32]

    Voronin and R

    S. Voronin and R. Chartrand. A new generalized thresholding alg orithm for inverse problems with sparsity constraints. In IEEE Internat ional Con- ference on Acoustics, Speech and Signal Processing (ICASSP), 1 636-1640, 2013

    work page 2013

  33. [33]

    C. Lu, J. Feng, Y. Chen, W. Liu, Z. Lin, and S. Yan, Tensor robu st princi- pal component analysis: Exact recovery of corrupted low-rank t ensors via convex optimization, in Proceedings of the IEEE Conference on Com puter Vision and Pattern Recognition, pp. 52495257, 2016

    work page 2016

  34. [34]

    Wang, A., Lai, Z., Jin, Z. (2019). Noisy low-tubal- rank tensor completion. Neurocomputing, 330, 267279. https://doi.org/10.1016/j.neucom.2018.11.012

    work page doi:10.1016/j.neucom.2018.11.012 2019

  35. [35]

    Adaptive subgradient metho ds for online learning and stochastic optimization

    Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient metho ds for online learning and stochastic optimization. JMLR, 12(Jul):21212159 , 2011

    work page 2011

  36. [36]

    Convergence analys is of proximal gradient with momentum for nonconvex optimization

    Li, Q., Zhou, Y., Liang, Y., and Varshney, P. Convergence analys is of proximal gradient with momentum for nonconvex optimization. In IC ML, pp. 21112119, 2017

    work page 2017

  37. [37]

    Q. Yao, J. Kwok, B. Han. Efficient Nonconvex Regularized Tenso r Com- pletion with Structure-aware Proximal Iterations. Internationa l Conference on Machine Learning (ICML). 2019

    work page 2019

  38. [38]

    T., Wang, T

    yao, quanming, Kwok, J. T., Wang, T. F., Liu, T. Y. (2018). Larg e- Scale Low-Rank Matrix Learning with Nonconvex Regularizers. IEEE Transactions on Pattern Analysis and Machine Intelligence, 8828(c ), 116. https://doi.org/10.1109/TPAMI.2018.2858249

    work page doi:10.1109/tpami.2018.2858249 2018

  39. [39]

    Field-of-Experts Filters Guided Tensor Completion

    Biao Xiong ; Qiegen Liu ; Jiaojiao Xiong ; Sanqian Li ; Shanshan Wang ; Dong Liang. Field-of-Experts Filters Guided Tensor Completion. IE EE Transactions on Multimedia. 20(9) (2018), 2316-2329. 22

    work page 2018

  40. [40]

    Smooth PARAF A C De- composition for Tensor Completion, IEEE Transactions on Signal Pr ocess- ing, 64(20) (2016), 5423-5436

    Tatsuya Yokota ; Qibin Zhao ; Andrzej Cichocki. Smooth PARAF A C De- composition for Tensor Completion, IEEE Transactions on Signal Pr ocess- ing, 64(20) (2016), 5423-5436

    work page 2016

  41. [41]

    Klopp et al., Noisy low-rank matrix completion with general samp ling distribution, Bernoulli, vol

    O. Klopp et al., Noisy low-rank matrix completion with general samp ling distribution, Bernoulli, vol. 20, no. 1, pp. 282303, 2014. 23

    work page 2014