Linear programming (LP) is an extremely useful tool which has been successfully applied to solve various problems in a wide range of areas, including operations research, engineering, economics, or even more abstract ...
详细信息
Linear programming (LP) is an extremely useful tool which has been successfully applied to solve various problems in a wide range of areas, including operations research, engineering, economics, or even more abstract mathematical areas such as combinatorics. It is also used in many machine learning applications, such as ℓ1-regularized SVMs, basis pursuit, nonnegative matrix factorization, etc. Interior Point Methods (IPMs) are one of the most popular methods to solve LPs both in theory and in practice. Their underlying complexity is dominated by the cost of solving a system of linear equations at each iteration. In this paper, we consider both feasible and infeasible IPMs for the special case where the number of variables is much larger than the number of constraints. Using tools from Randomized Linear algebra, we present a preconditioning technique that, when combined with the iterative solvers such as Conjugate Gradient or Chebyshev Iteration, provably guarantees that IPM algorithms (suitably modified to account for the error incurred by the approximate solver), converge to a feasible, approximately optimal solution, without increasing their iteration complexity. Our empirical evaluations verify our theoretical results on both real-world and synthetic data.
A 4 × 4 invertible circulant matrix on GF(28) can represent the Mixcolumn operation of AES, which plays an important role as a confusion operation. Starting from the analysis of the Mixcolumns operation of AES, w...
详细信息
Let (K, nu) be a valued field, where nu is a rank-one discrete valuation, with valuation ring R. The goal of this paper is to investigate some basic concepts of Newton polygon techniques of a monic polynomial f (x) is...
详细信息
Let (K, nu) be a valued field, where nu is a rank-one discrete valuation, with valuation ring R. The goal of this paper is to investigate some basic concepts of Newton polygon techniques of a monic polynomial f (x) is an element of R[x];namely, theorem of the product, of the polygon, and of the residual polynomial, in such way that improves that given in [D. Cohen, A. Movahhedi and A. Salinier, Factorization over local fields and the irreducibility of generalized difference polynomials, Mathematika 47 (2000) 173-196] and generalizes that given in [J. Guardia, J. Montes and E. Nart, Newton polygons of higher order in algebraic numbertheory, Trans. Amer. Math. Soc. 384(1) (2012) 361-416] to any rank-one valued field.
Many computer vision applications require robust and efficient estimation of camera geometry from a minimal number of input data measurements, i.e., solving minimal problems in a RANSAC framework. Minimal problems are...
详细信息
The main goal behind mathematical cryptography is to keep messages and multimedia messages secret at a time when modern means of communication have spread and become very diverse. Fuzzy matrices as strong tools which ...
详细信息
Many cyber-attach schemes and coding models established by algebra tools are build to address the problem of security of cyber-pysical systems (CPS). As an important field of algebra computing, Boolean Polynomial Syst...
详细信息
Recently 3D image processing has interested researchers in both theoretical and applied fields and thus has constituted a challenging subject. Theoretically, this needs suitable functional bases that are easy to imple...
详细信息
Recently 3D image processing has interested researchers in both theoretical and applied fields and thus has constituted a challenging subject. Theoretically, this needs suitable functional bases that are easy to implement by the next. It holds that Clifford wavelets are main tools to achieve this necessity. In the present paper we intend to develop some new classes of Clifford wavelet functions. Some classes of new monogenic polynomials are developed firstly from monogenic extensions of 2-parameters Clifford weights. Such classes englobe the well known Jacobi, Gegenbauer and Hermite ones. The constructed polynomials are next applied to develop new Clifford wavelets. Reconstruction and Fourier-Plancherel formulae have been proved. Finally, computational examples are developed provided with graphical illustrations of the Clifford mother wavelets in some cases. Some graphical illustrations of the constructed wavelets have been provided and finally concrete applications in biofields have been developed dealing with EEG/ECG and Brain image processing.
We establish a new perturbation theory for orthogonal polynomials using a Riemann–Hilbert approach and consider applications in numerical linear algebra and random matrix theory. This new approach shows that the orth...
详细信息
MSC Codes 11G30, 11G50, 14G05, 14G25We prove the Relative Manin–Mumford Conjecture for families of abelian varieties in characteristic 0. We follow the Pila–Zannier method to study special point problems, and we use...
In this paper, we consider roots of multivariate polynomials over a finite grid. When given information on the leading monomial with respect to a fixed monomial ordering, the footprint bound [Footprints or generalized...
详细信息
In this paper, we consider roots of multivariate polynomials over a finite grid. When given information on the leading monomial with respect to a fixed monomial ordering, the footprint bound [Footprints or generalized Bezout's theorem, IEEE Trans. Inform. theory 46(2) (2000) 635-641, On (or in) Dick Blahut's 'footprint', Codes, Curves Signals (1998) 3-9] provides us with an upper bound on the number of roots, and this bound is sharp in that it can always be attained by trivial polynomials being a constant times a product of an appropriate combination of terms consisting of a variable minus a constant. In contrast to the one variable case, there are multivariate polynomials attaining the footprint bound being not of the above form. This even includes irreducible polynomials. The purpose of the paper is to determine a large class of polynomials for which only the mentioned trivial polynomials can attain the bound, implying that to search for other polynomials with the maximal number of roots one must look outside this class.
暂无评论