Small Space Representations for Metric Min-sum k-Clustering and Their Applications

The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C ₁,…,C _k ?P such that $\sum_{i=1}^{k}\sum_{p,q\in C_{i}}d(p,q)The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C ₁,…,C _k ⊆P such that ?_i=1^k?_{p,q ? Ci}d(p,q)\sum_{i=1}^{k}\sum_{p,q\in C_{i}}d(p,q) is minimized. We show the first efficient construction of a coreset for this problem. Our coreset construction is based on a new adaptive sampling algorithm. With our construction of coresets we obtain two main algorithmic results.     

Lower Bounds for Agnostic Learning via Approximate Rank

We prove that the concept class of disjunctions cannot be pointwise approximated by linear combinations of any small set of arbitrary real-valued functions. That is, suppose that there exist functions f₁, ?, f_r\phi_{1}, \ldots , \phi_{r} : {− 1, 1}ⁿ → \mathbbR{\mathbb{R}} with the property that every disjunction f on n variables has $\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi _{i}\|_{\infty}\leq 1/3$\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi _{i}\|_{\infty}\leq 1/3 for some reals a₁, ?, a_r\alpha_{1}, \ldots , \alpha_{r}. We prove that then $r \geq exp \{\Omega(\sqrt{n})\}$r \geq exp \{\Omega(\sqrt{n})\}, which is tight. We prove an incomparable lower bound for the concept class of decision lists. For the concept class of majority functions, we obtain a lower bound of W(2ⁿ/n)\Omega(2^{n}/n) , which almost meets the trivial upper bound of 2ⁿ for any concept class. These lower bounds substantially strengthen and generalize the polynomial approximation lower bounds of Paturi (1992) and show that the regression-based agnostic learning algorithm of Kalai et al. (2005) is optimal.     

Expansion of Self-Similar Functions in the Faber–Schauder System

Let Ω = A^N be a space of right-sided infinite sequences drawn from a finite alphabet A = {0,1}, N = {1,2,…}. Let ρ(x, y)Σ_k=1^∞|x _k ? y _k |2^?k be a metric on Ω = AN, and μ the Bernoulli measure on Ω with probabilities p₀, p₁ > 0, p₀ + p₁ = 1. Denote by B(x,ω) an open ball of radius r centered at ω. The main result of this paper \(\mu (B(\omega ,r))r + \sum\nolimits_{n = 0}^\infty {\sum\nolimits_{j = 0}^{{2^n} - 1} {{\mu _{n,j}}} } (\omega )\tau ({2^n}r - j)\), where τ(x) = 2min {x,1 ? x}, 0 ≤ x ≤ 1, (τ(x) = 0, if x < 0 or x > 1 ), \({\mu _{n,j}}(\omega ) = (1 - {p_{{\omega _{n + 1}}}})\prod _{k = 1}^n{p_{{\omega _k}}} \oplus {j_k}\), \(j = {j_1}{2^{n - 1}} + {j_2}{2^{n - 2}} + ... + {j_n}\). The family of functions 1, x, τ(2 ⁿ r ? j), j = 0,1,…, 2 ⁿ ? 1, n = 0,1,…, is the Faber–Schauder system for the space C([0,1]) of continuous functions on [0, 1]. We also obtain the Faber–Schauder expansion for Lebesgue’s singular function, Cezaro curves, and Koch–Peano curves. Article is published in the author’s wording.     

Efficient temporal counting with bounded error

This paper studies aggregate search in transaction time databases. Specifically, each object in such a database can be modeled as a horizontal segment, whose y-projection is its search key, and its x-projection represents the period when the key was valid in history. Given a query timestamp q _t and a key range , a count-query retrieves the number of objects that are alive at q _t , and their keys fall in . We provide a method that accurately answers such queries, with error less than , where N _alive(q _t ) is the number of objects alive at time q _t , and ɛ is any constant in (0, 1]. Denoting the disk page size as B, and n =  N / B, our technique requires O(n) space, processes any query in O(log _B n) time, and supports each update in O(log _B n) amortized I/Os. As demonstrated by extensive experiments, the proposed solutions guarantee query results with extremely high precision (median relative error below 5%), while consuming only a fraction of the space occupied by the existing approaches that promise precise results.     

A Sigma-Pi-Sigma Neural Network (SPSNN)

This letter presents a sigma-pi-sigma neural network (SPSNN) structure. The SPSNN can learn to implement static mapping that multilayer neural networks and radial basis function networks usually do. The output of the SPSNN has the sum of product-of-sum form , where x _j's are inputs, N _v is the number of inputs, f _nij() is a function to be generated through the network training, and K is the number of pi-sigma network (PSN) which is the basic building block for SPSNN. A linear memory array can be used to implement f _nij (). The function f _nij (x _j ) can be expressed as , where B _ijk() is a single-variable basis function, w _nijk's are weight values stored in memory, N _q is the quantized element number for x _j , and N _e is the number of basis functions in the neighborhood used for storing information for x _j. If all B _ijk()'s are Gaussian functions, the new neural network degenerates to a Gaussian function network. This paper focuses on the use of overlapped rectangular pulses as the basis functions. With such basis functions, will equal either zero or w _nijk, and the computation of f _nij (x _j) becomes a simple addition of retrieved w _nijk's. The new neural network structure demonstrates excellent learning convergence characteristics and requires small memory space. It has merits over multilayer neural networks, radial basis function networks and CMAC. This revised version was published online in June 2006 with corrections to the Cover Date.     

An extension theorem for arcs and linear codes

We prove the following generalization to the extension theorem of Hill and Lizak: For every nonextendable linear [n, k, d] _q code, q = p ^s , (d,q) = 1, we have $\sum\limits_{i\not \equiv 0,d(\bmod q)} {A_i > q^{k - 3} r(q),} $ where q + r(q) + 1 is the smallest size of a nontrivial blocking set in PG(2, q). This result is applied further to rule out the existence of some linear codes over $\mathbb{F}_4 $ meeting the Griesmer bound.     

Polylogarithms and the Asymptotic Formula for the Moments of Lebesgue’s Singular Function

Recall that Lebesgue’s singular function L(t) is defined as the unique solution to the equation L(t) = qL(2t) + pL(2t ? 1), where p, q > 0, q = 1 ? p, p ≠ q. The variables M _n = ∫₀¹t ⁿ dL(t), n = 0,1,… are called the moments of the function The principal result of this work is \({M_n} = {n^{{{\log }_2}p}}{e^{ - \tau (n)}}(1 + O({n^{ - 0.99}}))\), where the function τ(x) is periodic in log₂x with the period 1 and is given as \(\tau (x) = \frac{1}{2}1np + \Gamma '(1)lo{g_2}p + \frac{1}{{1n2}}\frac{\partial }{{\partial z}}L{i_z}( - \frac{q}{p}){|_{z = 1}} + \frac{1}{{1n2}}\sum\nolimits_{k \ne 0} {\Gamma ({z_k})L{i_{{z_k} + 1}}( - \frac{q}{p})} {x^{ - {z_k}}}\), \({z_k} = \frac{{2\pi ik}}{{1n2}}\), k ≠ 0. The proof is based on poissonization and the Mellin transform.     

Alcuni problemi relativi alle formule di quadratura del tipo di tchebycheff

In this paper we study quadrature formulas of the form $$\int\limits_{ - 1}^1 {(1 - x)^a (1 + x)^\beta f(x)dx = \sum\limits_{i = 0}^{r - 1} {[A_i f^{(i)} ( - 1) + B_i f^{(i)} (1)] + K_n (\alpha ,\beta ;r)\sum\limits_{i = 1}^n {f(x_{n,i} ),} } } $$ (α>?1, β>?1), with realA _i ,B _i ,K _n and real nodesx _n,i in (?1,1), valid for prolynomials of degree ≤2n+2r?1. In the first part we prove that there is validity for polynomials exactly of degree2n+2r?1 if and only if α=β=?1/2 andr=0 orr=1. In the second part we consider the problem of the existence of the formula $$\int\limits_{ - 1}^1 {(1 - x^2 )^{\lambda - {1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-\nulldelimiterspace} 2}} f(x)dx = A_n f( - 1) + B_n f(1) + C\sum\limits_{i = 1}^n {f(x_{n,i} )} }$$ for polynomials of degree ≤n+2. Some numerical results are given when λ=1/2.     

Interpolation of Shifted-Lacunary Polynomials

Given a “black box” function to evaluate an unknown rational polynomial f ? \mathbbQ[x]f \in {\mathbb{Q}}[x] at points modulo a prime p, we exhibit algorithms to compute the representation of the polynomial in the sparsest shifted power basis. That is, we determine the sparsity $t \in {\mathbb{Z}}_{>0}$t \in {\mathbb{Z}}_{>0}, the shift a ? \mathbbQ\alpha \in {\mathbb{Q}}, the exponents 0 ￡ e₁ < e₂ < ? < e_t{0 \leq e_{1} < e_{2} < \cdots < e_{t}}, and the coefficients c₁, ?, c_t ? \mathbbQ \{0}c_{1}, \ldots , c_{t} \in {\mathbb{Q}} \setminus \{0\} such that

Large deviations for distributions of sums of random variables: Markov chain method

Let {ξ _k } _k=0^∞ be a sequence of i.i.d. real-valued random variables, and let g(x) be a continuous positive function. Under rather general conditions, we prove results on sharp asymptotics of the probabilities $ P\left\{ {\frac{1} {n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\} $ P\left\{ {\frac{1} {n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\} , n → ∞, and also of their conditional versions. The results are obtained using a new method developed in the paper, namely, the Laplace method for sojourn times of discrete-time Markov chains. We consider two examples: standard Gaussian random variables with g(x) = |x| ^p , p > 0, and exponential random variables with g(x) = x for x ≥ 0.     

Symmetric Rank Codes

As is well known, a finite field _n = GF(q ⁿ ) can be described in terms of n × n matrices A over the field = GF(q) such that their powers A ⁱ , i = 1, 2, ..., q ⁿ – 1, correspond to all nonzero elements of the field. It is proved that, for fields _n of characteristic 2, such a matrix A can be chosen to be symmetric. Several constructions of field-representing symmetric matrices are given. These matrices A ⁱ together with the all-zero matrix can be considered as a _n -linear matrix code in the rank metric with maximum rank distance d = n and maximum possible cardinality q ⁿ . These codes are called symmetric rank codes. In the vector representation, such codes are maximum rank distance (MRD) linear [n, 1, n] codes, which allows one to use known rank-error-correcting algorithms. For symmetric codes, an algorithm of erasure symmetrization is proposed, which considerably reduces the decoding complexity as compared with standard algorithms. It is also shown that a linear [n, k, d = n – k + 1] MRD code _k containing the above-mentioned one-dimensional symmetric code as a subcode has the following property: the corresponding transposed code is also _n -linear. Such codes have an extended capability of correcting symmetric errors and erasures.     

List decoding for a multiple access hyperchannel

We obtain bounds on the rate of (optimal) list-decoding codes with a fixed list size L ≥ 1 for a q-ary multiple access hyperchannel (MAHC) with s ≥ 2 inputs and one output. By definition, an output signal of this channel is the set of symbols of a q-ary alphabet that occur in at least one of the s input signals. For example, in the case of a binary MAHC, where q = 2, an output signal takes values in the ternary alphabet {0, 1, {0, 1}}; namely, it equals 0 (1) if all the s input signals are 0 (1) and equals {0, 1} otherwise. Previously, upper and lower bounds on the code rate for a q-ary MAHC were studied for L ≥ 1 and q = 2, and also for the nonbinary case q ≥ 3 for L = 1 only, i.e., for so-called frameproof codes. Constructing upper and lower bounds on the rate for the general case of L ≥ 1 and q ≥ 2 in the present paper is based on a substantial development of methods that we designed earlier for the classical binary disjunctive multiple access channel.     

The <Emphasis Type="Italic">k</Emphasis>-Homotopic Thinning and a Torus-Like Digital Image in <Emphasis Type="Bold">Z</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

In order to discuss digital topological properties of a digital image (X,k), many recent papers have used the digital fundamental group and several digital topological invariants such as the k-linking number, the k-topological number, and so forth. Owing to some difficulties of an establishment of the multiplicative property of the digital fundamental group, a k-homotopic thinning method can be essentially used in calculating the digital fundamental group of a digital product with k-adjacency. More precisely, let be a simple closed k _i -curve with l _i elements in . For some k-adjacency of the digital product which is a torus-like set, proceeding with the k-homotopic thinning of , we obtain its k-homotopic thinning set denoted by DT _k . Writing an algorithm for calculating the digital fundamental group of , we investigate the k-fundamental group of by the use of various properties of a digital covering (Z×Z,p ₁×p ₂,DT _k ), a strong k-deformation retract, and algebraic topological tools. Finally, we find the pseudo-multiplicative property (contrary to the multiplicative property) of the digital fundamental group. This property can be used in classifying digital images from the view points of both digital k-homotopy theory and mathematical morphology.

State-space for non-linear algebraically constrained dynamical systems

Non-linear state differential equations x = f(x, u) with algebraic constraints g(x, u, e) = 0, e = e (t), which describe possibly singular systems, are considered. The derivation of equivalent unconstrained state differential equations x* = f* (x*, e, ?,...), {x* }c:{x} ≥ {x} with the ‘ output’ equations u = h*(x*, u*, e, ?,…) and x equals; h* * (x*, e, ?…) is studied. Instead of an extension of the linear matrix-oriented singular system theory, the non-linear system inversion ideas are found to be easily applicable, to preserve much of the original system structure, and to give insight into the possibly distributional behaviour of and the possible incompatibilities in the system.     

W1,q stability of the Fortin operator for the MAC scheme

We prove in this paper the continuity of the natural projection operator from W^1,q₀(\varOmega )^dW^{1,q}_{0}(\varOmega )^{d}, q∈[1,+∞), d=2 or d=3, to the MAC discrete space of piecewise constant functions over the dual cells, endowed with the finite volume W₀^1,qW_{0}^{1,q}-discrete norm. Since this projection operator is also a Fortin operator (that is an operator which “preserves” the divergence), this result may be applied to control the pressure in mixed problems where the test function for the velocity must be more regular than H¹₀(\varOmega )^dH^{1}_{0}(\varOmega )^{d}.     

Uniform stabilization for linear systems with persistency of excitation: the neutrally stable and the double integrator cases

Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, ${\int_t^{t+T}\alpha(s){\rm d}s \geq \mu}Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, . In particular, when α(t) becomes zero the system dynamics switches to an uncontrollable system. In this paper, we address the following question: is it possible to find a linear time-invariant state-feedback u = Kx, with K only depending on (A, B) and possibly on μ, T, which globally asymptotically stabilizes the system? We give a positive answer to this question for two cases: when A is neutrally stable and when the system is the double integrator. Notation  A continuous function is of class , if it is strictly increasing and is of class if it is continuous, non-increasing and tends to zero as its argument tends to infinity. A function is said to be a class -function if, for any t ≥ 0, and for any s ≥ 0. We use |·| for the Euclidean norm of vectors and the induced L ₂-norm of matrices.     

Comparing Nontriviality for E and EXP

A set A is nontrivial for the linear-exponential-time class E=DTIME(2 ^lin ) if for any k≥1 there is a set B _k ∈E such that B _k is (p-m-)reducible to A and B_k ? DTIME(2^k·n)B_{k} \not\in \mathrm{DTIME}(2^{k\cdot n}). I.e., intuitively, A is nontrivial for E if there are arbitrarily complex sets in E which can be reduced to A. Similarly, a set A is nontrivial for the polynomial-exponential-time class EXP=DTIME(2 ^poly ) if for any k≥1 there is a set [^(B)]_k ? EXP\hat{B}_{k} \in \mathrm {EXP} such that [^(B)]_k\hat{B}_{k} is reducible to A and [^(B)]_k ? DTIME(2^nk)\hat{B}_{k} \not\in \mathrm{DTIME}(2^{n^{k}}). We show that these notions are independent, namely, there are sets A ₁ and A ₂ in E such that A ₁ is nontrivial for E but trivial for EXP and A ₂ is nontrivial for EXP but trivial for E. In fact, the latter can be strengthened to show that there is a set A∈E which is weakly EXP-hard in the sense of Lutz (SIAM J. Comput. 24:1170–1189, 11) but E-trivial.     

A technical note on AC-Unification. The number of minimal unifiers of the equation αx1 + ⋯ + αxp ≐AC βy1 + ⋯ + βyq

We show in this note that the equation αx₁ + #x22EF; +αx_p?_ACβy₁ + α +βy_q where + is an AC operator and αx stands for x+...+x (α times), has exactly $$\left( { - 1} \right)^{p + q} \sum\limits_{i = 0}^p {\sum\limits_{j = 0}^q {\left( { - 1} \right)^{1 + 1} \left( {\begin{array}{*{20}c} p \\ i \\ \end{array} } \right)\left( {\begin{array}{*{20}c} q \\ j \\ \end{array} } \right)} 2^{\left( {\alpha + \begin{array}{*{20}c} {j - 1} \\ \alpha \\ \end{array} } \right)\left( {\beta + \begin{array}{*{20}c} {i - 1} \\ \beta \\ \end{array} } \right)} } $$ minimal unifiers if gcd(α, β)=1.     

Theory Of A B-Spline Basis Function

This paper extends the work of a previous paper of the author. A theoretical argument is provided to justify the heuristic algorithm used in the former paper. On the basis of the theory one derives, the previous algorithm can be further simplified. In the simplified basis function algorithm, the regular basis function (where $N_i^1(t)$ is 1 for $t_i \le t \lt t_{i + 1}$ and zero elsewhere) can be used for all cases except the case of the last point of a clamped B-spline where the basis function is modified to $N_{i,1} (t)$ where is 1 for $t_i \le t \le t_{i + 1}$ and zero elsewhere. Under this simplified algorithm, the knots ( i.e. , $t_{0}$ , $t_{1}, \ldots, t_{n+k}$ ) are a k -extended partition in the interior of the knot vector with a possibility that two ends of the knot vector could be a $(k + 1)$ -extended partition (case of clamped B-spline). It is shown that given a set of $(n + 1)$ control points, $V_{0}$ , $V_{1}, \ldots, V_{n}$ , the order of k , and the knots $(t_{0}, t_{1}, \ldots, t_{n+k})$ , the B-spline $P(t) = \sum_{i = 0}^{n} N_{i}^{k}(t)V_{i}$ is a continuous function for $t \in [t_{k - 1}, t_{n + 1}]$ and maintains the partition of unity. This algorithm circumvents the problem of generating a spike at the last point of a clamped B-spline. The constraint of having k -extended partition interior knots overcomes the problem of disconnecting the B-spline at the k repeated knot.     

Sensitivity minimization in an H ∞ norm: parametrization of all suboptimal solutions

A number of problems in the control of linear feedback systems can be reduced to the following: we are given three stable rational matrix functions K, ?, ψ of sizes p ₁ x q ₁, p ₁ x q ₂ and p ₂ x q ₁ respectively, and seek a stable rational q ₂ x p ₂ matrix function S so as to minimize ¦K + ?Sψ¦_∞. We assume that p ₁ ≥ q ₂, p ₂≤q ₁ and that ? and ψ have maximal rank (q ₂ and p ₂ respectively) on the jω-axis. Given a tolerance level μ sufficiently large, we obtain a linear fractional map G → F = [0 ₁₁ G + 0 ₁₂, 0 ₁₃][0 ₂₁ G + 0 ₂₂, 0 ₂₃]^?1 such that F = K + ?Sψ with S stable and ¦F _∞ ≤ μ if and only if G is a stable q ₂ x p ₂ matrix function with ¦G¦_∞ ≤ 1. The computation of 0 = [0 _ij ] (1 ≤ i ≤ 2, 1 ≤ j ≤ 3) reduces to solving a pair of symmetric Wiener–Hopf factorization problems. For the special case where ? = [I _q2, 0]^T, ψ = [I _p2, 0] (and K not necessarily stable) to which the general case can be reduced, we provide explicit state-space formulae for 0 in terms of a state-space realization of K and the solutions of some related Riccati equations. The approach is a natural extension of that of Ball–Helton and Ball–Ran for the case p ₁ = q ₂ and p ₂ = q ₁.