A randomized algorithm for the decomposition of matrices

Given an $m\times n$ matrix A and a positive integer k, we describe a randomized procedure for the approximation of A with a matrix Z of rank k. The procedure relies on applying $A^{\mathrm{T}}$ to a collection of l random vectors, where l is an integer equal to or slightly greater than k; the scheme is efficient whenever A and $A^{\mathrm{T}}$ can be applied rapidly to arbitrary vectors. The discrepancy between A and Z is of the same order as $\sqrt{lm}$ times the $(k+1)$st greatest singular value ${\sigma }_{k+1}$ of A, with negligible probability of even moderately large deviations. The actual estimates derived in the paper are fairly complicated, but are simpler when $l?k$ is a fixed small nonnegative integer. For example, according to one of our estimates for $l?k=20$, the probability that the spectral norm $6A?Z6$ is greater than $10\sqrt{(k+20)m}{\sigma }_{k+1}$ is less than ${10}^{?17}$. The paper contains a number of estimates for $6A?Z6$, including several that are stronger (but more detailed) than the preceding example; some of the estimates are effectively independent of m. Thus, given a matrix A of limited numerical rank, such that both A and $A^{\mathrm{T}}$ can be applied rapidly to arbitrary vectors, the scheme provides a simple, efficient means for constructing an accurate approximation to a singular value decomposition of A. Furthermore, the algorithm presented here operates reliably independently of the structure of the matrix A. The results are illustrated via several numerical examples.     

New algorithms for convex cost tension problem with application to computer vision

Motivated by various applications to computer vision, we consider the convex cost tension problem, which is the dual of the convex cost flow problem. In this paper, we first propose a primal algorithm for computing an optimal solution of the problem. Our primal algorithm iteratively updates primal variables by solving associated minimum cut problems. We show that the time complexity of the primal algorithm is $O(K?T(n,m))$, where $K$ is the range of primal variables and $T(n,m)$ is the time needed to compute a minimum cut in a graph with $n$ nodes and $m$ edges. We then develop an improved version of the primal algorithm, called the primal–dual algorithm, by making good use of dual variables in addition to primal variables. Although its time complexity is the same as that of the primal algorithm, we can expect a better performance in practice. We finally consider an application to a computer vision problem called the panoramic image stitching.     

The adversary degree-associated reconstruction number of double-brooms

A vertex-deleted subgraph of a graph G is a card. A dacard specifies the degree of the deleted vertex along with the card. The adversary degree-associated reconstruction number $\mathrm{adrn}(G)$ is the least k such that every set of k dacards determines G. We determine $\mathrm{adrn}(D_{m,n,p})$, where the double-broom $D_{m,n,p}$ with $p\ge 2$ is the tree with $m+n+p$ vertices obtained from a path with p vertices by appending m leaves at one end and n leaves at the other end. We determine $\mathrm{adrn}(D_{m,n,p})$ for all $m,n,p$. For $2\le m\le n$, usually $\mathrm{adrn}(D_{m,n,p})=m+2$, except $\mathrm{adrn}(D_{m,m+1,p})=m+1$ and $\mathrm{adrn}(D_{m,m+2,p})=m+3$. There are exceptions when $(m,n)=(2,3)$ or $p=4$. For $m=1$ the usual value is 4, with exceptions when $p\in \{2,3\}$ or $n=2$.     

Lower bounds for the Hilbert number of polynomial systems

Let $H(m)$ denote the maximal number of limit cycles of polynomial systems of degree m. It is called the Hilbert number. The main part of Hilbert?s 16th problem posed in 1900 is to find its value. The problem is still open even for $m=2$. However, there have been many interesting results on the lower bound of it for $m?2$. In this paper, we give some new lower bounds of this number. The results obtained in this paper improve all existing results for all $m?7$ based on some known results for $m=3,4,5,6$. In particular, we obtain that $H(m)$ grows at least as rapidly as $\frac{1}{2\ln 2}{(m+2)}^2\ln (m+2)$ for all large m.     

On perfect 2-colorings of the q-ary n-cube

A coloring of a $q$-ary $n$-dimensional cube (hypercube) is called perfect if, for every $n$-tuple $x$, the collection of the colors of the neighbors of $x$ depends only on the color of $x$. A Boolean-valued function is called correlation-immune of degree $n?m$ if it takes value $1$ the same number of times for each $m$-dimensional face of the hypercube. Let $f={\chi }^S$ be a characteristic function of a subset $S$ of hypercube. In the present paper we prove the inequality $\rho \left(S\right)q(\mathrm{cor}\left(f\right)+1)\le \alpha \left(S\right)$, where $\mathrm{cor}\left(f\right)$ is the maximum degree of the correlation immunity of $f$, $\alpha \left(S\right)$ is the average number of neighbors in the set $S$ for $n$-tuples in the complement of a set $S$, and $\rho \left(S\right)=\left|S\right|/q^n$ is the density of the set $S$. Moreover, the function $f$ is a perfect coloring if and only if we have an equality in the formula above. Also, we find a new lower bound for the cardinality of components of a perfect coloring and a 1-perfect code in the case $q>2$.     

On the geography of threefolds of general type

Let X be a complex nonsingular projective 3-fold of general type. We show that there are positive constants c, $c^{\prime }$ and $m_1$ such that $\chi ({\omega }_X)??c\mathrm{Vol}(X)$ and $P_m(X)?c^{\prime }{m}^3\mathrm{Vol}(X)$ for all $m?m_1$.     

Multiplicity results for two kinds of equivariant systems

Two equivariant problems of the form $\epsilon \mathrm{\Delta }u=\nabla F\left(u\right)$ are considered, where $F$ is a real function which is invariant under the action of a group $G$, and, using Morse theory, for each problem an arbitrarily great number of orbits of solutions is founded, choosing $\epsilon$ suitably small.The first problem is a $O\left(2\right)$-equivariant system of two equations, which can be seen as a complex Ginzburg-Landau equation, while the second one is a system of $m$ equations which is equivariant for the action of a finite group of real orthogonal matrices $m\times m$.     

Efficient one-dimensional real scaled matching

Real Scaled Matching is the problem of finding all locations in the text where the pattern, proportionally enlarged according to an arbitrary real-sized scale, appears. Real scaled matching is an important problem that was originally inspired by Computer Vision.In this paper, we present a new, more precise and realistic, definition for one-dimensional real scaled matching, and an efficient algorithm for solving this problem. For a text of length n and a pattern of length m, the algorithm runs in time $\mathrm{O}(n\log m+\sqrt{n}{m}^{3/2}\sqrt{\log m})$.     

Structures and lower bounds for binary covering arrays

A $q$-ary $t$-covering array is an $m\times n$ matrix with entries from $\{0,1,\dots ,q?1\}$ with the property that for any $t$ column positions, all $q^t$ possible vectors of length $t$ occur at least once. One wishes to minimize $m$ for given $t$ and $n$, or maximize $n$ for given $t$ and $m$. For $t=2$ and $q=2$, it is completely solved by Rényi, Katona, and Kleitman and Spencer. They also show that maximal binary 2-covering arrays are uniquely determined. Roux found a lower bound of $m$ for a general $t,n$, and $q$. In this article, we show that $m\times n$ binary 2-covering arrays under some constraints on $m$ and $n$ come from the maximal covering arrays. We also improve the lower bound of Roux for $t=3$ and $q=2$, and show that some binary 3 or 4-covering arrays are uniquely determined.