In this paper, we develop a novel alternating linearization method for solving convex minimization whose objective function is the sum of two separable functions. The motivation of the paper is to extend the recent wo...In this paper, we develop a novel alternating linearization method for solving convex minimization whose objective function is the sum of two separable functions. The motivation of the paper is to extend the recent work Goldfarb et al.(2013) to cope with more generic convex minimization. For the proposed method,both the separable objective functions and the auxiliary penalty terms are linearized. Provided that the separable objective functions belong to C1,1(Rn), we prove the O(1/?) arithmetical complexity of the new method. Some preliminary numerical simulations involving image processing and compressive sensing are conducted.展开更多
We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary dimensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve th...We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary dimensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve the known exponents. We also show some applications of our results: (i) we decrease from O(n 2 + n 1+o(1)logq) to O(n 1.9998 + n 1+o(1)logq) the known arithmetic complexity bound for the univariate polynomial factorization of degree n over a finite field with q elements; (ii) we decrease from 2.837 to 2.7945 the known exponent of the work and arithmetic processor bounds for fast deterministic (NC) parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n × n matrix, as well as for the solution to a nonsingular linear system of n equations; (iii) we decrease from O(m 1.575 n) to O(m 1.5356 n) the known bound for computing basic solutions to a linear programming problem with m constraints and n variables.展开更多
基金supported by National Natural Science Foundation of China(Grant Nos.11301055 and 11401315)Natural Science Foundation of Jiangsu Province(Grant No.BK2009397)the Fundamental Research Funds for the Central Universities(Grant No.ZYGX2013J103)
文摘In this paper, we develop a novel alternating linearization method for solving convex minimization whose objective function is the sum of two separable functions. The motivation of the paper is to extend the recent work Goldfarb et al.(2013) to cope with more generic convex minimization. For the proposed method,both the separable objective functions and the auxiliary penalty terms are linearized. Provided that the separable objective functions belong to C1,1(Rn), we prove the O(1/?) arithmetical complexity of the new method. Some preliminary numerical simulations involving image processing and compressive sensing are conducted.
文摘We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary dimensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve the known exponents. We also show some applications of our results: (i) we decrease from O(n 2 + n 1+o(1)logq) to O(n 1.9998 + n 1+o(1)logq) the known arithmetic complexity bound for the univariate polynomial factorization of degree n over a finite field with q elements; (ii) we decrease from 2.837 to 2.7945 the known exponent of the work and arithmetic processor bounds for fast deterministic (NC) parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n × n matrix, as well as for the solution to a nonsingular linear system of n equations; (iii) we decrease from O(m 1.575 n) to O(m 1.5356 n) the known bound for computing basic solutions to a linear programming problem with m constraints and n variables.
