Binarization is widely used as an image preprocessing step to separate object especially text from background before recognition. For noisy images with uneven illumination, threshold values should be computed pixel by pixel to obtain a good segmentation. Since local threshold values typically depend on moments-based statistics such as mean and variance of gray levels inside rectangular windows, integral images are commonly used to accelerate the calculation. However, integral images are memory consuming. For Sauvola's method, the two integral images occupy @math bytes given a @math input image. By using a recursive technique to avoid integral images, memory usage of intermediate data structures can be reduced significantly to @math bytes, while the time complexity remains @math independent of window size. Therefore, the proposed implementation enable various local adaptive binarization methods to be applied in real-time use cases on devices with limited resources.
@cite_20 used integral images to speed up the calculation of the mean of gray levels inside a window. @cite_9 extended the trick to calculate the standard deviation. Let @math , then @math as shown in Fig. . The integral image @math can be computed recursively using the following recurrence relation: @math . Therefore, the time complexity of Sauvola's method can be reduced to @math , which is independent of window size. However, consumption of memory increased significantly from @math to @math because the two additional integral images need to be stored.
@cite_9 @cite_20
2005008005 2003099669
In an unreliable single-hop broadcast network setting, we investigate the throughput and decoding-delay performance of random linear network coding as a function of the coding window size and the network size. Our model consists of a source transmitting packets of a single flow to a set of @math users over independent erasure channels. The source performs random linear network coding (RLNC) over @math (coding window size) packets and broadcasts them to the users. We note that the broadcast throughput of RLNC must vanish with increasing @math , for any fixed @math Hence, in contrast to other works in the literature, we investigate how the coding window size @math must scale for increasing @math . Our analysis reveals that the coding window size of @math represents a phase transition rate, below which the throughput converges to zero, and above which it converges to the broadcast capacity. Further, we characterize the asymptotic distribution of decoding delay and provide approximate expressions for the mean and variance of decoding delay for the scaling regime of @math These asymptotic expressions reveal the impact of channel correlations on the throughput and delay performance of RLNC. We also show how our analysis can be extended to other rateless block coding schemes such as the LT codes. Finally, we comment on the extension of our results to the cases of dependent channels across users and asymmetric channel model. Let @math be the largest component of the Erdős–Renyi random graph @math . The mixing time of random walk on @math in the strictly supercritical regime, p = c n with fixed c > 1, was shown to have order log2n by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald. In the critical window, p = (1 + e) n where λ = e3n is bounded, Nachmias and Peres proved that the mixing time on @math is of order n. However, it was unclear how to interpolate between these results, and estimate the mixing time as the giant component emerges from the critical window. Indeed, even the asymptotics of the diameter of @math in this regime were only recently obtained by Riordan and Wormald, as well as the present authors and Kim. In this paper, we show that for p = (1 + e) n with λ = e3n → ∞ and λ = o(n), the mixing time on @math is with high probability of order (n λ)log2λ. In addition, we show that this is the order of the largest mixing time over all components, both in the slightly supercritical and in the slightly subcritical regime [i.e., p = (1 − e) n with λ as above]. We consider the maximum independent set problem on graphs with maximum degree @math . We show that the integrality gap of the Lov 'asz @math -function based SDP is @math . This improves on the previous best result of @math , and almost matches the integrality gap of @math recently shown for stronger SDPs, namely those obtained using poly- @math levels of the @math semidefinite hierarchy. The improvement comes from an improved Ramsey-theoretic bound on the independence number of @math -free graphs for large values of @math . We also show how to obtain an algorithmic version of the above-mentioned @math -based integrality gap result, via a coloring algorithm of Johansson. The resulting approximation guarantee of @math matches the best unique-games-based hardness result up to lower-order poly- @math factors. We introduce a general purpose algorithm for rapidly computing certain types of oscillatory integrals which frequently arise in problems connected to wave propagation, general hyperbolic equations, and curvilinear tomography. The problem is to numerically evaluate a so-called Fourier integral operator (FIO) of the form @math at points given on a Cartesian grid. Here, @math is a frequency variable, @math is the Fourier transform of the input @math , @math is an amplitude, and @math is a phase function, which is typically as large as @math ; hence the integral is highly oscillatory. Because a FIO is a dense matrix, a naive matrix vector product with an input given on a Cartesian grid of size @math by @math would require @math operations. This paper develops a new numerical algorithm which requires @math operations and as low as @math in storage space (the constants in front of these estimates are small). It operates by localizing the integral over polar wedges with small angular aperture in the frequency plane. On each wedge, the algorithm factorizes the kernel @math into two components: (1) a diffeomorphism which is handled by means of a nonuniform FFT and (2) a residual factor which is handled by numerical separation of the spatial and frequency variables. The key to the complexity and accuracy estimates is the fact that the separation rank of the residual kernel is provably independent of the problem size. Several numerical examples demonstrate the numerical accuracy and low computational complexity of the proposed methodology. We also discuss the potential of our ideas for various applications such as reflection seismology. We consider the problem of maintaining aggregates and statistics over data streams, with respect to the last N data elements seen so far. We refer to this model as the sliding window model. We consider the following basic problem: Given a stream of bits, maintain a count of the number of 1's in the last N elements seen from the stream. We show that, using @math bits of memory, we can estimate the number of 1's to within a factor of @math . We also give a matching lower bound of @math memory bits for any deterministic or randomized algorithms. We extend our scheme to maintain the sum of the last N positive integers and provide matching upper and lower bounds for this more general problem as well. We also show how to efficiently compute the Lp norms ( @math ) of vectors in the sliding window model using our techniques. Using our algorithm, one can adapt many other techniques to work for the sliding window model with a multiplicative overhead of @math in memory and a @math factor loss in accuracy. These include maintaining approximate histograms, hash tables, and statistics or aggregates such as sum and averages. We develop fast and memory efficient numerical methods for learning functions of many variables that admit sparse representations in terms of general bounded orthonormal tensor product bases. Such functions appear in many applications including, e.g., various Uncertainty Quantification(UQ) problems involving the solution of parametric PDE that are approximately sparse in Chebyshev or Legendre product bases. We expect that our results provide a starting point for a new line of research on sublinear-time solution techniques for UQ applications of the type above which will eventually be able to scale to significantly higher-dimensional problems than what are currently computationally feasible. More concretely, let @math be a finite Bounded Orthonormal Product Basis (BOPB) of cardinality @math . We will develop methods that approximate any function @math that is sparse in the BOPB, that is, @math of the form @math with @math of cardinality @math . Our method has a runtime of just @math , uses only @math function evaluations on a fixed and nonadaptive grid, and not more than @math bits of memory. For @math , the runtime @math will be less than what is required to simply enumerate the elements of the basis @math ; thus our method is the first approach applicable in a general BOPB framework that falls into the class referred to as "sublinear-time". This and the similarly reduced sample and memory requirements set our algorithm apart from previous works based on standard compressive sensing algorithms such as basis pursuit which typically store and utilize full intermediate basis representations of size @math . We investigate the diameter problem in the streaming and sliding-window models. We show that, for a stream of @math points or a sliding window of size @math , any exact algorithm for diameter requires @math bits of space. We present a simple @math -approximation algorithm for computing the diameter in the streaming model. Our main result is an @math -approximation algorithm that maintains the diameter in two dimensions in the sliding-window model using @math bits of space, where @math is the maximum, over all windows, of the ratio of the diameter to the minimum non-zero distance between any two points in the window. Numerous centrality measures have been developed to quantify the importances of nodes in time-independent networks, and many of them can be expressed as the leading eigenvector of some matrix. With the increasing availability of network data that changes in time, it is important to extend such eigenvector-based centrality measures to time-dependent networks. In this paper, we introduce a principled generalization of network centrality measures that is valid for any eigenvector-based centrality. We consider a temporal network with @math nodes as a sequence of @math layers that describe the network during different time windows, and we couple centrality matrices for the layers into a supracentrality matrix of size @math whose dominant eigenvector gives the centrality of each node @math at each time @math . We refer to this eigenvector and its components as a joint centrality, as it reflects the importances of both the node @math and the time layer @math . We also introduce the concepts of marginal and conditional... It is shown that statistics of records for time series generated by random walks are independent of the details of the jump distribution, as long as the latter is continuous and symmetric. In @math steps, the mean of the record distribution grows as the @math while the standard deviation grows as @math , so the distribution is non-self-averaging. The mean shortest and longest duration records grow as @math and @math , respectively. The case of a discrete random walker is also studied, and similar asymptotic behavior is found. We present a general technique for detecting and counting small subgraphs. It consists of forming special linear combinations of the numbers of occurrences of different induced subgraphs of fixed size in a graph. These combinations can be efficiently computed by rectangular matrix multiplication. Our two main results utilizing the technique are as follows. Let @math be a fixed graph with @math vertices and an independent set of size @math 1. Detecting if an @math -vertex graph contains a (not necessarily induced) subgraph isomorphic to @math can be done in time @math , where @math is the exponent of fast arithmetic matrix multiplication of an @math matrix by an @math matrix. 2. When @math counting the number of (not necessarily induced) subgraphs isomorphic to @math can be done in the same time, i.e., in time @math It follows in particular that we can count the nu... Let @math be an @math real random matrix whose elements are independent and identically distributed standard normal random variables, and let @math be the 2-norm condition number of @math . We prove that, for any @math , @math , and @math , @math satisfies @math where @math and @math @math are universal positive constants independent of @math , @math , and @math . Moreover, for any @math and @math , @math A similar pair of results for complex Gaussian random matrices is also established. Given data stream @math of size @math of numbers from @math , the frequency of @math is defined as @math . The @math -th of @math is defined as @math . We consider the problem of approximating frequency moments in insertion-only streams for @math . For any constant @math we show an @math upper bound on the space complexity of the problem. Here @math is the iterative @math function. To simplify the presentation, we make the following assumptions: @math and @math are polynomially far; approximation error @math and parameter @math are constants. We observe a natural bijection between streams and special matrices. Our main technical contribution is a non-uniform sampling method on matrices. We call our method a ; it samples a heavy element (i.e., element @math with frequency @math ) with probability @math and gives approximation @math . In addition, the estimations never exceed the real values, that is @math for all @math . As a result, we reduce the space complexity of finding a heavy element to @math bits. We apply our method of recursive sketches and resolve the problem with @math bits. In this paper we present several results on the expected complexity of a convex hull of @math points chosen uniformly and independently from a convex shape. (i) We show that the expected number of vertices of the convex hull of @math points, chosen uniformly and independently from a disk is @math , and @math for the case a convex polygon with @math sides. Those results are well known (see rs-udkhv-63,r-slcdn-70,ps-cgi-85 ), but we believe that the elementary proof given here are simpler and more intuitive. (ii) Let @math be a set of directions in the plane, we define a generalized notion of convexity induced by @math , which extends both rectilinear convexity and standard convexity. We prove that the expected complexity of the @math -convex hull of a set of @math points, chosen uniformly and independently from a disk, is @math , where @math is the largest angle between two consecutive vectors in @math . This result extends the known bounds for the cases of rectilinear and standard convexity. (iii) Let @math be an axis parallel hypercube in @math . We prove that the expected number of points on the boundary of the quadrant hull of a set @math of @math points, chosen uniformly and independently from @math is @math . Quadrant hull of a set of points is an extension of rectilinear convexity to higher dimensions. In particular, this number is larger than the number of maxima in @math , and is also larger than the number of points of @math that are vertices of the convex hull of @math . Those bounds are known bkst-anmsv-78 , but we believe the new proof is simpler. The Hopfield model for a neural network is studied in the limit when the number @math of stored patterns increases with the size @math of the network, as @math . It is shown that, despite its spin-glass features, the model exhibits associative memory for @math , @math . This is a result of the existence at low temperature of @math dynamically stable degenerate states, each of which is almost fully correlated with one of the patterns. These states become ground states at @math . The phase diagram of this rich spin-glass is described. In this paper, we study the dominance relation under a stochastic setting. Let @math be a set of @math colored stochastic points in @math , each of which is associated with an existence probability. We investigate the problem of computing the probability that a realization of @math contains inter-color dominances, which we call the (CSD) problem. We propose the first algorithm to solve the CSD problem for @math in @math time. On the other hand, we prove that, for @math , even the CSD problem with a restricted color pattern is #P-hard. In addition, even if the existence probabilities are restricted to be @math , the problem remains #P-hard for @math . A simple FPRAS is then provided to approximate the desired probability in any dimension. We also study a variant of the CSD problem in which the dominance relation is considered with respect to not only the standard basis but any orthogonal basis of @math . Specifically, this variant, which we call the free-basis colored stochastic dominance (FBCSD) problem, considers the probability that a realization of @math contains inter-color dominances with respect to any orthogonal basis of @math . We show that the CSD problem is polynomial-time reducible to the FBCSD problem in the same dimension, which proves the #P-hardness of the latter for @math . Conversely, we reduce the FBCSD problem in @math to the CSD problem in @math , by which an @math time algorithm for the former is obtained. Let @math be an i.i.d. sequence of random variables in @math , @math . We show that, for any function @math , under regularity conditions, [n^ 1 2 (n^ -1 i=1 ^n (X_i) f ^(X_i) - (x) ,dx ) P 0, ] where @math is the classical kernel estimator of the density of @math . This result is striking because it speeds up traditional rates, in root @math , derived from the central limit theorem when @math . Although this paper highlights some applications, we mainly address theoretical issues related to the later result. We derive upper bounds for the rate of convergence in probability. These bounds depend on the regularity of the functions @math and @math , the dimension @math and the bandwidth of the kernel estimator @math . Moreover, they are shown to be accurate since they are used as renormalizing sequences in two central limit theorems each reflecting different degrees of smoothness of @math . As an application to regression modelling with random design, we provide the asymptotic normality of the estimation of the linear functionals of a regression function. As a consequence of the above result, the asymptotic variance does not depend on the regression function. Finally, we debate the choice of the bandwidth for integral approximation and we highlight the good behavior of our procedure through simulations. The k-means method is a widely used clustering algorithm. One of its distinguished features is its speed in practice. Its worst-case running-time, however, is exponential, leaving a gap between practical and theoretical performance. Arthur and Vassilvitskii (FOCS 2006) aimed at closing this gap, and they proved a bound of @math on the smoothed running-time of the k-means method, where n is the number of data points and @math is the standard deviation of the Gaussian perturbation. This bound, though better than the worst-case bound, is still much larger than the running-time observed in practice. We improve the smoothed analysis of the k-means method by showing two upper bounds on the expected running-time of k-means. First, we prove that the expected running-time is bounded by a polynomial in @math and @math . Second, we prove an upper bound of @math , where d is the dimension of the data space. The polynomial is independent of k and d, and we obtain a polynomial bound for the expected running-time for @math . Finally, we show that k-means runs in smoothed polynomial time for one-dimensional instances. Motivated by applications in which the data may be formulated as a matrix, we consider algorithms for several common linear algebra problems. These algorithms make more efficient use of computational resources, such as the computation time, random access memory (RAM), and the number of passes over the data, than do previously known algorithms for these problems. In this paper, we devise two algorithms for the matrix multiplication problem. Suppose @math and @math (which are @math and @math , respectively) are the two input matrices. In our main algorithm, we perform @math independent trials, where in each trial we randomly sample an element of @math with an appropriate probability distribution @math on @math . We form an @math matrix @math consisting of the sampled columns of @math , each scaled appropriately, and we form a @math matrix @math using the corresponding rows of @math , again scaled appropriately. The choice of @math and the column and row scaling are crucial features of the algorithm. When these are chosen judiciously, we show that @math is a good approximation to @math . More precisely, we show that @math where @math denotes the Frobenius norm, i.e., @math . This algorithm can be implemented without storing the matrices @math and @math in RAM, provided it can make two passes over the matrices stored in external memory and use @math additional RAM to construct @math and @math . We then present a second matrix multiplication algorithm which is similar in spirit to our main algorithm. In addition, we present a model (the pass-efficient model) in which the efficiency of these and other approximate matrix algorithms may be studied and which we argue is well suited to many applications involving massive data sets. In this model, the scarce computational resources are the number of passes over the data and the additional space and time required by the algorithm. The input matrices may be presented in any order of the entries (and not just row or column order), as is the case in many applications where, e.g., the data has been written in by multiple agents. In addition, the input matrices may be presented in a sparse representation, where only the nonzero entries are written. An efficient parallel algorithm is presented for computing selected components of @math where @math is a structured symmetric sparse matrix. Calculations of this type are useful for several applications, including electronic structure analysis of materials in which the diagonal elements of the Green's functions are needed. The algorithm proposed here is a direct method based on a block @math factorization. The selected elements of @math we compute lie in the nonzero positions of @math . We use the elimination tree associated with the block @math factorization to organize the parallel algorithm, and reduce the synchronization overhead by passing the data level by level along this tree using the technique of local buffers and relative indices. We demonstrate the efficiency of our parallel implementation by applying it to a discretized two dimensional Hamiltonian matrix. We analyze the performance of the parallel algorithm by examining its load balance and communication overhead, and show that our parallel implementation exhibits an excellent weak scaling on a large-scale high performance distributed-memory parallel machine. A number of problems in probability and statistics can be addressed using the multivariate normal (Gaussian) distribution. In the one-dimensional case, computing the probability for a given mean and variance simply requires the evaluation of the corresponding Gaussian density. In the @math -dimensional setting, however, it requires the inversion of an @math covariance matrix, @math , as well as the evaluation of its determinant, @math . In many cases, such as regression using Gaussian processes, the covariance matrix is of the form @math , where @math is computed using a specified covariance kernel which depends on the data and additional parameters (hyperparameters). The matrix @math is typically dense, causing standard direct methods for inversion and determinant evaluation to require @math work. This cost is prohibitive for large-scale modeling. Here, we show that for the most commonly used covariance functions, the matrix @math can be hierarchically factored into a product of block low-rank updates of the identity matrix, yielding an @math algorithm for inversion. More importantly, we show that this factorization enables the evaluation of the determinant @math , permitting the direct calculation of probabilities in high dimensions under fairly broad assumptions on the kernel defining @math . Our fast algorithm brings many problems in marginalization and the adaptation of hyperparameters within practical reach using a single CPU core. The combination of nearly optimal scaling in terms of problem size with high-performance computing resources will permit the modeling of previously intractable problems. We illustrate the performance of the scheme on standard covariance kernels.