For a nonnegative irreducible tensor, we give distribution properties of its eigenvalues. In particular, the spectral radius of a nonnegative irreducible tensor with positive trace is proved to be the unique eigenvalue on the spectral circle. Unlike the matrix setting, we give an example to present that this type of tensor is not always primitive. Thus, for a nonnegative irreducible tensor, the primitivity is a sufficient condition only for the spectral radius to be the unique eigenvalue on the spectral circle. Also, the stochastic tensor is defined, and we show that every nonnegative irreducible tensor with unit spectral radius is diagonally similar to a certain irreducible stochastic tensor. Based on this result, the minimax theorem for tensors is proved by using an alternative approach. Further, with the help of the minimax theorem, we illustrate that the problem of finding the spectral radius (largest singular value) of a nonnegative irreducible square (rectangular) tensor can be converted into a conv...
20 August 2015 in IEEE Transactions on Neural Networks and Learning Systems
This paper addresses the robust low-rank tensor recovery problems. Tensor recovery aims at reconstructing a low-rank tensor from some linear measurements, which finds applications in image processing, pattern recognition, multitask learning, and so on. In real-world applications, data might be contaminated by sparse gross errors. However, the existing approaches may not be very robust to outliers. To resolve this problem, this paper proposes approaches based on the regularized redescending M-estimators, which have been introduced in robust statistics. The robustness of the proposed approaches is achieved by the regularized redescending M-estimators. However, the nonconvexity also leads to a computational difficulty. To handle this problem, we develop algorithms based on proximal and linearized block coordinate descent methods. By explicitly deriving the Lipschitz constant of the gradient of the data-fitting risk, the descent property of the algorithms is present. Moreover, we verify that the objective functions of the proposed approaches satisfy the Kurdyka-Łojasiewicz property, which establishes the global convergence of the algorithms. The numerical experiments on synthetic data as well as real data verify that our approaches are robust in the presence of outliers and still effective in the absence of outliers.
This letter addresses the robustness problem when learning a large margin classifier in the presence of label noise. In our study, we achieve this purpose by proposing robustified large margin support vector machines. The robustness of the proposed robust support vector classifiers (RSVC), which is interpreted from a weighted viewpoint in this work, is due to the use of nonconvex classification losses. Besides the robustness, we also show that the proposed RSCV is simultaneously smooth, which again benefits from using smooth classification losses. The idea of proposing RSVC comes from M-estimation in statistics since the proposed robust and smooth classification losses can be taken as one-sided cost functions in robust statistics. Its Fisher consistency property and generalization ability are also investigated. Besides the robustness and smoothness, another nice property of RSVC lies in the fact that its solution can be obtained by solving weighted squared hinge loss–based support vector machine problems iteratively. We further show that in each iteration, it is a quadratic programming problem in its dual space and can be solved by using state-of-the-art methods. We thus propose an iteratively reweighted type algorithm and provide a constructive proof of its convergence to a stationary point. Effectiveness of the proposed classifiers is verified on both artificial and real data sets.
In this letter, we propose a rank-one tensor updating algorithm for solving tensor completion problems. Unlike the existing methods which penalize the tensor by using the sum of nuclear norms of unfolding matrices, our optimization model directly employs the tensor nuclear norm which is studied recently. Under the framework of the conditional gradient method, we show that at each iteration, solving the proposed model amounts to computing the tensor spectral norm and the related rank-one tensor. Because the problem of finding the related rank-one tensor is NP-hard, we propose a subroutine to solve it approximately, which is of low computational complexity. Experimental results on real datasets show that our algorithm is efficient and effective.
19 February 2011 in Frontiers of Mathematics in China
This paper studies models and algorithms for a class of tensor optimization problems, based on a rank-1 equivalence property between a tensor and certain unfoldings. It is first shown that in $d$th order tensor space, the set of rank-1 tensors is the same as the intersection of $\lceil \log_2(d) \rceil$ tensor sets, of which tensors have a specific rank-1 balanced unfolding matrix. Moreover, the number $\lceil \log_2(d) \rceil$ is proved to be optimal in some sense. Based on the above equivalence property, three relaxation approaches for solving the best rank-1 tensor approximation problems are proposed, including two convex relaxations and a nonconvex one. The two convex relaxations utilize the matrix nuclear norm regularization/constraints. They have the advantage of identifying whether the solution is a global optimizer of the original problem, by computing the nuclear norm or the Frobenius norm of a certain matrix. Under certain assumptions, the optimal solution of the original problem is characterize...