Using underapproximations for sparse nonnegative matrix factorization

Nonnegative matrix factorization consists in (approximately) factorizing a nonnegative data matrix by the product of two low-rank nonnegative matrices. It has been successfully applied as a data analysis technique in numerous domains, e.g., text mining, image processing, microarray data analysis, collaborative filtering, etc.We introduce a novel approach to solve NMF problems, based on the use of an underapproximation technique, and show its effectiveness to obtain sparse solutions. This approach, based on Lagrangian relaxation, allows the resolution of NMF problems in a recursive fashion. We also prove that the underapproximation problem is NP-hard for any fixed factorization rank, using a reduction of the maximum edge biclique problem in bipartite graphs.We test two variants of our underapproximation approach on several standard image datasets and show that they provide sparse part-based representations with low reconstruction error. Our results are comparable and sometimes superior to those obtained by two standard sparse nonnegative matrix factorization techniques.     

限制树宽图上的有界聚类

有界聚类问题源于II3M研究院开发的一个分布式流处理系统,即S系统。问题的输入是一个点赋权和边赋权的无向图,并指定若干个称为终端的顶点。称顶点集合的一个子集为一个子类。子类中所有顶点的权和加上该子类边界上所有边的权和称为该子类的费用。有界聚类问题是要得到所有顶点的一个聚类,要求每个子类的费用不超过给定预算召,每个子类至多包含一个终端,并使得所有子类的总费用最小。对于限制树宽图上的有界聚类问题,给出了拟多项式时间精确算法。利用取整的技巧对该算法进行修正,可在多项式时间之内得到(1+ε)-近似解,其中每个子类的费用不超过(1+ε)B,:是任意小的正数。如果进一步要求每个子类恰好包含一个终端,则所给算法可在多项式时间之内得到(1+ε)-近似解,其中每个子类的费用不超过(2+ε)B。     

Bounded synthesis

A fundamental challenge in the synthesis of reactive systems is the size of the search space: the number of candidate implementations of a temporal specification is typically superexponential or even, for distributed system architectures, infinite. In this article, we introduce the bounded synthesis approach, which makes it possible to traverse this immense search space in a structured manner. We fix a bound on a system parameter, such as the number of states, and limit the search to those implementations that fall below the bound. By incrementally expanding the search to larger bounds, we maintain completeness, while orienting the search towards the simplest (and often most useful) solutions. The technical backbone of this solution is a novel translation from formulas of linear-time temporal logic to sequences of safety tree automata, which are guaranteed to underapproximate the specification and to eventually become emptiness-equivalent. Bounded synthesis is applicable to the entire range of synthesis problems, from individual processes to synchronous and asynchronous distributed systems, to systems with additional design constraints, such as symmetry. We include experimental results from a SMT-based implementation, which demonstrate that bounded synthesis solves many synthesis problems that were previously considered intractable.     

Bounded time-stamps

Summary Time-stamps are labels which a system adds to its data items. These labels enable the system to keep track of the temporal precedence relations among its data elements. Many distributed protocols and some applications use the natural numbers as time-stamps. The natural numbers however are not useful for bounded protocols. In this paper we develop a theory ofbounded time-stamps. Time-stamp schemes are defined and the complexity of their implementation is analyzed. This indicates a direction for developing a general tool for converting time-stamp based protocols to bounded protocols. Amos Israeli received his B.Sc. in Mathematics and Physics from Hebrew University in 1976, and his M.Sc. and D.Sc. in Computer Science from the Weizmann Institute in 1980 and the Technion in 1985, respectively. Currently he is a senior lecturer at the Tlectrical Engineering Department at the Technion. Prior to this he was a postdoctoral fellow at the Aiken Computation Laboratory at Harvard. His research interests are in Parallel and Distributed Computing and in Robotics. In particular he has worked on the design and analysis of Wait-Free and Self-Stabilizing distributed protocols. Ming Li received his M.S. and Ph.D. in Computer Science from Wayne State University in 1980 and Cornell University 1985, respectively. Currently he is an associate professor at the Computer Science Department at the University of Waterloo. His research interests are in Theory of Computing, Kolmogorov Complexity, and Machine Learning.Supported in part by the Weizmann fellowship and NSF Grant DCR-86-00379Supported in part by ONR Grant N00014-85-k-0445 and Army Research Office Grant DAAL03-86-K-0171 at Harvard University, by NSF Grant kDCR-86-06366 at Ohio State University, and by NSERC Operating Grant OGP0036747. Most of this work was done when the authors were at Aiken Computation Laboratory at Harvard University. The authors also acknowledge the hospitality of the computer science department at York University, Canada     

Bounded Evaluation: Querying Big Data with Bounded Resources

Machine Intelligence Research - This work aims to reduce queries on big data to computations on small data, and hence make querying big data possible under bounded resources. A query Q is boundedly...     

Bounded DOL languages

For an alphabet A and a morphism h : A¹ → A¹, the set of words w such that the DOL language L(A, h, w) is a BOUNDED language is shown to be B¹, where B is an effectively computable subset of A. Consequently, BOUNDEDNESS is decidable for DOL languages. The result depends on the authors' recent results on periodic DOL languages. Interpretation of the result for polynomially bounded DOL languages is also considered.     

Bounded MSC communication

Message sequence charts (MSCs) and high-level message sequence charts (HMSCs) are popular formalisms for the specification of communication protocols between asynchronous processes. An important concept in this context is the size of the communication buffers used between processes. Since real systems impose limitations on the capacity (or speed) of communication links, we ask whether a given HMSC can be implemented with respect to a given buffer size imposed by the environment. We introduce four different measures for buffer sizes and investigate for each of these measures the complexity of deciding whether a given MSC (or HMSC, or nested MSC) satisfies a given bound on the buffer size. The complexity of these problems varies between the classes P, NP, and coNP.     

Bounded memory protocols

It is well-known that the Dolev–Yao adversary is a powerful adversary. Besides acting as the network, intercepting, decomposing, composing and sending messages, he can remember as much information as he needs. That is, his memory is unbounded. We recently proposed a weaker Dolev–Yao like adversary, which also acts as the network, but whose memory is bounded. We showed that this Bounded Memory Dolev–Yao adversary, when given enough memory, can carry out many existing protocol anomalies. In particular, the known anomalies arise for bounded memory protocols, where although the total number of sessions is unbounded, there are only a bounded number of concurrent sessions and the honest participants of the protocol cannot remember an unbounded number of facts or an unbounded number of nonces at a time. This led us to the question of whether it is possible to infer an upper-bound on the memory required by the Dolev–Yao adversary to carry out an anomaly from the memory restrictions of the bounded protocol. This paper answers this question negatively (Theorem 8).     

Bounded hairpin completion

Hairpin completion is a formal operation inspired from biochemistry. Here we consider a restricted variant of hairpin completion called bounded hairpin completion. Applied to a word encoding a single stranded molecule x such that either a suffix or a prefix of x is complementary to a subword of x, hairpin completion produces a new word z, which is a prolongation of x to the right or to the left by annealing.Although this operation is a purely mathematical one and the biological reality is just a source of inspiration, it seems rather unrealistic to impose no restriction on the length of the prefix or suffix added by the hairpin completion. The restriction considered here concerns the length of all prefixes and suffixes that are added to the current word by hairpin completion. They cannot be longer than a given constant. Closure properties of some classes of formal languages under the non-iterated and iterated bounded hairpin completion are investigated. We consider the bounded hairpin completion distance between two words and generalize this distance to languages and discuss algorithms for computing them. Finally also the inverse operation, namely bounded hairpin reduction, as well as the set of all primitive bounded hairpin roots of a regular language are considered.     

Bounded Unpopularity Matchings

We investigate the following problem: given a set of jobs and a set of people with preferences over the jobs, what is the optimal way of matching people to jobs? Here we consider the notion of popularity. A matching M is popular if there is no matching M′ such that more people prefer M′ to M than the other way around. Determining whether a given instance admits a popular matching and, if so, finding one, was studied by Abraham et al. (SIAM J. Comput. 37(4):1030–1045, 2007). If there is no popular matching, a reasonable substitute is a matching whose unpopularity is bounded. We consider two measures of unpopularity—unpopularity factor denoted by u(M) and unpopularity margin denoted by g(M). McCutchen recently showed that computing a matching M with the minimum value of u(M) or g(M) is NP-hard, and that if G does not admit a popular matching, then we have u(M)≥2 for all matchings M in G.Here we show that a matching M that achieves u(M)=2 can be computed in \(O(m\sqrt{n})\) time (where m is the number of edges in G and n is the number of nodes) provided a certain graph H admits a matching that matches all people. We also describe a sequence of graphs: H=H ₂,H ₃,…,H _k such that if H _k admits a matching that matches all people, then we can compute in \(O(km\sqrt{n})\) time a matching M such that u(M)≤k?1 and \(g(M)\le n(1-\frac{2}{k})\). Simulation results suggest that our algorithm finds a matching with low unpopularity in random instances.     

Bounded self-stabilizing Petri nets

We investigate the property of self-stabilization in bounded Petri nets. We give characterizations for both self-stabilizing bounded ordinary Petri nets (i.e., Petri nets without multiple arcs) and self-stabilizing bounded general Petri nets (i.e., Petri nets with multiple arcs). These characterizations allow us to determine the complexity of deciding self-stabilization for each of these classes. In particular, we show the self-stabilization problem to be PTIME-complete for bounded ordinary Petri nets and PSPACE-complete for bounded general Petri nets.Louis Rosier passed away on May 6, 1991, while this paper was under review     

Bounded Rationality and Control

Automation and Remote Control - A rationality-bounding condition is formulated: when jointly solving control, communication, and computing problems (С $$ {}^{3} $$ ), an optimal solution...     

Balancing Bounded Treewidth Circuits

We use algorithmic tools for graphs of small treewidth to address questions in complexity theory. For our main construction, we prove that multiplicatively disjoint arithmetic circuits of size n ^O(1) and treewidth k can be simulated by bounded fan-in arithmetic formulas of depth O(k ²logn). From this we derive an analogous statement for syntactically multilinear arithmetic circuits, which strengthens the central theorem of M. Mahajan and B.V.R. Rao (Proc. 33rd International Symposium on Mathematical Foundations of Computer Science, vol. 5162, pp. 455–466, 2008). We show our main construction has the following three applications:

• Bounded width arithmetic circuits of size n ^O(1) can be balanced to depth O(logn), provided chains of iterated multiplication in the circuit are of length O(1).
• Boolean bounded fan-in circuits of size n ^O(1) and treewidth k can be simulated by bounded fan-in formulas of depth O(k ²logn). This strengthens in the non-uniform setting the known inclusion that SC⁰?NC¹.
• We demonstrate treewidth restricted cases of Directed-Reachability and Circuit Value Problem that can be solved in LogDCFL.

We also give a construction showing, for both arithmetic and Boolean circuits, that any circuit of size n ^O(1) and treewidth O(log ⁱ n) can be simulated by a circuit of width O(log ⁱ⁺¹ n) and size n ^c , where c=O(1), if i=0, and c=O(loglogn) otherwise.     

Time Bounded Frequency Computations

(1) We obtain two new results concerning the inclusion problem of polynomial time frequency classes with equal numbers of errors. 1. (m, m+d) P(m+1, m+d+1) Pform<2^d. 2. (m, m+d) P=(m+1, m+d+1) Pformc(d) wherec(d) is large enough. This disproves a conjecture of Kinber. (2) We give a transparent proof of a generalization of Kinber's result that there exist arbitrarily complex problems admitting a polynomial time frequency computation. Several corollaries provide more insight into the structure of the hierarchy of polynomial time frequency classes. (3) The relationships between polynomial time frequency classes and selectivity classes are studied.     

Bounded disorder file organization

The bounded disorder file organization proposed by W. Litwin and D.B. Lomet (1987) uses a combination of hashing and tree indexing. Lomet provided an approximate analysis with the mention of the difficulty involved in exact modeling of data nodes, which motivated this work. In an earlier paper (M.V. Ramakrishna and P. Mukhopadhyay, 1988) we provided an exact model and analysis of the data nodes, which is based on the solution of a classical sequential occupancy problem. After summarizing the analysis of data nodes, an alternate file growth method based on repeated trials using universal hashing is proposed and analyzed. We conclude that the alternate file growth method provides simplicity and significant improvement in storage utilization     

Bounded error adaptive control

The paper discusses the adaptive control of a linear time-invariant plant when the measurement of the plant output is corrupted by a bounded disturbance. The principal contribution is the demonstration of the boundedness of all the signals of the overall system using a nonlinear adaptive law involving a dead zone. A statement of the prior information needed to determine the adaptive algorithm as well as a discussion of the limitations of the scheme are given. Computer simulations are presented to illustrate the effect of various parameters.     

Stochastic Processes for Bounded Noise

The scalar differential inclusionx f(x) + g(x) u, u [-1,1], x(0) = x ₀ (0.1) is considered as a model of the dynamical system x = f(x) perturbed by the bounded noise g(x)u, u [-1,1], and the problem of constructing a nontrivial probability measure on the set {\cal S} of solutions to (0.1) is studied. In particular, it is shown that: (i) every Markov process whose probability measure is supported on {\cal S} is degenerate, in a sense to be specified (see Theorem 3.1); (ii) given a flow of probability measures _t on the reachable sets R _t of (0.1), satisfying a certain compatibility condition, a Markov process X _t is constructed such that its marginals are exactly _t and (0.1) is satisfied from one side (see Theorem 4.1); its finite-dimensional distributions are computed and the regularity of its sample paths is investigated (see Section 5.2); (iii) given a process of a type previously considered, another process Y _t is constructed through its finite-dimensional distributions, and its distribution is shown to be supported exactly on {\cal S}. Finally, a model example is considered (see Section 7). Date received: July 18, 2000. Date revised: July 18, 2002. The work of G.C. was supported by EC Grant ERB-CIPA-CT-93-1554; that of V.K. by EC Grant ERB-CIPA-CT-92-0370 and GA R 201/98/0227. The stay of V.K. and I.V. at the Faculty of Biological Sciences was supported by MMT Grant No. VS96086. I.V. was partly supported by GA R Grant No. 201/95/0629.