  This study aims to solve the over-reliance on the rank estimation strategy in
the standard tensor factorization-based tensor recovery and the problem of a
large computational cost in the standard t-SVD-based tensor recovery. To this
end, we proposes a new tensor norm with a dual low-rank constraint, which
utilizes the low-rank prior and rank information at the same time. In the
proposed tensor norm, a series of surrogate functions of the tensor tubal rank
can be used to achieve better performance in harness low-rankness within tensor
data. It is proven theoretically that the resulting tensor completion model can
effectively avoid performance degradation caused by inaccurate rank estimation.
Meanwhile, attributed to the proposed dual low-rank constraint, the t-SVD of a
smaller tensor instead of the original big one is computed by using a sample
trick. Based on this, the total cost at each iteration of the optimization
algorithm is reduced to $\mathcal{O}(n^3\log n +kn^3)$ from $\mathcal{O}(n^4)$
achieved with standard methods, where $k$ is the estimation of the true tensor
rank and far less than $n$. Our method was evaluated on synthetic and
real-world data, and it demonstrated superior performance and efficiency over
several existing state-of-the-art tensor completion methods.
