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.

A Representation of Binary Matrices

Христина Костадинова, Красимир Йорджев - В статията се обсъжда представянето на произволна бинарна матрица с помощта на последователност от цели неотрицателни числа. Разгледани са някои предимства и недостатъци на това представяне като алтернатива на стандартното, общоприето представяне чрез двумерен масив. Показано е, че представянето на бинарните матрици с помощта на наредени n-торки от естествени числа води до по-бързи алгоритми и до съществена икономия на оперативна памет. Използуван е апарата на обектно-ориентираното програмиране със синтаксиса и семантиката на езика C++.

Fast pseudorandom generator based on packed matrices

Pseudorandom generators are a basic foundation of many cryptographic services and information security protocols. We propose a modification of a previously published matricial pseudorandom generator that significantly improves performance and security. The resulting generator is successfully compared to world class standards.

An optimized pseudorandom generator using packed matrices

Most cryptographic services and information security protocols require a dependable source of random data; pseudorandom generators are convenient and efficient for this application working as one of the basic foundation blocks on which to build the required security infrastructure. We propose a modification of a previously published matricial pseudorandom generator that significantly improves performance and security by using word packed matrices and modifying key scheduling and bit extraction schemes. The resulting generator is then successfully compared to world class standards.

Matrix Decomposition Methods for Data Mining : Computational Complexity and Algorithms

Matrix decompositions, where a given matrix is represented as a product of two other matrices, are regularly used in data mining. Most matrix decompositions have their roots in linear algebra, but the needs of data mining are not always those of linear algebra. In data mining one needs to have results that are interpretable -- and what is considered interpretable in data mining can be very different to what is considered interpretable in linear algebra. --- The purpose of this thesis is to study matrix decompositions that directly address the issue of interpretability. An example is a decomposition of binary matrices where the factor matrices are assumed to be binary and the matrix multiplication is Boolean. The restriction to binary factor matrices increases interpretability -- factor matrices are of the same type as the original matrix -- and allows the use of Boolean matrix multiplication, which is often more intuitive than normal matrix multiplication with binary matrices. Also several other decomposition methods are described, and the computational complexity of computing them is studied together with the hardness of approximating the related optimization problems. Based on these studies, algorithms for constructing the decompositions are proposed. Constructing the decompositions turns out to be computationally hard, and the proposed algorithms are mostly based on various heuristics. Nevertheless, the algorithms are shown to be capable of finding good results in empirical experiments conducted with both synthetic and real-world data.

The discrete Pascal transform and its applications

We introduce a new discrete polynomial transform constructed from the rows of Pascal’s triangle. The forward and inverse transforms are computed the same way in both the oneand two-dimensional cases, and the transform matrix can be factored into binary matrices for efficient hardware implementation. We conclude by discussing applications of the transform in

Mathematical Modeling of the Weaving Structure Design

Красимир Йорджев, Христина Костадинова - В работата се разглежда една релация на еквивалентност в множеството от всички квадратни бинарни матрици. Обсъдена е комбинаторната задача за намиране мощността и елементите на фактормножеството относно тази релация. Разгледана е и възможността за получаване на някои специални елементи на това фактормножество. Предложен е алгоритъм за решаване на поставените задачи. Получените в статията резултати намират приложение при описанието топологията на различните тъкачни структури.

Representing Equivalence Problems for Combinatorial Objects

Methods for representing equivalence problems of various combinatorial objects as graphs or binary matrices are considered. Such representations can be used for isomorphism testing in classification or generation algorithms. Often it is easier to consider a graph or a binary matrix isomorphism problem than to implement heavy algorithms depending especially on particular combinatorial objects. Moreover, there already exist well tested algorithms for the graph isomorphism problem (nauty) and the binary matrix isomorphism problem as well (Q-Extension). ACM Computing Classification System (1998): F.2.1, G.4.

Stability of curcumin microencapsulated by spray and freeze drying in binary and ternary matrices of maltodextrin, gum arabic and modified starch

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Blind steganalysis : a countermeasure for binary image steganography

In this paper, we propose a new blind steganalytic method to detect the presence of secret messages embedded in black and white images using the steganographic techniques. We start by extracting several sets of matrix, such as run length matrix, gap length matrix and pixel difference. We also apply characteristic function on these matrices to enhance their discriminative capabilities. Then we calculate the statistics which include mean, variance, kurtosis and skewness to form our feature sets. The presented empirical works demonstrate our proposed method can effectively detect three different types of steganography. This proves the universality of our proposed method as a blind steganalysis. In addition, the experimental results show our proposed method is capable of detecting small amount of the embedded message.

SYNTHESIS AND SPECTRAL CHARACTERISTICS OF DIVALENT SAMARIUM ACTIVATED BINARY FLUORIDES

A simple technique for preparation of powder binary fluorides activated with divalent samarium ions is described. The samarium impurity is introduced as samarium trifluoride SmF3 and hydrogen acts as the reducing agent to transform Sm3+ into Sm2+. Using this method, samarium has been stabilized in the divalent state in some fluorides: KMgF3, LiBaF3, BaBeF4, SrMgF4 and BaMgF4. Moreover, BaBeF4, SrMgF4 and BaMgF4 have never been activated with Sm2+ ions up to now. We also find that under the same synthetic conditions samarium can not be stabilized in the divalent state in some fluorides: KCaF3, CaBeF4 and CaMgF4, but the characteristic luminescence of trivalent samarium Sm3+ appears in these matrices. The emission and excitation spectra of samarium (Sm2+ and Sm3+) in these binary fluorides are presented and briefly discussed. The relationship between the oxidation state of samarium and the composition, the structure of matrices is also analyzed.

On infinite graphs and related matrices

This thesis Entitled On Infinite graphs and related matrices.ln the last two decades (iraph theory has captured wide attraction as a Mathematical model for any system involving a binary relation. The theory is intimately related to many other branches of Mathematics including Matrix Theory Group theory. Probability. Topology and Combinatorics . and has applications in many other disciplines..Any sort of study on infinite graphs naturally involves an attempt to extend the well known results on the much familiar finite graphs. A graph is completely determined by either its adjacencies or its incidences. A matrix can convey this information completely. This makes a proper labelling of the vertices. edges and any other elements considered, an inevitable process. Many types of labelling of finite graphs as Cordial labelling, Egyptian labelling, Arithmetic labeling and Magical labelling are available in the literature. The number of matrices associated with a finite graph are too many For a study ofthis type to be exhaustive. A large number of theorems have been established by various authors for finite matrices. The extension of these results to infinite matrices associated with infinite graphs is neither obvious nor always possible due to convergence problems. In this thesis our attempt is to obtain theorems of a similar nature on infinite graphs and infinite matrices. We consider the three most commonly used matrices or operators, namely, the adjacency matrix

Ionic liquids and other liquid matrices for sensitive MALDI MS analysis

Although liquid matrix-assisted laser desorption/ionization (MALDI) has been used in mass spectrometry (MS) since the early introduction of MALDI, its substantial lack of sensitivity compared to solid (crystalline) MALDI was for a long time a major hurdle to its analytical competitiveness. In the last decade, this situation has changed with the development of new sensitive liquid matrices, which are often based on a binary matrix acid/base system. Some of these matrices were inspired by the recent progress in ionic liquid research, while others were developed from revisiting previous liquid MALDI work as well as from a combination of these two approaches. As a result, two high-performing liquid matrix classes have been developed, the ionic liquid matrices (ILMs) and the liquid support matrices (LSMs), now allowing MS measurements at a sensitivity level that is very close to the level of solid MALDI and in some cases even surpasses it. This chapter provides some basic information on a selection of highly successful representatives of these new liquid matrices and describes in detail how they are made and applied in MALDI MS analysis.

Comparison of different clean-up procedures for the determination of N-methylcarbamate insecticides in vegetable matrices by high-performance liquid chromatography with UV detection

Several clean-up procedures which included the use of glass chromatography columns (silica gel, alumina, Florisil, silanized Celite-charcoal), Sep-Pak cartridges and standard solutions were compared for the determination of the following N-methylcarbamate (NMC) insecticides: aldicarb, carbaryl, carbofuran, methomyl and propoxur. According to recovery results of the compounds after elution in a glass column, the most efficient systems employed 4.6% deactivated alumina and a silanized Celite-charcoal (4:1) as adsorbents, using dichloromethane-methanol (99:1) and toluene-acetonitrile (75:25) mixtures, respectively, as binary eluents. The recoveries of the compounds studied varied from 84 to 120%. Comparable recoveries (75-100%) for Sep-Pak cartridges in normal phase (NH2, CN) and reversed phase (C-8) were observed. Different temperatures were tested during the concentration step in a rotary evaporator, and we verified a strong influence of this parameter on the stability of some compounds, such as carbofuran and carbaryl. Recovery studies employing the best clean up procedures were performed at the Brazilian agricultural level in potato and carrot samples; Validation methodology of the US Food and Drug Administration was adapted for the N-methylcarbamate analysis. Their recoveries ranged between 79 and 93% with coefficients of variation of 2.3-8%. (C) 1998 Elsevier B.V. B.V.

Microencapsulation of turmeric oleoresin in binary and ternary blends of gum arabic, maltodextrin and modified starch

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)