Regularization parameter estimation for large-scale Tikhonov regularization using a priori information

Solutions of numerically ill-posed least squares problems for A∈R^m×n by Tikhonov regularization are considered. For D∈R^p×n, the Tikhonov regularized least squares functional is given by where matrix W is a weighting matrix and is given. Given a priori estimates on the covariance structure of errors in the measurement data , the weighting matrix may be taken as which is the inverse covariance matrix of the mean 0 normally distributed measurement errors in . If in addition is an estimate of the mean value of , and σ is a suitable statistically-chosen value, J evaluated at its minimizer approximately follows a χ² distribution with degrees of freedom. Using the generalized singular value decomposition of the matrix pair , σ can then be found such that the resulting J follows this χ² distribution. But the use of an algorithm which explicitly relies on the direct solution of the problem obtained using the generalized singular value decomposition is not practical for large-scale problems. Instead an approach using the Golub-Kahan iterative bidiagonalization of the regularized problem is presented. The original algorithm is extended for cases in which is not available, but instead a set of measurement data provides an estimate of the mean value of . The sensitivity of the Newton algorithm to the number of steps used in the Golub-Kahan iterative bidiagonalization, and the relation between the size of the projected subproblem and σ are discussed. Experiments presented contrast the efficiency and robustness with other standard methods for finding the regularization parameter for a set of test problems and for the restoration of a relatively large real seismic signal. An application for image deblurring also validates the approach for large-scale problems. It is concluded that the presented approach is robust for both small and large-scale discretely ill-posed least squares problems.     

Invariance properties in the root sensitivity of time-delay systems with double imaginary roots

If is an eigenvalue of a time-delay system for the delay τ₀ then is also an eigenvalue for the delays τ_k?τ₀+k2π/ω, for any k∈Z. We investigate the sensitivity, periodicity and invariance properties of the root for the case that is a double eigenvalue for some τ_k. It turns out that under natural conditions (the condition that the root exhibits the completely regular splitting property if the delay is perturbed), the presence of a double imaginary root for some delay τ₀ implies that is a simple root for the other delays τ_k, k≠0. Moreover, we show how to characterize the root locus around . The entire local root locus picture can be completely determined from the square root splitting of the double root. We separate the general picture into two cases depending on the sign of a single scalar constant; the imaginary part of the first coefficient in the square root expansion of the double eigenvalue.     

On generalized middle-level problem

Let be the subgraph of the hypercube Q_n induced by levels between k and n-k, where n?2k+1 is odd. The well-known middle-level conjecture asserts that is Hamiltonian for all k?1. We study this problem in for fixed k. It is known that and are Hamiltonian for all odd n?3. In this paper we prove that also is Hamiltonian for all odd n?5, and we conjecture that is Hamiltonian for every k?0 and every odd n?2k+1.     

Pentagons: A weakly relational abstract domain for the efficient validation of array accesses

We introduce Pentagons (), a weakly relational numerical abstract domain useful for the validation of array accesses in byte-code and intermediate languages (IL). This abstract domain captures properties of the form of . It is more precise than the well known Interval domain, but it is less precise than the Octagon domain.The goal of is to be a lightweight numerical domain useful for adaptive static analysis, where is used to quickly prove the safety of most array accesses, restricting the use of more precise (but also more expensive) domains to only a small fraction of the code.We implemented the abstract domain in , a generic abstract interpreter for.NET assemblies. Using it, we were able to validate 83% of array accesses in the core runtime library in a little bit more than 3 minutes.     

On domination number of Cartesian product of directed cycles

Let γ(G) denote the domination number of a digraph G and let Cm□Cn denote the Cartesian product of Cm and Cn, the directed cycles of length m,n?2. In this paper, we determine the exact values: γ(C₂□Cn)=n; γ(C₃□Cn)=n if , otherwise, γ(C₃□Cn)=n+1; if , otherwise, .     

Learning of event-recording automata

In regular inference, a regular language is inferred from answers to a finite set of membership queries, each of which asks whether the language contains a certain word. One of the most well-known regular inference algorithms is the L^∗ algorithm due to Dana Angluin. However, there are almost no extensions of these algorithms to the setting of timed systems. We extend Angluin’s algorithm for on-line learning of regular languages to the setting of timed systems. Since timed automata can freely use an arbitrary number of clocks, we restrict our attention to systems that can be described by deterministic event-recording automata (DERAs). We present three algorithms, , and , for inference of DERAs. In and , we further restrict event-recording automata to be event-deterministic in the sense that each state has at most one outgoing transition per action; learning such an automaton becomes significantly more tractable. The algorithm builds on , by attempts to construct a smaller (in number of locations) automaton. Finally, is a learning algorithm for a full class of deterministic event-recording automata, which infers a so called simple DERA, which is similar in spirit to the region graph.     

Spectral radius minimization for optimal average consensus and output feedback stabilization

In this paper, we consider two problems which can be posed as spectral radius minimization problems. Firstly, we consider the fastest average agreement problem on multi-agent networks adopting a linear information exchange protocol. Mathematically, this problem can be cast as finding an optimal such that x(k+1)=Wx(k), , and W∈S(E). Here, is the value possessed by the agents at the kth time step, is an all-one vector and S(E) is the set of real matrices in with zeros at the same positions specified by a network graph G(V,E), where V is the set of agents and E is the set of communication links between agents. The optimal W is such that the spectral radius is minimized. To this end, we consider two numerical solution schemes: one using the qth-order spectral norm (2-norm) minimization (q-SNM) and the other gradient sampling (GS), inspired by the methods proposed in [Burke, J., Lewis, A., & Overton, M. (2002). Two numerical methods for optimizing matrix stability. Linear Algebra and its Applications, 351-352, 117-145; Xiao, L., & Boyd, S. (2004). Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1), 65-78]. In this context, we theoretically show that when E is symmetric, i.e. no information flow from the ith to the jth agent implies no information flow from the jth to the ith agent, the solution from the 1-SNM method can be chosen to be symmetric and is a local minimum of the function . Numerically, we show that the q-SNM method performs much better than the GS method when E is not symmetric. Secondly, we consider the famous static output feedback stabilization problem, which is considered to be a hard problem (some think NP-hard): for a given linear system (A,B,C), find a stabilizing control gain K such that all the real parts of the eigenvalues of A+BKC are strictly negative. In spite of its computational complexity, we show numerically that q-SNM successfully yields stabilizing controllers for several benchmark problems with little effort.     

A compact data structure for representing a dynamic multiset

We develop a data structure for maintaining a dynamic multiset that uses bits and O(1) words, in addition to the space required by the n elements stored, supports searches in worst-case time and updates in amortized time. Compared to earlier data structures, we improve the space requirements from O(n) bits to bits, but the running time of updates is amortized, not worst-case.     

Testing juntas

We show that a boolean valued function over n variables, where each variable ranges in an arbitrary probability space, can be tested for the property of depending on only J of them using a number of queries that depends only polynomially on J and the approximation parameter ε. We present several tests that require a number of queries that is polynomial in J and linear in ε⁻¹. We show a non-adaptive test that has one-sided error, an adaptive version of it that requires fewer queries, and a non-adaptive two-sided version of the test that requires the least number of queries. We also show a two-sided non-adaptive test that applies to functions over n boolean variables, and has a more compact analysis.We then provide a lower bound of on the number of queries required for the non-adaptive testing of the above property; a lower bound of for adaptive algorithms naturally follows from this. In establishing this lower bound we also prove a result about random walks on the group Z^q₂ that may be interesting in its own right. We show that for some , the distributions of the random walk at times t and t+2 are close to each other, independently of the step distribution of the walk.We also discuss related questions. In particular, when given in advance a known J-junta function , we show how to test a function for the property of being identical to up to a permutation of the variables, in a number of queries that is polynomial in J and ε⁻¹.     

On the lower bounds of the second order nonlinearities of some Boolean functions

The rth order nonlinearity of a Boolean function is an important cryptographic criterion in analyzing the security of stream as well as block ciphers. It is also important in coding theory as it is related to the covering radius of the Reed-Muller code R(r,n). In this paper we deduce the lower bounds of the second order nonlinearities of the following two types of Boolean functions:

1.

with d=2^2r+2^r+1 and , where n=6r.

2.

, where x,y∈F_2^t,n=2t,n?6 and i is an integer such that 1?i<t,gcd(2^t-1,2ⁱ+1)=1.

For some λ, the functions of the first type are bent functions, whereas Boolean functions of the second type are all bent functions, i.e., they possess the maximum first order nonlinearity. It is demonstrated that in some cases our bounds are better than the previously obtained bounds.     

Efficient approximation algorithms for shortest cycles in undirected graphs

We describe a simple combinatorial approximation algorithm for finding a shortest (simple) cycle in an undirected graph. Given an adjacency-list representation of an undirected graph G with n vertices and unknown girth k, our algorithm returns with high probability a cycle of length at most 2k for even k and 2k+2 for odd k, in time . Thus, in general, it yields a approximation. For a weighted, undirected graph, with non-negative edge weights in the range {1,2,…,M}, we present a simple combinatorial 2-approximation algorithm for a minimum weight (simple) cycle that runs in time O(n²logn(logn+logM)).     

Bottleneck flows in unit capacity networks

The bottleneck network flow problem (BNFP) is a generalization of several well-studied bottleneck problems such as the bottleneck transportation problem (BTP), bottleneck assignment problem (BAP), bottleneck path problem (BPP), and so on. The BNFP can easily be solved as a sequence of O(logn) maximum flow problems on almost unit capacity networks. We observe that this algorithm runs in O(min{m3/2,n2/3m}logn) time by showing that the maximum flow problem on an almost unit capacity graph can be solved in O(min{m3/2,n2/3m}) time. We then propose a faster algorithm to solve the unit capacity BNFP in time, an improvement by a factor of at least . For dense graphs, the improvement is by a factor of . On unit capacity simple graphs, we show that BNFP can be solved in time, an improvement by a factor of . As a consequence we have an algorithm for the BTP with unit arc capacities.