On the uniqueness of overcomplete dictionaries, and a practical way to retrieve them

A full-rank under-determined linear system of equations Ax = b has in general infinitely many possible solutions. In recent years there is a growing interest in the sparsest solution of this equation—the one with the fewest non-zero entries, measured by ∥x∥₀. Such solutions find applications in signal and image processing, where the topic is typically referred to as “sparse representation”. Considering the columns of A as atoms of a dictionary, it is assumed that a given signal b is a linear composition of few such atoms. Recent work established that if the desired solution x is sparse enough, uniqueness of such a result is guaranteed. Also, pursuit algorithms, approximation solvers for the above problem, are guaranteed to succeed in finding this solution.Armed with these recent results, the problem can be reversed, and formed as an implied matrix factorization problem: Given a set of vectors {b_i}, known to emerge from such sparse constructions, Ax_i = b_i, with sufficiently sparse representations x_i, we seek the matrix A. In this paper we present both theoretical and algorithmic studies of this problem. We establish the uniqueness of the dictionary A, depending on the quantity and nature of the set {b_i}, and the sparsity of {x_i}. We also describe a recently developed algorithm, the K-SVD, that practically find the matrix A, in a manner similar to the K-Means algorithm. Finally, we demonstrate this algorithm on several stylized applications in image processing.     

Small divisors of Bernoulli sums

Let ?= {?_i,i ≥1} be a sequence of independent Bernoulli random variables (P{?_i = 0} = P{?_i = 1 } = 1/2) with basic probability space (Ω, A, P). Consider the sequence of partial sums B_n=?₁+...+?_n, n=1,2..... We obtain an asymptotic estimate for the probability P{P^-(B_n) > >} for >≤n^{e/log log n}, c a positive constant.     

Numerical radius and zero pattern of matrices

Let A be an n×n complex matrix and r be the maximum size of its principal submatrices with no off-diagonal zero entries. Suppose A has zero main diagonal and x is a unit n-vector. Then, letting ‖A‖ be the Frobenius norm of A, we show that

|〈Ax,x〉^|2?(1−1/2r−1/2n)‖A^‖2.     

Characterization of the absence of a spectral gapfor a class of periodic Jacobi operators

Let q ∈ {2, 3} and let 0 = s₀ < s₁ < … < s_q = T be integers. For m, n ∈ Z, we put ¯m,n = {j ∈ Z| m? j ? n}. We set l_j = s_j − s_j−1 for j ∈ 1, q. Given (p₁,, p_q) ∈ R^q, let b: Z → R be a periodic function of period T such that b(·) = p_j on s_j−1 + 1, s_j for each j ∈ 1, q. We study the spectral gaps of the Jacobi operator (Ju)(n) = u(n + 1) + u(n − 1) + b(n)u(n) acting on l²(Z). By [λ_2j , λ_2j−1] we denote the jth band of the spectrum of J counted from above for j ∈ 1, T. Suppose that p_m ≠ p_n for m ≠ n. We prove that the statements (i) and (ii) below are equivalent for λ ∈ R and i ∈ 1, T − 1.     

On the Bateman-Horn Conjecture

Let r be a positive integer and f₁,…,f_r be distinct polynomials in Z[X]. If f₁(n),…,f_r(n) are all prime for infinitely many n, then it is necessary that the polynomials f_i are irreducible in Z[X], have positive leading coefficients, and no prime p divides all values of the product f₁(n)···f_r(n), as n runs over Z. Assuming these necessary conditions, Bateman and Horn (Math. Comput.16 (1962), 363-367) proposed a conjectural asymptotic estimate on the number of positive integers n?x such that f₁(n),…,f_r(n) are all primes. In the present paper, we apply the Hardy-Littlewood circle method to study the Bateman-Horn conjecture when r?2. We consider the Bateman-Horn conjecture for the polynomials in any partition {f₁,…,f_s}, {f_s+1,…,f_r} with a linear change of variables. Our main result is as follows: If the Bateman-Horn conjecture on such a partition and change of variables holds true with some conjectural error terms, then the Bateman-Horn conjecture for f₁,…,f_r is equivalent to a plausible error term conjecture for the minor arcs in the circle method.     

Strong linear preservers of rank reverse permutability on triangular matrices

Let F be a field with ∣F∣ > 2 and T_n(F) be the set of all n × n upper triangular matrices, where n ? 2. Let k ? 2 be a given integer. A k-tuple of matrices A₁, …, A_k ∈ T_n(F) is called rank reverse permutable if rank(A₁ A₂ ? A_k) = rank(A_k A_k−1 ? A₁). We characterize the linear maps on T_n(F) that strongly preserve the set of rank reverse permutable matrix k-tuples.     

Piecewise linear maps, Liapunov exponents and entropy

Let be a class of piecewise linear maps associated with a transition matrix A. In this paper, we prove that if fA,x∈LA, then the Liapunov exponent λ(x) of fA,x is equal to a measure theoretic entropy hmA,x of fA,x, where mA,x is a Markov measure associated with A and x. The Liapunov exponent and the entropy are computable by solving an eigenvalue problem and can be explicitly calculated when the transition matrix A is symmetric. Moreover, we also show that maxxλ(x)=maxxhmA,x=log(λ₁), where λ₁ is the maximal eigenvalue of A.     

Asymptotic Analysis for Random Walks with Nonidentically Distributed Jumps Having Finite Variance

Let ξ₁,ξ₂,... be independent random variables with distributions F₁F₂,... in a triangular array scheme (F _i may depend on some parameter). Assume that Eξ _i = 0, Eξ _i ² < ∞, and put \(S_n = \sum {_{i = 1}^n \;} \xi _i ,\;\overline S _n = \max _{k \leqslant n} S_k\). Assuming further that some regularly varying functions majorize or minorize the “averaged” distribution \(F = \frac{1}{n}\sum {_{i = 1}^n F_i }\), we find upper and lower bounds for the probabilities P(S _n > x) and \(P(\bar S_n > x)\). We also study the asymptotics of these probabilities and of the probabilities that a trajectory {S _k } crosses the remote boundary {g(k)}; that is, the asymptotics of P(max_k≤n(S _k ? g(k)) > 0). The case n = ∞ is not excluded. We also estimate the distribution of the first crossing time.     

Linear equations with unknowns from a multiplicative group whose solutions lie in a small number of subspaces

Let K be a field of characteristic 0 and let (K^*)ⁿ denote the n-fold Cartesian product of K^*, endowed with coordinatewise multiplication. Let Γ be a subgroup of (K^*)ⁿ of finite rank. We consider equations (*) a₁x₁ + … + a_nx_n = 1 in x = (x₁x_n)Γ, where a = (a₁,a_n)(K^*)ⁿ. Two tuples a, b(K^*)ⁿ are called Γ-equivalent if there is a uΓ such that b = u · a. Gy?ry and the author [Compositio Math. 66 (1988) 329-354] showed that for all but finitely many Γ-equivalence classes of tuples a(K^*)ⁿ, the set of solutions of (*) is contained in the union of not more than 2⁽ⁿ⁺¹! proper linear subspaces of Kⁿ. Later, this was improved by the author [J. reine angew. Math. 432 (1992) 177-217] to (n!)²ⁿ⁺². In the present paper we will show that for all but finitely many Γ-equivalence classes of tuples of coefficients, the set of non-degenerate solutions of (*) (i.e., with non-vanishing subsums) is contained in the union of not more than 2ⁿ proper linear subspaces of Kⁿ. Further we give an example showing that 2ⁿ cannot be replaced by a quantity smaller than n.     

Generalized radix representations and dynamical systems. IV

For r = (r₁,…, r_d) ∈ ?^d the mapping τ_r:?^d →?^d given byτ_r(a₁,…,a_d) = (a₂, …, a_d,−⌊r₁a₁+…+ r_da_d⌋)where ⌊·⌋ denotes the floor function, is called a shift radix system if for each a ∈ ?^d there exists an integer k > 0 with τ_r^k(a) = 0. As shown in Part I of this series of papers, shift radix systems are intimately related to certain well-known notions of number systems like β-expansibns and canonical number systems. After characterization results on shift radix systems in Part II of this series of papers and the thorough investigation of the relations between shift radix systems and canonical number systems in Part III, the present part is devoted to further structural relationships between shift radix systems and β-expansions. In particular we establish the distribution of Pisot polynomials with and without the finiteness property (F).     

Some lower bounds for the spectral radius of matrices using traces

Let A be an n×n matrix with eigenvalues λ₁,λ₂,…,λ_n, and let m be an integer satisfying rank(A)?m?n. If A is real, the best possible lower bound for its spectral radius in terms of m, trA and trA² is obtained. If A is any complex matrix, two lower bounds for are compared, and furthermore a new lower bound for the spectral radius is given only in terms of trA,trA²,‖A‖,‖A^∗A-AA^∗‖,n and m.     

Estimates for interval probabilities of the sums of random variables with locally subexponential distributions

Let {_i} _i=1 be a sequence of independent identically distributed nonnegative random variables, S _n = ξ₁ + ? +ξ_n. Let Δ = (0, T] and x + Δ = (x, x + T]. We study the ratios of the probabilities P(S _n ε x + Δ)/P(ξ ₁ ε x + Δ) for all n and x. The estimates uniform in x for these ratios are known for the so-called Δ-subexponential distributions. Here we improve these estimates for two subclasses of Δ-subexponential distributions; one of them is a generalization of the well-known class LC to the case of the interval (0, T] with an arbitrary T ≤ ∞. Also, a characterization of the class LC is given.     

Norms on L of Periodic Interpolation Splines with Equidistant Nodes

We consider the set S _r,n of periodic (with period 1) splines of degree r with deficiency 1 whose nodes are at n equidistant points x_i=i / n. For n-tuples y = (y₀, ... , y_n-1), we take splines s _r,n (y, x) from S _r,n solving the interpolation problem

$$s_{r,n} (y,t_i ) = y_i,$$

where t _i = x _i if r is odd and t _i is the middle of the closed interval [x _i , x _i+1 ] if r is even. For the norms L _r,n ^* of the operator y → s _r,n (y, x) treated as an operator from l¹ to L¹ [0, 1] we establish the estimate

$$L_{r,n}^ * = \frac{4}{{\pi ^2 n}}log min(r,n) + O\left( {\frac{1}{n}} \right)$$

with an absolute constant in the remainder. We study the relationship between the norms L _r,n ^* and the norms of similar operators for nonperiodic splines.

     

A quantitative Khintchine-Groshev type theorem over a field of formal series

An asymptotic formula which holds almost everywhere is obtained for the number of solutions to theDiophantine inequalities ‖qA − p‖ < Ψ(‖g‖), where A is an n x m matrix (m > 1) over the field of formal Laurent series with coefficients from a finite field, and p and q are vectors of polynomials over the same finite field.     

An integro-local theorem applicable on the whole half-axis to the sums of random variables with regularly varying distributions

We obtain an integro-local limit theorem for the sum S(n) = ξ(1)+?+ξ(n) of independent identically distributed random variables with distribution whose right tail varies regularly; i.e., it has the form P(ξ≥t) = t ^?β L(t) with β > 2 and some slowly varying function L(t). The theorem describes the asymptotic behavior on the whole positive half-axis of the probabilities P(S(n) ∈ [x, x + Δ)) as x → ∞ for a fixed Δ > 0; i.e., in the domain where the normal approximation applies, in the domain where S(n) is approximated by the distribution of its maximum term, as well as at the “junction” of these two domains.     

On diophantine equations of the form {({\boldsymbol x}-{\boldsymbol a}_{\bf 1})({\boldsymbol x}-{\boldsymbol a}_{\bf 2}) \ldots ({\boldsymbol x}-{\boldsymbol a}_{\boldsymbol k}) + {\boldsymbol r} = {\boldsymbol y}^{ \boldsymbol n}}

Erd?s and Selfridge [3] proved that a product of consecutive integers can never be a perfect power. That is, the equation x(x?+?1)(x?+?2)...(x?+?(m???1))?=?y ⁿ has no solutions in positive integers x,m,n where m, n?>?1 and y?∈?Q. We consider the equation $$ (x-a_1)(x-a_2) \ldots (x-a_k) + r = y^n $$ where 0?≤?a ₁?<?a ₂?<???<?a _k are integers and, with r?∈?Q, n?≥?3 and we prove a finiteness theorem for the number of solutions x in Z, y in Q. Following that, we show that, more interestingly, for every nonzero integer n?>?2 and for any nonzero integer r which is not a perfect n-th power for which the equation admits solutions, k is bounded by an effective bound.     

Generalizations of some zero sum theorems

Given an abelian group G of order n, and a finite non-empty subset A of integers, the Davenport constant of G with weight A, denoted by D _A (G), is defined to be the least positive integer t such that, for every sequence (x ₁,..., x _t ) with x _i ?∈?G, there exists a non-empty subsequence \((x_{j_1},\ldots, x_{j_l})\) and a _i ?∈?A such that \(\sum_{i=1}^{l}a_ix_{j_i} = 0\). Similarly, for an abelian group G of order n, E _A (G) is defined to be the least positive integer t such that every sequence over G of length t contains a subsequence \((x_{j_1} ,\ldots, x_{j_n})\) such that \(\sum_{i=1}^{n}a_ix_{j_i} = 0\), for some a _i ?∈?A. When G is of order n, one considers A to be a non-empty subset of {1,..., n???1 }. If G is the cyclic group \({\Bbb Z}/n{\Bbb Z}\), we denote E _A (G) and D _A (G) by E _A (n) and D _A (n) respectively.In this note, we extend some results of Adhikari et al (Integers 8 (2008) Article A52) and determine bounds for \(D_{R_n}(n)\) and \(E_{R_n}(n)\), where \(R_n = \{x^2 : x \in (\mathbb{Z}/n\mathbb{ Z})^*\}\). We follow some lines of argument from Adhikari et al (Integers 8 (2008) Article A52) and use a recent result of Yuan and Zeng (European J. Combinatorics 31 (2010) 677–680), a theorem due to Chowla (Proc. Indian Acad. Sci. (Math. Sci.) 2 (1935) 242–243) and Kneser’s theorem (Math. Z. 58 (1953) 459–484; 66 (1956) 88–110; 61 (1955) 429–434).     

Isotopes of the alternative monster and the Skosyrsky algebra

We prove that the isotopes of the alternative monster and the Skosyrsky algebra satisfy the identity П_i=1⁴ [x_i, y_i] = 0. Hence, the algebras themselves satisfy the identity П_i=1⁴ (c, x_i, y_i) = 0. We also show that none of the identities П_i=1ⁿ(c, x_i, y_i) = 0 holds in all commutative alternative nil-algebras of index 3. Thus, we refute the Grishkov–Shestakov hypothesis about the structure of the free finitely generated commutative alternative nil-algebras of index 3.     

Some explicit solutions of the additive Deligne-Simpson problem and their applications

In this paper we construct three infinite series and two extra triples (E₈ and ) of complex matrices B, C, and A=B+C of special spectral types associated to Simpson's classification in Amer. Math. Soc. Proc. 1 (1992) 157 and Magyar et al. classification in Adv. Math. 141 (1999) 97. This enables us to construct Fuchsian systems of differential equations which generalize the hypergeometric equation of Gauss-Riemann. In a sense, they are the closest relatives of the famous equation, because their triples of spectral flags have finitely many orbits for the diagonal action of the general linear group in the space of solutions. In all the cases except for E₈, we also explicitly construct scalar products such that A, B, and C are self-adjoint with respect to them. In the context of Fuchsian systems, these scalar products become monodromy invariant complex symmetric bilinear forms in the spaces of solutions.When the eigenvalues of A, B, and C are real, the matrices and the scalar products become real as well. We find inequalities on the eigenvalues of A, B, and C which make the scalar products positive-definite.As proved by Klyachko, spectra of three hermitian (or real symmetric) matrices B, C, and A=B+C form a polyhedral convex cone in the space of triple spectra. He also gave a recursive algorithm to generate inequalities describing the cone. The inequalities we obtain describe non-recursively some faces of the Klyachko cone.     

The Critical Case of the Cramer-Lundberg Theorem on the Asymptotic Tail Behavior of the Maximum of a Negative Drift Random Walk

We study the asymptotic tail behavior of the maximum M = max{0,S _n ,n ≥ = 1} of partial sums S _n = ξ₁ + ? + ξ _n of independent identically distributed random variables ξ₁,ξ₂,... with negative mean. We consider the so-called Cramer case when there exists a β > 0 such that E e ^βξ1 = 1. The celebrated Cramer-Lundberg approximation states the exponential decay of the large deviation probabilities of M provided that Eξ₁ e ^βξ1 is finite. In the present article we basically study the critical case Eξ₁ e ^βξ1 = ∞.