Patterns in permuted binary matrices

Reorganizing a dataset so that its hidden structure can be observed is useful in any data analysis task. For example, detecting a regularity in a dataset helps us to interpret the data, compress the data, and explain the processes behind the data. We study datasets that come in the form of binary matrices (tables with 0s and 1s). Our goal is to develop automatic methods that bring out certain patterns by permuting the rows and columns. We concentrate on the following patterns in binary matrices: consecutive-ones (C1P), simultaneous consecutive-ones (SC1P), nestedness, k-nestedness, and bandedness. These patterns reflect specific types of interplay and variation between the rows and columns, such as continuity and hierarchies. Furthermore, their combinatorial properties are interlinked, which helps us to develop the theory of binary matrices and efficient algorithms. Indeed, we can detect all these patterns in a binary matrix efficiently, that is, in polynomial time in the size of the matrix. Since real-world datasets often contain noise and errors, we rarely witness perfect patterns. Therefore we also need to assess how far an input matrix is from a pattern: we count the number of flips (from 0s to 1s or vice versa) needed to bring out the perfect pattern in the matrix. Unfortunately, for most patterns it is an NP-complete problem to find the minimum distance to a matrix that has the perfect pattern, which means that the existence of a polynomial-time algorithm is unlikely. To find patterns in datasets with noise, we need methods that are noise-tolerant and work in practical time with large datasets. The theory of binary matrices gives rise to robust heuristics that have good performance with synthetic data and discover easily interpretable structures in real-world datasets: dialectical variation in the spoken Finnish language, division of European locations by the hierarchies found in mammal occurrences, and co-occuring groups in network data. In addition to determining the distance from a dataset to a pattern, we need to determine whether the pattern is significant or a mere occurrence of a random chance. To this end, we use significance testing: we deem a dataset significant if it appears exceptional when compared to datasets generated from a certain null hypothesis. After detecting a significant pattern in a dataset, it is up to domain experts to interpret the results in the terms of the application.

Some nonstandard error analysis of discontinuous Galerkin methods for elliptic problems

An a priori error analysis of discontinuous Galerkin methods for a general elliptic problem is derived under a mild elliptic regularity assumption on the solution. This is accomplished by using some techniques from a posteriori error analysis. The model problem is assumed to satisfy a GAyenrding type inequality. Optimal order L (2) norm a priori error estimates are derived for an adjoint consistent interior penalty method.

A maximal operator, Carleson's embedding, and tent spaces for vector-valued functions

This thesis is concerned with the area of vector-valued Harmonic Analysis, where the central theme is to determine how results from classical Harmonic Analysis generalize to functions with values in an infinite dimensional Banach space. The work consists of three articles and an introduction. The first article studies the Rademacher maximal function that was originally defined by T. Hytönen, A. McIntosh and P. Portal in 2008 in order to prove a vector-valued version of Carleson's embedding theorem. The boundedness of the corresponding maximal operator on Lebesgue-(Bochner) -spaces defines the RMF-property of the range space. It is shown that the RMF-property is equivalent to a weak type inequality, which does not depend for instance on the integrability exponent, hence providing more flexibility for the RMF-property. The second article, which is written in collaboration with T. Hytönen, studies a vector-valued Carleson's embedding theorem with respect to filtrations. An earlier proof of the dyadic version assumed that the range space satisfies a certain geometric type condition, which this article shows to be also necessary. The third article deals with a vector-valued generalizations of tent spaces, originally defined by R. R. Coifman, Y. Meyer and E. M. Stein in the 80's, and concerns especially the ones related to square functions. A natural assumption on the range space is then the UMD-property. The main result is an atomic decomposition for tent spaces with integrability exponent one. In order to suit the stochastic integrals appearing in the vector-valued formulation, the proof is based on a geometric lemma for cones and differs essentially from the classical proof. Vector-valued tent spaces have also found applications in functional calculi for bisectorial operators. In the introduction these three themes come together when studying paraproduct operators for vector-valued functions. The Rademacher maximal function and Carleson's embedding theorem were applied already by Hytönen, McIntosh and Portal in order to prove boundedness for the dyadic paraproduct operator on Lebesgue-Bochner -spaces assuming that the range space satisfies both UMD- and RMF-properties. Whether UMD implies RMF is thus an interesting question. Tent spaces, on the other hand, provide a method to study continuous time paraproduct operators, although the RMF-property is not yet understood in the framework of tent spaces.

A Circuit-Based Proof of Toda′s Theorem

We present a simple proof of Toda′s result (Toda (1989), in "Proceedings, 30th Annual IEEE Symposium on Foundations of Computer Science," pp. 514-519), which states that circled plus P is hard for the Polynomial Hierarchy under randomized reductions. Our approach is circuit-based in the sense that we start with uniform circuit definitions of the Polynomial Hierarchy and apply the Valiant-Vazirani lemma on these circuits (Valiant and Vazirani (1986), Thoeret. Comput. Sci.47, 85-93).

Stability analysis of stochastically parametered nonconservative columns

Nonconservatively loaded columns. which have stochastically distributed material property values and stochastic loadings in space are considered. Young's modulus and mass density are treated to constitute random fields. The support stiffness coefficient and tip follower load are considered to be random variables. The fluctuations of external and distributed loadings are considered to constitute a random field. The variational formulation is adopted to get the differential equation and boundary conditions. The non self-adjoint operators are used at the boundary of the regularity domain. The statistics of vibration frequencies and modes are obtained using the standard perturbation method, by treating the fluctuations to be stochastic perturbations. Linear dependence of vibration and stability parameters over property value fluctuations and loading fluctuations are assumed. Bounds for the statistics of vibration frequencies are obtained. The critical load is first evaluated for the averaged problem and the corresponding eigenvalue statistics are sought. Then, the frequency equation is employed to transform the eigenvalue statistics to critical load statistics. Specialization of the general procedure to Beck, Leipholz and Pfluger columns is carried out. For Pfluger column, nonlinear transformations are avoided by directly expressing the critical load statistics in terms of input variable statistics.

Stability of stochastic Leipholz column with stochastic loading

The Leipholz column which is having the Young modulus and mass per unit length as stochastic processes and also the distributed tangential follower load behaving stochastically is considered. The non self-adjoint differential equation and boundary conditions are considered to have random field coefficients. The standard perturbation method is employed. The non self-adjoint operators are used within the regularity domain. Full covariance structure of the free vibration eigenvalues and critical loads is derived in terms of second order properties of input random fields characterizing the system parameter fluctuations. The mean value of critical load is calculated using the averaged problem and the corresponding eigenvalue statistics are sought. Through the frequency equation a transformation is done to yield load parameter statistics. A numerical study incorporating commonly observed correlation models is reported which illustrates the full potentials of the derived expressions.

Dehydrophenylalanine zippers: strong helix-helix clamping through a network of weak interactions

A decapeptide Boc-L-Ala-(DeltaPhe)(4)-L-Ala-(DeltaPhe)(3)-Gly-OMe (Peptide I) was synthesized to study the preferred screw sense of consecutive alpha,beta-dehydrophenylalanine (DeltaPhe) residues. Crystallographic and CD studies suggest that, despite the presence of two L-Ala residues in the sequence, the decapeptide does not have a preferred screw sense. The peptide crystallizes with two conformers per asymmetric unit, one of them a slightly distorted right-handed 3(10)-helix (X) and the other a left-handed 3(10)-helix (Y) with X and Y being antiparallel to each other. An unanticipated and interesting observation is that in the solid state, the two shape-complement molecules self-assemble and interact with an extensive network of C-H...O hydrogen bonds and pi-pi interactions, directed laterally to the helix axis with amazing regularity. Here, we present an atomic resolution picture of the weak interaction mediated mutual recognition of two secondary structural elements and its possible implication in understanding the specific folding of the hydrophobic core of globular proteins and exploitation in future work on de novo design.

Nonlinear measures of respiration: Respiratory irregularity and increased chaos of respiration in patients with panic disorder

Background. Respiratory irregularity has been previously reported in patients with panic disorder using time domain measures. However, the respiratory signal is not entirely linear and a few previous studies used approximate entropy (APEN), a measure of regularity of time series. We have been studying APEN and other nonlinear measures including a measure of chaos, the largest Lyapunov exponent (LLE) of heart rate time series, in some detail. In this study, we used these measures of respiration to compare normal controls (n = 18) and patients with panic disorder (n = 22) in addition to the traditional time domain measures of respiratory rate and tidal volume. Methods: Respiratory signal was obtained by the Respitrace system using a thoracic and an abdominal belt, which was digitized at 500 Hz. Later, the time series were constructed at 4 Hz, as the highest frequency in this signal is limited to 0.5 Hz. We used 256 s of data (1,024 points) during supine and standing postures under normal breathing and controlled breathing at 12 breaths/min. Results: APEN was significantly higher in patients in standing posture during normal as well as controlled breathing (p = 0.002 and 0.02, respectively). LLE was also significantly higher in standing posture during normal breathing (p = 0.009). Similarly, the time domain measures of standard deviations and the coefficient of variation (COV) of tidal volume (TV) were significantly higher in the patient group (p = 0.02 and 0.004, respectively). The frequency of sighs was also higher in the patient group in standing posture (p = 0.02). In standing posture, LLE (p < 0.05) as well as APEN (p < 0.01) contributed significantly toward the separation of the two groups over and beyond the linear measure, i.e. the COV of TV. Conclusion: These findings support the previously described respiratory irregularity in patients with panic disorder and also illustrate the utility of nonlinear measures such as APEN and LLE as additional measures toward a better understanding of the abnormalities of respiratory physiology in similar patient populations as the correlation between LLE, APEN and some of the time domain measures only explained up to 50-60% of the variation. Copyright (C) 2002 S. Karger AG, Basel.

A note on surface water waves for finite depth in the presence of an ice-cover

A class of I boundary value problems involving propagation of two-dimensional surface water waves, associated with water of uniform finite depth, against a plane vertical wave maker is investigated under the assumption that the surface is covered by a thin sheet of ice. It is assumed that the ice-cover behaves like a thin isotropic elastic plate. Then the problems under consideration lead to those of solving the two-dimensional Laplace equation in a semi-infinite strip, under Neumann boundary conditions on the vertical boundary as well as on one of the horizontal boundaries, representing the bottom of the fluid region, and a condition involving upto fifth order derivatives of the unknown function on the top horizontal ice-covered boundary, along with the two appropriate edge-conditions, at the ice-covered corner, ensuring the uniqueness of the solutions. The mixed boundary value problems are solved completely, by exploiting the regularity property of the Fourier cosine transform.

An operator-splitting Galerkin/SUPG finite element method for population balance equations : stability and convergence

We present a heterogeneous finite element method for the solution of a high-dimensional population balance equation, which depends both the physical and the internal property coordinates. The proposed scheme tackles the two main difficulties in the finite element solution of population balance equation: (i) spatial discretization with the standard finite elements, when the dimension of the equation is more than three, (ii) spurious oscillations in the solution induced by standard Galerkin approximation due to pure advection in the internal property coordinates. The key idea is to split the high-dimensional population balance equation into two low-dimensional equations, and discretize the low-dimensional equations separately. In the proposed splitting scheme, the shape of the physical domain can be arbitrary, and different discretizations can be applied to the low-dimensional equations. In particular, we discretize the physical and internal spaces with the standard Galerkin and Streamline Upwind Petrov Galerkin (SUPG) finite elements, respectively. The stability and error estimates of the Galerkin/SUPG finite element discretization of the population balance equation are derived. It is shown that a slightly more regularity, i.e. the mixed partial derivatives of the solution has to be bounded, is necessary for the optimal order of convergence. Numerical results are presented to support the analysis.

Analysis of an Interior Penalty Method for Fourth Order Problems on Polygonal Domains

Error analysis for a stable C (0) interior penalty method is derived for general fourth order problems on polygonal domains under minimal regularity assumptions on the exact solution. We prove that this method exhibits quasi-optimal order of convergence in the discrete H (2), H (1) and L (2) norms. L (a) norm error estimates are also discussed. Theoretical results are demonstrated by numerical experiments.

A fully discrete C-0 interior penalty Galerkin approximation of the extended Fisher-Kolmogorov equation

A fully discrete C-0 interior penalty finite element method is proposed and analyzed for the Extended Fisher-Kolmogorov (EFK) equation u(t) + gamma Delta(2)u - Delta u + u(3) - u = 0 with appropriate initial and boundary conditions, where gamma is a positive constant. We derive a regularity estimate for the solution u of the EFK equation that is explicit in gamma and as a consequence we derive a priori error estimates that are robust in gamma. (C) 2013 Elsevier B.V. All rights reserved.

Information and Efficiency in the Nervous System-A Synthesis

In systems biology, questions concerning the molecular and cellular makeup of an organism are of utmost importance, especially when trying to understand how unreliable components-like genetic circuits, biochemical cascades, and ion channels, among others-enable reliable and adaptive behaviour. The repertoire and speed of biological computations are limited by thermodynamic or metabolic constraints: an example can be found in neurons, where fluctuations in biophysical states limit the information they can encode-with almost 20-60% of the total energy allocated for the brain used for signalling purposes, either via action potentials or by synaptic transmission. Here, we consider the imperatives for neurons to optimise computational and metabolic efficiency, wherein benefits and costs trade-off against each other in the context of self-organised and adaptive behaviour. In particular, we try to link information theoretic (variational) and thermodynamic (Helmholtz) free-energy formulations of neuronal processing and show how they are related in a fundamental way through a complexity minimisation lemma.

Vorticity moments in four numerical simulations of the 3D Navier-Stokes equations

The issue of intermittency in numerical solutions of the 3D Navier-Stokes equations on a periodic box 0, L](3) is addressed through four sets of numerical simulations that calculate a new set of variables defined by D-m(t) = (pi(-1)(0) Omega(m))(alpha m) for 1 <= m <= infinity where alpha(m) = 2m/(4m - 3) and Omega(m)(t)](2m) = L-3 integral(v) vertical bar omega vertical bar(2m) dV with pi(0) = vL(-2). All four simulations unexpectedly show that the D-m are ordered for m = 1,..., 9 such that Dm+1 < D-m. Moreover, the D-m squeeze together such that Dm+1/D-m NE arrow 1 as m increases. The values of D-1 lie far above the values of the rest of the D-m, giving rise to a suggestion that a depletion of nonlinearity is occurring which could be the cause of Navier-Stokes regularity. The first simulation is of very anisotropic decaying turbulence; the second and third are of decaying isotropic turbulence from random initial conditions and forced isotropic turbulence at fixed Grashof number respectively; the fourth is of very-high-Reynolds-number forced, stationary, isotropic turbulence at up to resolutions of 4096(3).

Simultaneous Perturbation Newton Algorithms for Simulation Optimization

We present a new Hessian estimator based on the simultaneous perturbation procedure, that requires three system simulations regardless of the parameter dimension. We then present two Newton-based simulation optimization algorithms that incorporate this Hessian estimator. The two algorithms differ primarily in the manner in which the Hessian estimate is used. Both our algorithms do not compute the inverse Hessian explicitly, thereby saving on computational effort. While our first algorithm directly obtains the product of the inverse Hessian with the gradient of the objective, our second algorithm makes use of the Sherman-Morrison matrix inversion lemma to recursively estimate the inverse Hessian. We provide proofs of convergence for both our algorithms. Next, we consider an interesting application of our algorithms on a problem of road traffic control. Our algorithms are seen to exhibit better performance than two Newton algorithms from a recent prior work.