Newly deterministic construction of compressed sensing matrices via singular linear spaces over finite fields

A valuable opportunity is provided by compressed sensing (CS) to accomplish the tasks of high speed sampling, the transmission of large volumes of data, and storage in signal processing. To some extent, CS has brought tremendous changes in the information technologies that we use in our daily lives. However, the construction of compressed sensing matrices still can pose substantial problems. In this paper, we provide a kind of deterministic construction of sensing matrices based on singular linear spaces over finite fields. In particular, by choosing appropriate parameters, we constructed binary sensing matrices that are superior to existing matrices, and they outperform DeVore’s matrices. In addition, we used an embedding manipulation to merge our binary matrices with matrices that had low coherence, thereby improving such matrices. Compared with the quintessential binary matrices, the improved matrices possess better ability to compress and recover signals. The favorable performance of our binary and improved matrices was demonstrated by numerical simulations.     

On the Existence of Monotone Pure‐Strategy Equilibria in Bayesian Games

We generalize Athey's (2001) and McAdams' (2003) results on the existence of monotone pure‐strategy equilibria in Bayesian games. We allow action spaces to be compact locally complete metric semilattices and type spaces to be partially ordered probability spaces. Our proof is based on contractibility rather than convexity of best‐reply sets. Several examples illustrate the scope of the result, including new applications to multi‐unit auctions with risk‐averse bidders.     

A generalization of Macula’s disjunct matrices

As a generalization of the novel construction of disjunct matrices by Macula (Discrete Math. 162:311–312, 1996), we construct a new family of disjunct matrices and discuss its error-tolerant property.     

投入产出分析的几种系数矩阵在管理和经济分析中的作用

综合评价投入产出分析的几种系数矩阵在经济指标分析、经济效益分析和经济预测中的作用。提出投资系数矩阵的近似构造法,改进了利润作为目标函数的优化模型和推广了数学增量模型,并通过矩阵变换法从一个投入产出分析系数矩阵生成另一个相似的投入产出分析系数矩阵。     

Competent genetic algorithms for weighing matrices

In this paper, we demonstrate that the search for weighing matrices constructed from two circulants can be viewed as a minimization problem together with two competent genetic algorithms to locate optima of an objective function. The motivation to deal with the messy genetic algorithm (mGA) is given from the pioneering results of Goldberg, regarding the ability of the mGA to put tight genes together in a solution which points directly to structural patterns in weighing matrices. In order to take into advantage certain properties of two ternary sequences with zero autocorrelation we use an adaptation of the fast messy GA (fmGA) where we combine mGA with advanced techniques, such as thresholding and tie-breaking. This transformation of the weighing matrices problem to an instance of a combinatorial optimization problem seems to be promising, since we resolved two open cases for weighing matrices as these are listed in the second edition of the Handbook of Combinatorial Designs.     

A modified power spectral density test applied to?weighing matrices with small weight

The power spectral density test has been used for at least a decade in the search for many kinds of combinatorial matrices, such as weighing matrices for instance. In this paper we establish a modified power spectral density test that we apply to the search for weighing matrices of small weights constructed from two circulants. The main novelty of our approach is to define the Discrete Fourier Transform on the support of the first rows of the two circulants, thus exploiting the inherent sparsity of the problem. This new formalism turns out to be very efficient for small weights 9,18,36 and we find 10 new weighing matrices W(2⋅p,18) for prime p∈{37,47,53,59,61,67,73,79,83,97}. These matrices are given here for the first time. We also discuss briefly a connection with Combinatorial Optimization.     

What's Wrong with Risk Matrices?

Risk matrices—tables mapping "frequency" and "severity" ratings to corresponding risk priority levels—are popular in applications as diverse as terrorism risk analysis, highway construction project management, office building risk analysis, climate change risk management, and enterprise risk management (ERM). National and international standards (e.g., Military Standard 882C and AS/NZS 4360:1999) have stimulated adoption of risk matrices by many organizations and risk consultants. However, little research rigorously validates their performance in actually improving risk management decisions. This article examines some mathematical properties of risk matrices and shows that they have the following limitations. (a) Poor Resolution . Typical risk matrices can correctly and unambiguously compare only a small fraction (e.g., less than 10%) of randomly selected pairs of hazards. They can assign identical ratings to quantitatively very different risks ("range compression"). (b) Errors . Risk matrices can mistakenly assign higher qualitative ratings to quantitatively smaller risks. For risks with negatively correlated frequencies and severities, they can be "worse than useless," leading to worse-than-random decisions. (c) Suboptimal Resource Allocation . Effective allocation of resources to risk-reducing countermeasures cannot be based on the categories provided by risk matrices. (d) Ambiguous Inputs and Outputs . Categorizations of severity cannot be made objectively for uncertain consequences. Inputs to risk matrices (e.g., frequency and severity categorizations) and resulting outputs (i.e., risk ratings) require subjective interpretation, and different users may obtain opposite ratings of the same quantitative risks. These limitations suggest that risk matrices should be used with caution, and only with careful explanations of embedded judgments.     

Puzzles in Organizational Learning: An Exercise in Disciplined Imagination

Theory construction is in part an exercise in 'disciplined imagination'. One way to discipline our imaginations around the topic of organizational learning, it is to pay special attention to things we forget, values we slight, goals we neglect, facts we avoid and questions we fear. Each aspect of this framework is explored in the paper through a variety of stories and examples. These include Charles Handy's first job, fighting fires, medical diagnosis, Winston Churchill's reflections on the fall of Singapore and the identification of dangerous viruses. These rich and evocative stories offer moments for reflection on underlying issues involved in sense–making, and provide the reader with insights into the relationship between leadership and learning.     

Robotic-Cell Scheduling: Special Polynomially Solvable Cases of the Traveling Salesman Problem on Permuted Monge Matrices

In this paper, we introduce the 1 − K robotic-cell scheduling problem, whose solution can be reduced to solving a TSP on specially structured permuted Monge matrices, we call b-decomposable matrices. We also review a number of other scheduling problems which all reduce to solving TSP-s on permuted Monge matrices. We present the important insight that the TSP on b-decomposable matrices can be solved in polynomial time by a special adaptation of the well-known subtour-patching technique. We discuss efficient implementations of this algorithm on newly defined subclasses of permuted Monge matrices.     

Efficient point coverage in wireless sensor networks

We study minimum-cost sensor placement on a bounded 3D sensing field, R, which comprises a number of discrete points that may or may not be grid points. Suppose we have ℓ types of sensors available with different sensing ranges and different costs. We want to find, given an integer σ ≥ 1, a selection of sensors and a subset of points to place these sensors such that every point in R is covered by at least σ sensors and the total cost of the sensors is minimum. This problem is known to be NP-hard. Let k_i denote the maximum number of points that can be covered by a sensor of the ith type. We present in this paper a polynomial-time approximation algorithm for this problem with a proven approximation ratio . In applications where the distance of any two points has a fixed positive lower bound, each k_i is a constant, and so we have a polynomial-time approximation algorithms with a constant guarantee. While γ may be large, we note that it is only a worst-case upper bound. In practice the actual approximation ratio is small, even on randomly generated points that do not have a fixed positive minimum distance between them. We provide a number of numerical results for comparing approximation solutions and optimal solutions, and show that the actual approximation ratios in these examples are all less than 3, even though γ is substantially larger. This research was supported in part by NSF under grant CCF-04080261 and by NSF of China under grant 60273062.     

Incentives for information sharing in duopoly with capacity constraints

We study the ex ante incentives for firms to share their private information in a Cournot duopoly with capacity constraints. In both demand and cost information sharing games, we show that the incentives can be reversed when some equilibrium solutions are binding on capacity. Especially, we identify some conditions under which partial information sharing is the dominant strategy under both games. Numerical examples are provided for illustration. In addition, we show that information sharing does not necessarily increase social welfare.     

A feasibility approach for constructing combinatorial designs of circulant type

In this work, we propose an optimization approach for constructing various classes of circulant combinatorial designs that can be defined in terms of autocorrelation. The problem is formulated as a so-called feasibility problem having three sets, to which the Douglas–Rachford projection algorithm is applied. The approach is illustrated on three different classes of circulant combinatorial designs: circulant weighing matrices, D-optimal matrices of circulant type, and Hadamard matrices with two circulant cores. Furthermore, we explicitly construct two new circulant weighing matrices, a CW(126, 64) and a CW(198, 100), whose existence was previously marked as unresolved in the most recent version of Strassler’s table.     

A Review of Risk Matrices Used in Acute Hospitals in England

In healthcare, patient safety has received substantial attention and, in turn, a number of approaches to managing safety have been adopted from other high‐risk industries. One of these has been risk assessment, predominantly through the use of risk matrices. However, while other industries have criticized the design and use of these risk matrices, the applicability of such criticism has not been investigated formally in healthcare. This study examines risk matrices as used in acute hospitals in England and the guidance provided for their use. It investigates the applicability of criticisms of risk matrices from outside healthcare through a document analysis of the risk assessment policies, procedures, and strategies used in English hospitals. The findings reveal that there is a large variety of risk matrices used, where the design of some might increase the chance of risk misprioritization. Additionally, findings show that hospitals may provide insufficient guidance on how to use risk matrices as well as what to do in response to the existing criticisms of risk matrices. Consequently, this is likely to lead to variation in the quality of risk assessment and in the subsequent deployment of resources to manage the assessed risk. Finally, the article outlines ways in which hospitals could use risk matrices more effectively.     

Almost separable matrices

An \(m\times n\) matrix \(\mathsf {A}\) with column supports \(\{S_i\}\) is k-separable if the disjunctions \(\bigcup _{i \in \mathcal {K}} S_i\) are all distinct over all sets \(\mathcal {K}\) of cardinality k. While a simple counting bound shows that \(m > k \log _2 n/k\) rows are required for a separable matrix to exist, in fact it is necessary for m to be about a factor of k more than this. In this paper, we consider a weaker definition of ‘almost k-separability’, which requires that the disjunctions are ‘mostly distinct’. We show using a random construction that these matrices exist with \(m = O(k \log n)\) rows, which is optimal for \(k = O(n^{1-\beta })\). Further, by calculating explicit constants, we show how almost separable matrices give new bounds on the rate of nonadaptive group testing.     

How to Design Rating Schemes of Risk Matrices: A Sequential Updating Approach

Risk matrices have been widely used as a risk evaluation tool in many fields due to their simplicity and intuitive nature. Designing a rating scheme, i.e., determining the number of ratings used in a risk matrix and assigning different ratings to different cells, is an essential part of risk matrix construction. However, most of the related literature has focused on applying a risk matrix to various fields, instead of researching how to design risk matrices. Based on the analysis of several current rules, we propose a new approach, namely, the sequential updating approach (SUA), to design the rating scheme of a risk matrix in a reliable way. In this article, we propose three principles and a rating algorithm based on these principles. The three principles, namely, adjusted weak consistency, consistent internality, and continuous screening, characterize a good rating scheme. The resulting rating scheme has been proven to be unique. A global rating algorithm is then proposed to create the design that satisfies the three principles. We then explore the performance of the SUA. An illustrative application is first given to explain the feasibility of our approach. The sensitivity analysis shows that our method captures a resolution‐reliability tradeoff for decisionmakers in choosing an appropriate rating scheme for a risk matrix. Finally, we compare the designs based on the SUA and Cox's axioms, highlighting the advantages of the SUA.     

Structure Prediction and Computation of Sparse Matrix Products

We consider1 the problem of predicting the nonzero structure of a product of two or more matrices. Prior knowledge of the nonzero structure can be applied to optimize memory allocation and to determine the optimal multiplication order for a chain product of sparse matrices. We adapt a recent algorithm by the author and show that the essence of the nonzero structure and hence, a near-optimal order of multiplications, can be determined in near-linear time in the number of nonzero entries, which is much smaller than the time required for the multiplications. An experimental evaluation of the algorithm demonstrates that it is practical for matrices of order 103 with 104 nonzeros (or larger). A relatively small pre-computation results in a large time saved in the computation-intensive multiplication.     

Beyond the Matrix: Visual Methods for Qualitative Network Research

Network research remains dominated by approaches involving the analysis of numerical data stored in data matrices with the aim of identifying the effects of hidden social structures. While such research has advanced our understanding of social networks at the inter‐personal, inter‐unit and inter‐organizational level, repeated calls have been made for network research to attend to the situated meanings attached to both relationships and network structures. In this article, we advance a nascent literature on qualitative methods for social network analysis by drawing together developments in visual network research from across the social sciences. We introduce a typology of three visual methods for the collection of network data using network maps: participatory network mapping, network map interviews and visual network surveys. Drawing on three empirical examples from our research in the inter‐organizational domain, we demonstrate how these methods can be used for the collection of qualitative and quantitative relational data, and how they can be triangulated with other qualitative methods and social network analysis. We evaluate the merits and limitations of the methods presented and conclude that visual network research is a useful addition to existing methods for network research in business and management studies.     

Code for polyomino and computer search of isospectral polyominoes

A new code, binary 2-dimentional code (B2DC), is proposed for polyominoes. An algorithm based on the B2DC and the reverse search method are proposed for enumerating nonisomorphic planar simply connected polyominoes. An enumeration tree and a new father-son relationship are defined for enumerating polyominoes. Then we propose an algorithm to build adjacent matrices and laplacian matrices by B2DCs of polyominoes and search isospectral polyomino graphs by computing characteristic polynomials of those matrices.     

A Probabilistic Feasibility and Value Analysis of the Generalized Assignment Problem

We study the generalized assignment problem, under a probabilistic model for its cost and requirement parameters. First we address the issue of feasibility by deriving a tight condition on the probabilistic model that ensures that the corresponding problem instances are feasible with probability one as the number of jobs goes to infinity. Then, under an additional condition on the parameters, we show that the optimal solution value, normalized by dividing by the number of jobs, converges with probability one to a constant, again as the number of jobs goes to infinity. Finally, we discuss various examples.     

Minding and Mining the Periphery

This paper cites examples of where peripheral events have caused ripples that reached right to the centre of an organisation. However, it also says that activities on the periphery can be a source of strategic insights. It suggests some tools for creating a sensing organisation that include establishing listening posts and developing communities of practice. It concludes by saying managers need to create the ‘ambidextrous’ corporation, whereby they use these tools for probing the periphery without making them a distraction from the central business.