Optimal partial-match retrieval

This paper studies the design of a system to handle partial-match queries from a file. A partial-match query is a specification of the value of zero or more fields in a record. An answer to a query consists of a listing of all records in the file satisfying the values specified.Aho and Ullman have considered the case when the probability that a field is specified in a query is independent of which other fields are specified. We consider here the more realistic case where the independence assumption is dropped. This leads to an optimization problem more general than that considered by Aho and Ullman. The major part of the paper is the presentation of an efficient algorithm for solving this optimization problem.     

Wavelet-based fingerprint image retrieval

This paper presents a novel approach for personal identification based on a wavelet-based fingerprint retrieval system which encompasses three image retrieval tasks, namely, feature extraction, similarity measurement, and feature indexing.     

Radar placement based on a geometric uncertainty multiplier reduction criterion

In this paper the problem of retrieving wind field information from Doppler radar data motivates the formulation of a method to design radar network configurations. The problem of estimating wind velocities from radar data is posed and used to construct a certain retrieval operator. This operator contains a factor that may be interpreted as an uncertainty multiplier. It depends on the geometry of the configuration of the radar network. The uncertainty multiplier is shown to vary continuously with perturbations of the network configuration. It is also shown to be a generalization of the Doppler angle condition used in meteorology. Numerical examples are presented to determine a network of five radars minimizing the uncertainty multiplier for the problem. Also, a configuration of sites is determined that maximizes the area of the Doppler region.     

Projections and phase retrieval

We characterize collections of orthogonal projections for which it is possible to reconstruct a vector from the magnitudes of the corresponding projections. As a result we are able to show that in an M-dimensional real vector space a vector can be reconstructed from the magnitudes of its projections onto a generic collection of $N\ge 2M?1$ subspaces. We also show that this bound is sharp when $N=2^k+1$. The results of this paper answer a number of questions raised in [5].     

Semantic hashing

We show how to learn a deep graphical model of the word-count vectors obtained from a large set of documents. The values of the latent variables in the deepest layer are easy to infer and give a much better representation of each document than Latent Semantic Analysis. When the deepest layer is forced to use a small number of binary variables (e.g. 32), the graphical model performs “semantic hashing”: Documents are mapped to memory addresses in such a way that semantically similar documents are located at nearby addresses. Documents similar to a query document can then be found by simply accessing all the addresses that differ by only a few bits from the address of the query document. This way of extending the efficiency of hash-coding to approximate matching is much faster than locality sensitive hashing, which is the fastest current method. By using semantic hashing to filter the documents given to TF-IDF, we achieve higher accuracy than applying TF-IDF to the entire document set.     

The minimal measurement number for low-rank matrix recovery

The paper presents several results that address a fundamental question in low-rank matrix recovery: how many measurements are needed to recover low-rank matrices? We begin by investigating the complex matrices case and show that $4nr?4r^2$ generic measurements are both necessary and sufficient for the recovery of rank-r matrices in ${\mathbb{C}}^{n\times n}$. Thus, we confirm a conjecture which is raised by Eldar, Needell and Plan for the complex case. We next consider the real case and prove that the bound $4nr?4r^2$ is tight provided $n=2^k+r,k\in {\mathbb{Z}}_{+}$. Motivated by Vinzant's work [19], we construct 11 matrices in ${\mathbb{R}}^{4\times 4}$ by computer random search and prove they define injective measurements on rank-1 matrices in ${\mathbb{R}}^{4\times 4}$. This disproves the conjecture raised by Eldar, Needell and Plan for the real case. Finally, we use the results in this paper to investigate the phase retrieval by projection and show fewer than $2n?1$ orthogonal projections are possible for the recovery of $x\in {\mathbb{R}}^n$ from the norm of them, which gives a negative answer for a question raised in [1].     

《数学评论》概况和文献检索

本文着重介绍《数学评论》及其索引的有关知识，并提供利用《数学评论》查找数学文献的检索途径．     

Partial match retrieval using recursive linear hashing

Recursive linear hashing is a hashing technique proposed for files which can grow and shrink dynamically. The scheme is an extension of linear hashing, a method originally proposed by Litwin, but unlike Litwin's scheme, it does not require conventional overflow pages. In this paper, we investigate the application of recursive linear hashing to partial match retrieval problems. Consistent with the results for primary key retrieval, recursive linear hashing performs better than the conventional scheme on these problems, especially at high load factors.     

Bit-parallel -matching and suffix automata

(δ,γ)-matching is a string matching problem with applications to music retrieval. The goal is, given a pattern P_1…m and a text T_1…n on an alphabet of integers, find the occurrences P^′ of the pattern in the text such that (i) , and (ii) . The problem makes sense for δγδm. Several techniques for (δ,γ)-matching have been proposed, based on bit-parallelism or on skipping characters. We first present an O(mnlog(γ)/w) worst-case time and O(n) average-case time bit-parallel algorithm (being w the number of bits in the computer word). It improves the previous O(mnlog(δm)/w) worst-case time algorithm of the same type. Second, we combine our bit-parallel algorithm with suffix automata to obtain the first algorithm that skips characters using both δ and γ. This algorithm examines less characters than any previous approach, as the others do just δ-matching and check the γ-condition on the candidates. We implemented our algorithms and drew experimental results on real music, showing that our algorithms are superior to current alternatives with high values of δ.     

Learning objects and objectives towards automatic learning construction

This paper presents a method that creates instructionally sound learning experiences by means of learning objects. The method uses a mathematical model, distinguishes two kinds of Learning Objects Properties and proceeds in two major steps: first, the Course Creation is transformed into Set Covering under specific requirements derived from Learning Theories and practice; second, the Alternative Learning Sources are selected by using a similarity measure specially defined for this purpose.     

SOLVING SYSTEMS OF QUADRATIC EQUATIONS VIA EXPONENTIAL-TYPE GRADIENT DESCENT ALGORITHM

We consider the rank minimization problem from quadratic measurements, i.e., recovering a rank $r$ matrix $X \in \mathbb{R}^{n×r}$ from $m$ scalar measurements $y_i=a_i^T XX^T a_i,\;a_i\in \mathbb{R}^n,\;i=1,\ldots,m$. Such problem arises in a variety of applications such as quadratic regression and quantum state tomography. We present a novel algorithm, which is termed $exponential-type$ $gradient$ $descent$ $algorithm$, to minimize a non-convex objective function $f(U)=\frac{1}{4m}\sum_{i=1}^m(y_i-a_i^T UU^T a_i)^2$. This algorithm starts with a careful initialization, and then refines this initial guess by iteratively applying exponential-type gradient descent. Particularly, we can obtain a good initial guess of $X$ as long as the number of Gaussian random measurements is $O(nr)$, and our iteration algorithm can converge linearly to the true $X$ (up to an orthogonal matrix) with $m=O\left(nr\log (cr)\right)$ Gaussian random measurements.     

Phase retrieval from local measurements: Improved robustness via eigenvector-based angular synchronization

We improve a phase retrieval approach that uses correlation-based measurements with compactly supported measurement masks [30]. Our approach admits deterministic measurement constructions together with a robust, fast recovery algorithm that consists of solving a system of linear equations in a lifted space, followed by finding an eigenvector (e.g., via an inverse power iteration). Theoretical reconstruction error guarantees from [30] are improved as a result for the new and more robust reconstruction approach proposed herein. Numerical experiments demonstrate robustness and computational efficiency that compete with other approaches on large problems. Along the way, we show that this approach also trivially extends to phase retrieval problems based on windowed Fourier measurements.     

基于内容检索中的模糊处理

基于内容的检索是多媒体信息处理中的一个重要问题，图像、视频作为多媒体中最直观、最形象的内容，对它们的检索和查询是多媒体内容处理的一个重要方面。以往对图像检索往往借助于图像理解等领域发展起来的模式识别技术，但检索在很多方面又不同于模式识别，它通常并不需要精确匹配，而且由于检索中人一机交互性起着很重要的作用，使得在检索中有必要利用模糊的方法来提出查询要求，计算机也可以通过模糊相似性匹配来给出结果。本文提出了以信任度、可能性测度、权重有隶属函数概念作为模糊相似性匹配的基础来检索图像的方法。     

Learning mathematics through algorithmic and creative reasoning

There are extensive concerns pertaining to the idea that students do not develop sufficient mathematical competence. This problem is at least partially related to the teaching of procedure-based learning. Although better teaching methods are proposed, there are very limited research insights as to why some methods work better than others, and the conditions under which these methods are applied. The present paper evaluates a model based on students’ own creation of knowledge, denoted creative mathematically founded reasoning (CMR), and compare this to a procedure-based model of teaching that is similar to what is commonly found in schools, denoted algorithmic reasoning (AR). In the present study, CMR was found to outperform AR. It was also found cognitive proficiency was significantly associated to test task performance. However the analysis also showed that the effect was more pronounced for the AR group.