11,043 research outputs found
Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation
No full textIn the masked low-rank approximation problem, one is given data matrix A ∈ ℝ^{n × n} and binary mask matrix W ∈ {0,1}^{n × n}. The goal is to find a rank-k matrix L for which:
cost(L) := ∑_{i=1}^n ∑_{j=1}^n W_{i,j} ⋅ (A_{i,j} - L_{i,j})² ≤ OPT + ε ‖A‖_F²,
where OPT = min_{rank-k L̂} cost(L̂) and ε is a given error parameter. Depending on the choice of W, the above problem captures factor analysis, low-rank plus diagonal decomposition, robust PCA, low-rank matrix completion, low-rank plus block matrix approximation, low-rank recovery from monotone missing data, and a number of other important problems. Many of these problems are NP-hard, and while algorithms with provable guarantees are known in some cases, they either 1) run in time n^Ω(k²/ε) or 2) make strong assumptions, for example, that A is incoherent or that the entries in W are chosen independently and uniformly at random.
In this work, we show that a common polynomial time heuristic, which simply sets A to 0 where W is 0, and then finds a standard low-rank approximation, yields bicriteria approximation guarantees for this problem. In particular, for rank k' > k depending on the public coin partition number of W, the heuristic outputs rank-k' L with cost(L) ≤ OPT + ε ‖A‖_F². This partition number is in turn bounded by the randomized communication complexity of W, when interpreted as a two-player communication matrix. For many important cases, including all those listed above, this yields bicriteria approximation guarantees with rank k' = k ⋅ poly(log n/ε).
Beyond this result, we show that different notions of communication complexity yield bicriteria algorithms for natural variants of masked low-rank approximation. For example, multi-player number-in-hand communication complexity connects to masked tensor decomposition and non-deterministic communication complexity to masked Boolean low-rank factorization
Eigenvector Computation and Community Detection in Asynchronous Gossip Models
No full textWe give a simple distributed algorithm for computing adjacency matrix eigenvectors for the communication graph in an asynchronous gossip model. We show how to use this algorithm to give state-of-the-art asynchronous community detection algorithms when the communication graph is drawn from the well-studied stochastic block model. Our methods also apply to a natural alternative model of randomized communication, where nodes within a community communicate more frequently than nodes in different communities.
Our analysis simplifies and generalizes prior work by forging a connection between asynchronous eigenvector computation and Oja's algorithm for streaming principal component analysis. We hope that our work serves as a starting point for building further connections between the analysis of stochastic iterative methods, like Oja's algorithm, and work on asynchronous and gossip-type algorithms for distributed computation
Efficient Block Approximate Matrix Multiplication
No full textRandomized matrix algorithms have had significant recent impact on numerical linear algebra. One especially powerful class of methods are algorithms for approximate matrix multiplication based on sampling. Such methods typically sample individual matrix rows and columns using carefully chosen importance sampling probabilities. However, due to practical considerations like memory locality and the preservation of matrix structure, it is often preferable to sample contiguous blocks of rows and columns all together. Recently, (Wu, 2018) addressed this setting by developing an approximate matrix multiplication method based on block sampling. However, the method is inefficient, as it requires knowledge of optimal importance sampling probabilities that are expensive to compute.
We address this issue by showing that the method of Wu can be accelerated through the use of a randomized implicit trace estimation method. Doing so allows us to provably reduce the cost of sampling to near-linear in the size of the matrices being multiplied, without impacting the accuracy of the final approximate matrix multiplication. Overall, this yields a fast practical algorithm, which we test on a number of synthetic and real-world data sets. We complement our algorithmic contribution with the first extensive empirical comparison of block algorithms for randomized matrix multiplication. Our method offers a significant runtime advantage over the method of (Wu, 2018) and also outperforms basic uniform sampling of blocks. However, we find another recent method of (Charalambides, 2021) which uses sub-optimal but efficiently computable sampling probabilities often (but not always) offers the best trade-off between speed and accuracy
Interview with Nicholas Christopher, author of Somewhere in the Night: Film Noir and the American City
No full textInterview with Nicholas Christopher, author of Somewhere in the Night: Film Noir and the American Cit
Matt Christopher Papers - Accession 1309
No full textThe collection includes letters written by the children’s book author, Matt Christopher, to his son, Marty Christopher. Many of the letters also contain newspaper articles of interest to Matt Christopher, which deal with local sports teams, his writing career, his participation in an exhibition baseball game against the New York Giants in 1938, and other of general interest. Most of the letters are personal in nature, however, a majority of the letters delve into Matt Christopher’s writing career, personal interests, the author’s health, as well as his family life.https://digitalcommons.winthrop.edu/manuscriptcollection_findingaids/2649/thumbnail.jp
Matt Christopher Papers - Accession 1221
No full textMatt Christopher (1917-1997) was a prolific author of children’s books having written over 100 books as well as over 300 short stories, articles, poems, and screenplays. Most of his writings dealt with sports themes, but he also wrote fantasy and mystery themed stories as well. The Matt Christopher Papers consist of both published and unpublished manuscripts, articles, and short stories. Also included are personal and business correspondence, biographical information, scrapbooks, photographs, and memorabilia.https://digitalcommons.winthrop.edu/manuscriptcollection_findingaids/1976/thumbnail.jp
Dr. Christopher von Rueden – Faculty Author Interview
No full textDr. Christopher von Rueden, an anthropologist and Assistant Professor in the Jepson School of Leadership Studies, discusses a recent article entitled, “Men’s status and reproductive success in 33 non-industrial societies: Effects of subsistence, marriage system, and reproductive strategy,” which he co-authored with Dr. Adrian Jaeggi, an anthropologist at Emory University. Their findings were recently published in the journal, Proceedings of the National Academy of Sciences
ESP Across Cultures
No full textThis present volume constitutes the third online edition of ESP Across Cultures.
The decision to change from a paper-based to an online edition has undoubtedly
been beneficial in terms of enjoying greater visibility within the international academic
community. One thing that has not changed over the years, however, since
the inception of the journal in 2004, has been the policy of double-blind peer reviewing,
which means that only a selected number of the papers submitted end up as
being published.
There are seven papers in the current issue, each one analysing a particular aspect
of English for Specific Purposes from a cross-cultural perspective.
The first paper, by Hmoud S. Alotaibi, focuses on research article introductions
in Arabic, analysing the extent to which scholars writing in Arabic in the sphere of
education adhere to the CARS (Create A Research Space) model delineated by John
Swales which was elaborated in particular with regard to the academic conventions
widely adopted in the English-speaking world. Instead of restricting the investigation
to the introductory section as past studies in this field did, the author examines
all of the subheadings and he concludes that all introductions include Move 2 in a
subheading entitled the Problem of the Study, a result that contradicts previous
findings where the paucity of Move 2 was common in non-English RAs, and especially
in Arabic ones.
Patrizia Anesa analyses the websites of the main arbitration centres operating in
Asia from a textual perspective to define how they are discursively constructed and
can be used as promotional tools, thereby helping us to evaluate the importance assumed
by internationalization processes or by local cultural elements in promoting a
particular centre as a seat for international arbitration. She concludes that while
some scholars argue that we are witnessing the ‘Asianization’ of arbitration, with
the increasing bargaining power of Asian parties, on the other hand a phenomenon
of ‘Universal Arbitration’ is also emerging, i.e. a form of convergence of how disputes
are resolved so that parties of any nationality can operate in the same way
with ever fewer language barriers.
In their paper, Mahmood Reza Atai and Fatemeh Asadnia examine the communicative
and promotional function of university homepages by looking at the ‘university
overview’, ‘university mission statement’, and ‘university introduction at a
glance’ genres, using a corpus of 210 texts selected from homepages of the top 500
universities ranked by the Academic Ranking of World Universities. The findings
demonstrated that the three genres shared communicative purposes, functional
units, certain moves and steps, socio-academic contexts, and discourse community
members that led to the formation of a genre set.
Gaetano Falco explores ways of using comics in an MA course on translation of
economic texts as a means of stimulating the interest of language students with no
economics skills in order to introduce economics-related lexis and improve thematic
competence in general. He observes that empirical research has shown that films
and comics can indeed be useful resources to teach economic translation to students
with no skills in economics. However, the author warns that the use of comics for
educational purposes may have its drawbacks, e.g. when students deal with complex
sign systems which embody complex economic concepts, where often the humorous
element is lost.
In her paper, Irina Khoutyz describes the differences in how scholars present
their findings in research articles (RA) in international journals in English and in
Beyza Björkman
Christian Burgers
Jan Chovanec
Anda-Elena Cretiu
Erika Dalan
John Douthwaite
Hanem El-Farahaty
Said Faiq
Silvia Ferreri
Inmaculada Fortanet-Gómez
Pedro Fuertes-Olivera
Giuliana Garzone
Christoph Hafner
Ruba Khamam
Anna Loiacono
Geraldine Ludbrook
John McRae
Susan Petrilli
Silvia Pireddu
Tarja Salmi-Tolonen
Jeffrey Segrave
Charlotte Taylor
Margherita Ulrych
John Kenneth White
Jessica Williams
I hope you will enjoy the current issue of this journal and will make the most of
the free access to all past issues.
Christopher Williams
(Chief Editor)
6 FOREWORD
local journals in Russian. She then looks into the reasons for these differences, seeking
explanations from the sociocultural contexts in which these RAs were written,
as well as providing advice to local authors as to how to make their RAs more competitive
at the international level. The differences include the apparent lack of
structure of Russian RAs with respect to English RAs; the tendency in Russian authors
not to specify the purpose in writing a paper; and the tendency of Russian authors
to present the methodology used in less detail compared with English RAs.
Luisella Leonzini investigates the use of verbal and visual metaphors in economic-
media discourse within the context of the euro crisis by studying the correlation
between linguistic and pictorial metaphors and text-image intersemiotic relations.
The research is based on a cross-analysis of English and Italian editorial
articles published between 2009 and 2012. In both corpora, metaphorical realizations
frame the economic crisis which hit the single currency and the eurozone in
2009 as a partial collapse and hint at a possible return to stability in the form of a
recovery. The aim of this paper is to analyse the collapse/caduta and
recovery/ripresa metaphors across languages in the press.
Ian Robinson reports on using corpus linguistics to aid students in writing a creative
text. He looks at the available literature to help understand what is meant by
‘creativity’. A worksheet was prepared using a corpus linguistic analysis of modern,
English versions of the stories of the Brothers Grimm. This worksheet was constructed
with the use of a specialized corpus, and a stop-list was created which contained
single words as well as word clusters found in the tales. Students were then
asked to select some of these words and phrases to help them write stories which
were then analysed, and a follow-up questionnaire was used to elicit the students’
perceptions concerning creativity. The author concludes that creativity is essential
in EFL and that it is something to be fostered in students
Dimensionality reduction for k-means clustering
No full textThesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.Cataloged from student-submitted PDF version of thesis.Includes bibliographical references (pages 123-131).In this thesis we study dimensionality reduction techniques for approximate k-means clustering. Given a large dataset, we consider how to quickly compress to a smaller dataset (a sketch), such that solving the k-means clustering problem on the sketch will give an approximately optimal solution on the original dataset. First, we provide an exposition of technical results of [CEM+15], which show that provably accurate dimensionality reduction is possible using common techniques such as principal component analysis, random projection, and random sampling. We next present empirical evaluations of dimensionality reduction techniques to supplement our theoretical results. We show that our dimensionality reduction algorithms, along with heuristics based on these algorithms, indeed perform well in practice. Finally, we discuss possible extensions of our work to neurally plausible algorithms for clustering and dimensionality reduction. This thesis is based on joint work with Michael Cohen, Samuel Elder, Nancy Lynch, Christopher Musco, and Madalina Persu.by Cameron N. Musco.S.M
Book review: The theatrical public sphere, by Christopher B. Balme
No full textBook review of: The theatrical public sphere, by Christopher B. Balme. Cambridge: Cambridge University Press, 2014; ISBN 9781107006836 (£60.00)Publisher PD
- …
