  It is challenging to recover the large-scale internet traffic data purely
from the link measurements. With the rapid growth of the problem scale, it will
be extremely difficult to sustain the recovery accuracy and the computational
cost. In this work, we propose a new Sparsity Low-Rank Recovery (SLRR) model
and its Schur Complement Based semi-proximal Alternating Direction Method of
Multipliers (SCB-spADMM) solver. Our approach distinguishes itself mainly for
the following two aspects. First, we fully exploit the spatial low-rank
property and the sparsity of traffic data, which are barely considered in the
literature. Our model can be divided into a series of subproblems, which only
relate to the traffics in a certain individual time interval. Thus, the model
scale is significantly reduced. Second, we establish a globally convergent
ADMM-type algorithm inspired by [Li et al., Math. Program., 155(2016)] to solve
the SLRR model. In each iteration, all the intermediate variables' optimums can
be calculated analytically, which makes the algorithm fast and accurate.
Besides, due to the separability of the SLRR model, it is possible to design a
parallel algorithm to further reduce computational time. According to the
numerical results on the classic datasets Abilene and GEANT, our method
achieves the best accuracy with a low computational cost. Moreover, in our
newly released large-scale Huawei Origin-Destination (HOD) network traffics,
our method perfectly reaches the seconds-level feedback, which meets the
essential requirement for practical scenarios.
