<?xml version="1.0" encoding="UTF-8"?>
 <rdf:RDF xmlns="http://purl.org/rss/1.0/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:taxo="http://purl.org/rss/1.0/modules/taxonomy/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:cc="http://web.resource.org/cc/" xmlns:syn="http://purl.org/rss/1.0/modules/syndication/" xmlns:admin="http://webns.net/mvcb/">
  <channel rdf:about="http://pinboard.in">
    <title>Pinboard (Vaguery)</title>
    <link>https://pinboard.in/u:Vaguery/public/</link>
    <description>recent bookmarks from Vaguery</description>
    <items>
      <rdf:Seq>	<rdf:li rdf:resource="https://www.researchgate.net/publication/392282754_ON_A_GENERALIZATION_OF_THE_PERFECT_SQUARE_SEQUENCE_AND_ITS_POLYNOMIAL?_tp=eyJjb250ZXh0Ijp7ImZpcnN0UGFnZSI6InByb2ZpbGUiLCJwYWdlIjoicHJvZmlsZSJ9fQ"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1606.09299"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2212.11644"/>
	<rdf:li rdf:resource="https://ianthehenry.com/posts/fibonacci/"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2209.14775"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2001.04109"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1702.02650"/>
	<rdf:li rdf:resource="https://publications.mfo.de/handle/mfo/1415"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2101.12638"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2005.00379"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1810.07921"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2004.13440"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1401.5226"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2010.11406"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1605.04416"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1702.06976"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1711.07420"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1601.07227"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1701.00706"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1704.05207"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1704.05211"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1906.05637"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1603.09133"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1903.06778"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1606.09402"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1811.00547"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1701.06377"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1611.03060"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1803.10908"/>
	<rdf:li rdf:resource="https://blogs.scientificamerican.com/roots-of-unity/the-metonymy-of-matrices/"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1709.08359"/>
	<rdf:li rdf:resource="http://parrt.cs.usfca.edu/doc/matrix-calculus/index.html"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1604.02181"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1706.02263"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1609.06349"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1711.02724"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1602.03311"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1605.01078"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1611.08035"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1605.06848"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1702.02017"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1602.06915"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1709.08461"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1607.05342"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1705.08743"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1708.08377"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1707.06356"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1709.06079"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1108.2714"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1203.2377"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1605.08107"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1608.04481"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1104.5557"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1505.07363"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1704.00708"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1605.08629"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1702.06166"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1202.4358"/>
	<rdf:li rdf:resource="http://www.mathrecreation.com/2016/11/polynomial-grid-division-examples.html"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1703.00998"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1701.01207"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1611.01120"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1602.02262"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1610.06145"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1609.05034"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1607.06303"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1602.00061"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1509.07766"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1605.01695"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1407.3254"/>
      </rdf:Seq>
    </items>
  </channel><item rdf:about="https://www.researchgate.net/publication/392282754_ON_A_GENERALIZATION_OF_THE_PERFECT_SQUARE_SEQUENCE_AND_ITS_POLYNOMIAL?_tp=eyJjb250ZXh0Ijp7ImZpcnN0UGFnZSI6InByb2ZpbGUiLCJwYWdlIjoicHJvZmlsZSJ9fQ">
    <title>(PDF) ON A GENERALIZATION OF THE PERFECT SQUARE SEQUENCE AND ITS POLYNOMIAL</title>
    <dc:date>2025-06-25T19:26:07+00:00</dc:date>
    <link>https://www.researchgate.net/publication/392282754_ON_A_GENERALIZATION_OF_THE_PERFECT_SQUARE_SEQUENCE_AND_ITS_POLYNOMIAL?_tp=eyJjb250ZXh0Ijp7ImZpcnN0UGFnZSI6InByb2ZpbGUiLCJwYWdlIjoicHJvZmlsZSJ9fQ</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In this study, we introduce a new recurrence relation of the perfect square sequence. We establish the relationship of perfect square sequence concerned with Fibonacci and Lucas sequences. We compute some important identities such as Catalan, Cassini, and special summation formula for this sequence. We associate the perfect square sequence with Lucas sequence and we call it the perfect square Lucas sequence. In addition, the Binet formula, generating function and summation formula of this sequence is obtained, as well as some properties are satisfied. Furthermore, we present the relationship of perfect square Lucas sequence with Fibonacci and Lucas sequences. Also, we obtain the relationship of perfect square Lucas sequence with perfect square sequence and we present matrix representation of this sequence. Besides, we described polynomials of perfect square and perfect square Lucas sequences. We get Binet formulas, generating functions, and Simpson formula for these polynomials. Eventually, satisfied some intriguing relations between these two polynomials, as well as we give the matrix representation of them.]]></description>
<dc:subject>mathematics Fibonacci number-theory matrices to-understand</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:cb725c391fc9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:Fibonacci"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:number-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1606.09299">
    <title>[1606.09299] Counting Matrices that are Squares</title>
    <dc:date>2024-09-09T15:51:57+00:00</dc:date>
    <link>https://arxiv.org/abs/1606.09299</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[On the math-fun mailing list (7 May 2013), Neil Sloane asked to calculate the number of n×n matrices with entries in {0,1} which are squares of other such matrices. In this paper we analyze the case that the arithmetic is in 𝔽2. We follow the dictum of Wilf ("What is an answer?") to derive a "effective" algorithm to count such matrices in much less time than it takes to enumerate them. The algorithm which we use involves the analysis of conjugacy classes of matrices. The restricted integer partitions which arise are counted by the coefficients of one of Ramanujan's mock Theta functions, which we found thanks to Sloane's OEIS (Online Encyclopedia of Integer Sequences). Let an be the number elements of Matn(𝔽2) which are squares, and bn be the number of elements of GL(n,𝔽2) which are squares. The numerical results strongly suggest that there are constants α,β>0 such that an∼α2n2, bn∼β2n2.
]]></description>
<dc:subject>number-theory matrices mathematical-recreations enumeration rather-interesting software-development-is-not-programming OEIS to-write-about to-simulate consider:variants</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:d80548104948/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:number-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-recreations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:software-development-is-not-programming"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:OEIS"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:variants"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2212.11644">
    <title>[2212.11644] Poset Matrix Structure Via Partial Composition Operations</title>
    <dc:date>2024-09-05T01:03:26+00:00</dc:date>
    <link>https://arxiv.org/abs/2212.11644</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[This paper examines the structure of poset matrices by formulating a set of new construction rules for this purpose. In this direction, the technique of partial composition operation will be introduced as the basis for the construction of poset matrices of any given size by extending the combinatorial setting of species of structures to poset matrices. More specifically, three new partial composition operations that apply to poset matrices are defined as the foundation for this study. Several new structural properties derived from viewing any poset matrix and its dual in terms of these operations are highlighted.
]]></description>
<dc:subject>sorting combinatorics graph-theory matrices construction rather-interesting to-understand enumeration consider:lexicase consider:multiobjective-sets consider:probability-theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:0d7d0ee327b3/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:sorting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:lexicase"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:multiobjective-sets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:probability-theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://ianthehenry.com/posts/fibonacci/">
    <title>The Fibonacci Matrix</title>
    <dc:date>2024-08-08T11:30:50+00:00</dc:date>
    <link>https://ianthehenry.com/posts/fibonacci/</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[When you think about the Fibonacci sequence, you probably imagine a swirling vortex of oscillating points stretching outwards to infinity:
]]></description>
<dc:subject>mathematical-recreations number-theory matrices animation to-visualize consider:other-matrices consider:generalizations linear-algebra</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:f6f9bf09d17e/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-recreations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:number-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:animation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-visualize"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:other-matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:generalizations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:linear-algebra"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2209.14775">
    <title>[2209.14775] On Constructing Spanners from Random Gaussian Projections</title>
    <dc:date>2023-10-12T11:11:56+00:00</dc:date>
    <link>https://arxiv.org/abs/2209.14775</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Graph sketching is a powerful paradigm for analyzing graph structure via linear measurements introduced by Ahn, Guha, and McGregor (SODA'12) that has since found numerous applications in streaming, distributed computing, and massively parallel algorithms, among others. Graph sketching has proven to be quite successful for various problems such as connectivity, minimum spanning trees, edge or vertex connectivity, and cut or spectral sparsifiers. Yet, the problem of approximating shortest path metric of a graph, and specifically computing a spanner, is notably missing from the list of successes. This has turned the status of this fundamental problem into one of the most longstanding open questions in this area.
We present a partial explanation of this lack of success by proving a strong lower bound for a large family of graph sketching algorithms that encompasses prior work on spanners and many (but importantly not also all) related cut-based problems mentioned above. Our lower bound matches the algorithmic bounds of the recent result of Filtser, Kapralov, and Nouri (SODA'21), up to lower order terms, for constructing spanners via the same graph sketching family. This establishes near-optimality of these bounds, at least restricted to this family of graph sketching techniques, and makes progress on a conjecture posed in this latter work.
]]></description>
<dc:subject>graph-theory numerical-methods matrices rather-interesting linear-projection transformations heuristics to-understand to-write-about</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:82ddc5bf2751/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:numerical-methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:linear-projection"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:transformations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:heuristics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2001.04109">
    <title>[2001.04109] On fast multiplication of a matrix by its transpose</title>
    <dc:date>2022-02-28T13:59:14+00:00</dc:date>
    <link>https://arxiv.org/abs/2001.04109</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We present a non-commutative algorithm for the multiplication of a 2x2-block-matrix by its transpose using 5 block products (3 recursive calls and 2 general products) over C or any finite field.We use geometric considerations on the space of bilinear forms describing 2x2 matrix products to obtain this algorithm and we show how to reduce the number of involved additions.The resulting algorithm for arbitrary dimensions is a reduction of multiplication of a matrix by its transpose to general matrix product, improving by a constant factor previously known reductions.Finally we propose schedules with low memory footprint that support a fast and memory efficient practical implementation over a finite this http URL conclude, we show how to use our result in LDLT factorization.
]]></description>
<dc:subject>matrices algorithms numerical-methods computational-complexity rather-interesting to-write-about to-visualize consider:genetic-programming</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:14bb5e1045e9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:numerical-methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-visualize"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:genetic-programming"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1702.02650">
    <title>[1702.02650] Diagonal elements in the Nonnegative Inverse Eigenvalue Problem</title>
    <dc:date>2021-11-09T11:28:52+00:00</dc:date>
    <link>https://arxiv.org/abs/1702.02650</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We say that a list of complex numbers is "realisable" if it is the spectrum of some (entrywise) nonnegative matrix. The Nonnegative Inverse Eigenvalue Problem (NIEP) is the problem of characterising all realisable lists. Although the NIEP remains unsolved, it has been solved in the case where every entry in the list (apart from the Perron eigenvalue) has nonpositive real part. For a given spectrum of this type, we show that a list of nonnegative numbers may arise as the diagonal elements of the realising matrix if and only if these numbers satisfy a remarkably simple inequality. Furthermore, we show that realisation can be achieved by the sum of a companion matrix and a diagonal matrix.
]]></description>
<dc:subject>number-theory inverse-problems matrices analysis to-write-about to-simulate consider:looking-to-see consider:visualization</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:f371540bff38/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:number-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inverse-problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:visualization"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://publications.mfo.de/handle/mfo/1415">
    <title>Algebra, matrices, and computers</title>
    <dc:date>2021-10-07T10:22:23+00:00</dc:date>
    <link>https://publications.mfo.de/handle/mfo/1415</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[What part does algebra play in representing the real
 world abstractly? How can algebra be used to solve
 hard mathematical problems with the aid of modern
 computing technology? We provide answers to these
 questions that rely on the theory of matrix groups
 and new methods for handling matrix groups in a
 computer.
]]></description>
<dc:subject>matrices mathematics rather-interesting review mathematical-programming group-theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:de7584db8d80/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:review"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-programming"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:group-theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2101.12638">
    <title>[2101.12638] On foci of ellipses inscribed in cyclic polygons</title>
    <dc:date>2021-07-13T00:26:28+00:00</dc:date>
    <link>https://arxiv.org/abs/2101.12638</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Given a natural number n≥3 and two points a and b in the unit disk 𝔻 in the complex plane, it is known that there exists a unique elliptical disk having a and b as foci that can also be realized as the intersection of a collection of convex cyclic n-gons whose vertices fill the whole unit circle 𝕋. What is less clear is how to find a convenient formula or expression for such an elliptical disk. Our main results reveal how orthogonal polynomials on the unit circle provide a useful tool for finding such a formula for some values of n. The main idea is to realize the elliptical disk as the numerical range of a matrix and the problem reduces to finding the eigenvalues of that matrix.
]]></description>
<dc:subject>analysis plane-geometry construction rather-interesting quite-lovely to-write-about to-visualize representation matrices out-of-the-box consider:heuristic-move consider:mathematical-modes</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:aecf06470e6c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:plane-geometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:quite-lovely"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-visualize"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:out-of-the-box"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:heuristic-move"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:mathematical-modes"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2005.00379">
    <title>[2005.00379] Pattern-Avoiding (0,1)-Matrices</title>
    <dc:date>2021-07-04T11:55:08+00:00</dc:date>
    <link>https://arxiv.org/abs/2005.00379</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We investigate pattern-avoiding (0,1)-matrices as generalizations of pattern-avoiding permutations. Our emphasis is on 123-avoiding and 321-avoiding patterns for which we obtain exact results as to the maximum number of 1's such matrices can have. We also give algorithms when carried out in all possible ways, construct all of the pattern-avoiding matrices of these two types.
]]></description>
<dc:subject>permutations matrices rather-interesting generalization patter-avoiding constraint-satisfaction enumeration combinatorics to-write-about consider:sampling consider:extensions consider:row-and-column-constraints-instead</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:307719459f7a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:permutations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:generalization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:patter-avoiding"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:constraint-satisfaction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:sampling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:extensions"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:row-and-column-constraints-instead"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1810.07921">
    <title>[1810.07921] Concentration of the Frobenius norm of generalized matrix inverses</title>
    <dc:date>2021-05-23T21:40:02+00:00</dc:date>
    <link>https://arxiv.org/abs/1810.07921</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In many applications it is useful to replace the Moore-Penrose pseudoinverse (MPP) by a different generalized inverse with more favorable properties. We may want, for example, to have many zero entries, but without giving up too much of the stability of the MPP. One way to quantify stability is by how much the Frobenius norm of a generalized inverse exceeds that of the MPP. In this paper we derive finite-size concentration bounds for the Frobenius norm of ℓp-minimal general inverses of iid Gaussian matrices, with 1≤p≤2. For p=1 we prove exponential concentration of the Frobenius norm of the sparse pseudoinverse; for p=2, we get a similar concentration bound for the MPP. Our proof is based on the convex Gaussian min-max theorem, but unlike previous applications which give asymptotic results, we derive finite-size bounds.
]]></description>
<dc:subject>matrices generalization rather-interesting inverse-problems performance-measure to-write-about consider:hillclimbing consider:diversity-of-sampling</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:b99b9dd7796c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:generalization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inverse-problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:performance-measure"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:hillclimbing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:diversity-of-sampling"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2004.13440">
    <title>[2004.13440] Asymptotics of product of nonnegative 2-by-2 matrices with applications to random walks with asymptotically zero drifts</title>
    <dc:date>2021-03-12T14:41:11+00:00</dc:date>
    <link>https://arxiv.org/abs/2004.13440</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Let AkAk−1⋯A1 be product of some nonnegative 2-by-2 matrices. In general, its elements are hard to evaluate. Under some conditions, we show that ∀i,j∈{1,2}, (AkAk−1⋯A1)i,j∼cϱ(Ak)ϱ(Ak−1)⋯ϱ(A1) as k→∞, where ϱ(An) is the spectral radius of the matrix An and c∈(0,∞) is some constant, so that the elements of AkAk−1⋯A1 can be estimated. As applications, consider the maxima of certain excursions of (2,1) and (1,2) random walks with asymptotically zero drifts. 
We get some delicate limit theories which are quite different from the ones of simple random walks. Limit theories of both the tail and critical tail sequences of continued fractions play important roles in our studies.
]]></description>
<dc:subject>branching-processes probability-theory random-walks matrices to-write-about to-simulate consider:looking-to-see consider:visualization</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:e1fc64c0ef53/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:branching-processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:probability-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:random-walks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:visualization"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1401.5226">
    <title>[1401.5226] The Why and How of Nonnegative Matrix Factorization</title>
    <dc:date>2021-01-14T11:13:38+00:00</dc:date>
    <link>https://arxiv.org/abs/1401.5226</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Nonnegative matrix factorization (NMF) has become a widely used tool for the analysis of high-dimensional data as it automatically extracts sparse and meaningful features from a set of nonnegative data vectors. We first illustrate this property of NMF on three applications, in image processing, text mining and hyperspectral imaging --this is the why. Then we address the problem of solving NMF, which is NP-hard in general. We review some standard NMF algorithms, and also present a recent subclass of NMF problems, referred to as near-separable NMF, that can be solved efficiently (that is, in polynomial time), even in the presence of noise --this is the how. Finally, we briefly describe some problems in mathematics and computer science closely related to NMF via the nonnegative rank.
]]></description>
<dc:subject>machine-learning dimension-reduction algorithms explanation rather-interesting feature-extraction matrices</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:669de992b896/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:machine-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:dimension-reduction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:explanation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-extraction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2010.11406">
    <title>[2010.11406] 1-norm minimization and minimum-rank structured sparsity for symmetric and ah-symmetric generalized inverses: rank one and two</title>
    <dc:date>2020-11-15T11:40:45+00:00</dc:date>
    <link>https://arxiv.org/abs/2010.11406</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Generalized inverses are important in statistics and other areas of applied matrix algebra. A \emph{generalized inverse} of a real matrix A is a matrix H that satisfies the Moore-Penrose (M-P) property AHA=A. If H also satisfies the M-P property HAH=H, then it is called \emph{reflexive}. Reflexivity of a generalized inverse is equivalent to minimum rank, a highly desirable property. We consider aspects of symmetry related to the calculation of various \emph{sparse} reflexive generalized inverses of A. As is common, we use (vector) 1-norm minimization for both inducing sparsity and for keeping the magnitude of entries under control. 
When A is symmetric, a symmetric H is highly desirable, but generally such a restriction on H will not lead to a 1-norm minimizing reflexive generalized inverse. We investigate a block construction method to produce a symmetric reflexive generalized inverse that is structured and has guaranteed sparsity. Letting the rank of A be r, we establish that the 1-norm minimizing generalized inverse of this type is a 1-norm minimizing symmetric generalized inverse when (i) r=1 and when (ii) r=2 and A is nonnegative. 
Another aspect of symmetry that we consider relates to another M-P property: H is \emph{ah-symmetric} if AH is symmetric. The ah-symmetry property is sufficient for a generalized inverse to be used to solve the least-squares problem min{‖Ax−b‖2: x∈ℝn} using H, via x:=Hb. We investigate a column block construction method to produce an ah-symmetric reflexive generalized inverse that is structured and has guaranteed sparsity. We establish that the 1-norm minimizing ah-symmetric generalized inverse of this type is a 1-norm minimizing ah-symmetric generalized inverse when (i) r=1 and when (ii) r=2 and A satisfies a technical condition.
]]></description>
<dc:subject>matrices inverse-problems rather-interesting approximation relaxations-of-rules to-write-about consider:looking-to-see consider:metaheuristics constraint-satisfaction multiobjective-optimization</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:ae9cc8c70f6c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inverse-problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:relaxations-of-rules"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:metaheuristics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:constraint-satisfaction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:multiobjective-optimization"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1605.04416">
    <title>[1605.04416] On the similarity of AB and BA for normal and other matrices</title>
    <dc:date>2020-07-11T13:12:32+00:00</dc:date>
    <link>https://arxiv.org/abs/1605.04416</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[It is well-known that AB and BA are similar when A and B are complex square Hermitian matrices. In this note we answer a question of F. Zhang by demonstrating that similarity can fail if A is Hermitian and B is normal. Perhaps surprisingly, similarity does hold when A is positive semidefinite and B is normal.
]]></description>
<dc:subject>number-theory analysis matrices rather-interesting inverse-problems consider:looking-to-see consider:feature-discovery to-write-about to-simulate</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:f3f69c59d076/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:number-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inverse-problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:feature-discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1702.06976">
    <title>[1702.06976] Heavy-Tailed Analogues of the Covariance Matrix for ICA</title>
    <dc:date>2020-05-22T21:33:57+00:00</dc:date>
    <link>https://arxiv.org/abs/1702.06976</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Independent Component Analysis (ICA) is the problem of learning a square matrix A, given samples of X=AS, where S is a random vector with independent coordinates. Most existing algorithms are provably efficient only when each Si has finite and moderately valued fourth moment. However, there are practical applications where this assumption need not be true, such as speech and finance. Algorithms have been proposed for heavy-tailed ICA, but they are not practical, using random walks and the full power of the ellipsoid algorithm multiple times. The main contributions of this paper are: 
(1) A practical algorithm for heavy-tailed ICA that we call HTICA. We provide theoretical guarantees and show that it outperforms other algorithms in some heavy-tailed regimes, both on real and synthetic data. Like the current state-of-the-art, the new algorithm is based on the centroid body (a first moment analogue of the covariance matrix). Unlike the state-of-the-art, our algorithm is practically efficient. To achieve this, we use explicit analytic representations of the centroid body, which bypasses the use of the ellipsoid method and random walks. 
(2) We study how heavy tails affect different ICA algorithms, including HTICA. Somewhat surprisingly, we show that some algorithms that use the covariance matrix or higher moments can successfully solve a range of ICA instances with infinite second moment. We study this theoretically and experimentally, with both synthetic and real-world heavy-tailed data.
]]></description>
<dc:subject>machine-learning benchmarking matrices rather-interesting to-write-about nudge-targets consider:representation consider:ReQ algorithms computational-complexity</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:d40bd17995ea/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:machine-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:benchmarking"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:ReQ"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1711.07420">
    <title>[1711.07420] Outliers in the spectrum for products of independent random matrices</title>
    <dc:date>2020-05-18T21:32:42+00:00</dc:date>
    <link>https://arxiv.org/abs/1711.07420</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[For fixed positive integers m, we consider the product of m independent n by n random matrices with iid entries as in the limit as n tends to infinity. Under suitable assumptions on the entries of each matrix, it is known that the limiting empirical distribution of the eigenvalues is described by the m-th power of the circular law. Moreover, this same limiting distribution continues to hold if each iid random matrix is additively perturbed by a bounded rank deterministic error. However, the bounded rank perturbations may create one or more outlier eigenvalues. We describe the asymptotic location of the outlier eigenvalues, which extends a result of Terence Tao for the case of a single iid matrix. Our methods also allow us to consider several other types of perturbations, including multiplicative perturbations.
]]></description>
<dc:subject>random-matrices matrices sampling probability-theory rather-interesting to-write-about consider:extreme-values</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:1f57f7bf96f0/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:random-matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:sampling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:probability-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:extreme-values"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1601.07227">
    <title>[1601.07227] A network that learns Strassen multiplication</title>
    <dc:date>2020-04-20T12:41:55+00:00</dc:date>
    <link>https://arxiv.org/abs/1601.07227</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We study neural networks whose only non-linear components are multipliers, to test a new training rule in a context where the precise representation of data is paramount. These networks are challenged to discover the rules of matrix multiplication, given many examples. By limiting the number of multipliers, the network is forced to discover the Strassen multiplication rules. This is the mathematical equivalent of finding low rank decompositions of the n×n matrix multiplication tensor, Mn. We train these networks with the conservative learning rule, which makes minimal changes to the weights so as to give the correct output for each input at the time the input-output pair is received. Conservative learning needs a few thousand examples to find the rank 7 decomposition of M2, and 105 for the rank 23 decomposition of M3 (the lowest known). High precision is critical, especially for M3, to discriminate between true decompositions and "border approximations".
]]></description>
<dc:subject>software-synthesis neural-networks matrices algorithms rather-interesting to-replicate to-write-about to-simulate consider:genetic-programming consider:heuristics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:4ddbfe0fd014/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:software-synthesis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:neural-networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-replicate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:genetic-programming"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:heuristics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1701.00706">
    <title>[1701.00706] Bounds on parameters of minimally non-linear patterns</title>
    <dc:date>2020-01-19T18:51:48+00:00</dc:date>
    <link>https://arxiv.org/abs/1701.00706</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Let ex(n,P) be the maximum possible number of ones in any 0-1 matrix of dimensions n×n that avoids P. Matrix P is called minimally non-linear if ex(n,P)=ω(n) but ex(n,P′)=O(n) for every strict subpattern P′ of P. We prove that the ratio between the length and width of any minimally non-linear 0-1 matrix is at most 4, and that a minimally non-linear 0-1 matrix with k rows has at most 5k−3 ones. We also obtain an upper bound on the number of minimally non-linear 0-1 matrices with k rows. 
In addition, we prove corresponding bounds for minimally non-linear ordered graphs. The minimal non-linearity that we investigate for ordered graphs is for the extremal function ex<(n,G), which is the maximum possible number of edges in any ordered graph on n vertices with no ordered subgraph isomorphic to G.]]></description>
<dc:subject>matrices pattern-avoiding pattern-matching combinatorics rather-interesting constraint-satisfaction looking-to-see enumeration feature-construction to-simulate to-write-about</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:ab0696e4ce3b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:pattern-avoiding"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:pattern-matching"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:constraint-satisfaction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1704.05207">
    <title>[1704.05207] Algorithms for Pattern Containment in 0-1 Matrices</title>
    <dc:date>2020-01-19T18:43:04+00:00</dc:date>
    <link>https://arxiv.org/abs/1704.05207</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We say a zero-one matrix A avoids another zero-one matrix P if no submatrix of A can be transformed to P by changing some ones to zeros. A fundamental problem is to study the extremal function ex(n,P), the maximum number of nonzero entries in an n×n zero-one matrix A which avoids P. To calculate exact values of ex(n,P) for specific values of n, we need containment algorithms which tell us whether a given n×n matrix A contains a given pattern matrix P. In this paper, we present optimal algorithms to determine when an n×n matrix A contains a given pattern P when P is a column of all ones, an identity matrix, a tuple identity matrix, an L-shaped pattern, or a cross pattern. These algorithms run in Θ(n2) time, which is the lowest possible order a containment algorithm can achieve. When P is a rectangular all-ones matrix, we also obtain an improved running time algorithm, albeit with a higher order.
]]></description>
<dc:subject>matrices constraint-satisfaction game-theory rather-interesting mathematical-recreations patterns permutations to-simulate to-write-about consider:feature-discovery combinatorics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:222b1a4330a0/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:constraint-satisfaction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:game-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-recreations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:patterns"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:permutations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:feature-discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1704.05211">
    <title>[1704.05211] Results on Pattern Avoidance Games</title>
    <dc:date>2020-01-19T18:41:07+00:00</dc:date>
    <link>https://arxiv.org/abs/1704.05211</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[A zero-one matrix A contains another zero-one matrix P if some submatrix of A can be transformed to P by changing some ones to zeros. A avoids P if A does not contain P. The Pattern Avoidance Game is played by two players. Starting with an all-zero matrix, two players take turns changing zeros to ones while keeping A avoiding P. We study the strategies of this game for some patterns P. We also study some generalizations of this game.
]]></description>
<dc:subject>crowdsourcing rather-interesting game-theory patterns permutations looking-to-see open-questions to-simulate to-write-about mathematical-recreations matrices</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:9e34129060b6/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:crowdsourcing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:game-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:patterns"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:permutations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:open-questions"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-recreations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1906.05637">
    <title>[1906.05637] Invariant Off-Diagonality: SICs as Equicoherent Quantum States</title>
    <dc:date>2019-11-25T17:33:34+00:00</dc:date>
    <link>https://arxiv.org/abs/1906.05637</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Coherence, treated as a resource in quantum information theory, is a basis-dependent quantity. Looking for states that have constant coherence under canonical changes of basis yields highly symmetric structures in state space. For the case of a qubit, we find an easy construction of qubit SICs (Symmetric Informationally Complete POVMs). SICs in dimension 3 and 8 are also shown to be equicoherent.
]]></description>
<dc:subject>quantums representation rather-interesting adjacent-possible (sorry) quantum-computing matrices algorithms to-simulate</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:5cb756c1161c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:quantums"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:adjacent-possible"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:(sorry)"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:quantum-computing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1603.09133">
    <title>[1603.09133] &quot;Compress and eliminate&quot; solver for symmetric positive definite sparse matrices</title>
    <dc:date>2019-08-30T10:48:56+00:00</dc:date>
    <link>https://arxiv.org/abs/1603.09133</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We propose a new approximate factorization for solving linear systems with symmetric positive definite sparse matrices. In a nutshell the algorithm is to apply hierarchically block Gaussian elimination and additionally compress the fill-in. The systems that have efficient compression of the fill-in mostly arise from discretization of partial differential equations. We show that the resulting factorization can be used as an efficient preconditioner and compare the proposed approach with state-of-art direct and iterative solvers.
]]></description>
<dc:subject>numerical-methods matrices algorithms computational-complexity rather-interesting to-write-about consider:performance-measures consider:feature-discovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:559890fd17b6/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:numerical-methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:performance-measures"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:feature-discovery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1903.06778">
    <title>[1903.06778] Matrix scaling limits in finitely many iterations</title>
    <dc:date>2019-07-14T12:47:23+00:00</dc:date>
    <link>https://arxiv.org/abs/1903.06778</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[The alternate row and column scaling algorithm applied to a positive n×n matrix A converges to a doubly stochastic matrix S(A), sometimes called the \emph{Sinkhorn limit} of A. For every positive integer n, a two parameter family of row but not column stochastic n×n positive matrices is constructed that become doubly stochastic after exactly one column scaling.
]]></description>
<dc:subject>matrices feature-construction open-questions number-theory rather-interesting to-write-about to-simulate consider:looking-to-see</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:cea894ceef16/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:open-questions"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:number-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1606.09402">
    <title>[1606.09402] Efficient Randomized Algorithms for the Fixed-Precision Low-Rank Matrix Approximation</title>
    <dc:date>2019-05-01T11:24:42+00:00</dc:date>
    <link>https://arxiv.org/abs/1606.09402</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Randomized algorithms for low-rank matrix approximation are investigated, with the emphasis on the fixed-precision problem and computational efficiency for handling large matrices. The algorithms are based on the so-called QB factorization, where Q is an orthonormal matrix. Firstly, a mechanism for calculating the approximation error in Frobenius norm is proposed, which enables efficient adaptive rank determination for large and/or sparse matrix. It can be combined with any QB-form factorization algorithm in which B's rows are incrementally generated. Based on the blocked randQB algorithm by P.-G. Martinsson and S. Voronin, this results in an algorithm called randQB EI. Then, we further revise the algorithm to obtain a pass-efficient algorithm, randQB FP, which is mathematically equivalent to the existing randQB algorithms and also suitable for the fixed-precision problem. Especially, randQB FP can serve as a single-pass algorithm for calculating leading singular values, under certain condition. With large and/or sparse test matrices, we have empirically validated the merits of the proposed techniques, which exhibit remarkable speedup and memory saving over the blocked randQB algorithm. We have also demonstrated that the single-pass algorithm derived by randQB FP is much more accurate than an existing single-pass algorithm. And with data from a scenic image and an information retrieval application, we have shown the advantages of the proposed algorithms over the adaptive range finder algorithm for solving the fixed-precision problem.
]]></description>
<dc:subject>numerical-methods approximation constraint-satisfaction algorithms performance-measure matrices to-write-about</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:84b5927ef659/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:numerical-methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:constraint-satisfaction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:performance-measure"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1811.00547">
    <title>[1811.00547] Geometric Mean of Partial Positive Definite Matrices with Missing Entries</title>
    <dc:date>2019-02-19T11:44:18+00:00</dc:date>
    <link>https://arxiv.org/abs/1811.00547</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In this paper the geometric mean of partial positive definite matrices with missing entries is considered. The weighted geometric mean of two sets of positive matrices is defined, and we show whether such a geometric mean holds certain properties which the weighted geometric mean of two positive definite matrices satisfies. Additionally, counterexamples demonstrate that certain properties do not hold. A Loewner order on partial Hermitian matrices is also defined. The known results for the maximum determinant positive completion are developed with an integral representation, and the results are applied to the weighted geometric mean of two partial positive definite matrices with missing entries. Moreover, a relationship between two positive definite completions is established with respect to their determinants, showing relationship between their entropy for a zero-mean,multivariate Gaussian distribution. Computational results as well as one application are shown.
]]></description>
<dc:subject>matrices to-understand inference proof looking-to-see to-write-about consider:algorithms missing-data data-cleaning</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:48ec3e3145bd/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inference"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:proof"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:missing-data"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:data-cleaning"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1701.06377">
    <title>[1701.06377] Counting Arithmetical Structures on Paths and Cycles</title>
    <dc:date>2018-12-20T12:22:19+00:00</dc:date>
    <link>https://arxiv.org/abs/1701.06377</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Let G be a finite, simple, connected graph. An arithmetical structure on G is a pair of positive integer vectors d,r such that (diag(d)−A)r=0, where A is the adjacency matrix of G. We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the cokernels of the matrices (diag(d)−A)). For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients (2n−1n−1), and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.]]></description>
<dc:subject>graph-theory combinatorics enumeration counting to-understand matrices feature-construction</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:86babe538748/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:counting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1611.03060">
    <title>[1611.03060] The Non-convex Geometry of Low-rank Matrix Optimization</title>
    <dc:date>2018-12-16T13:24:42+00:00</dc:date>
    <link>https://arxiv.org/abs/1611.03060</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[This work considers two popular minimization problems: (i) the minimization of a general convex function f(X) with the domain being positive semi-definite matrices; (ii) the minimization of a general convex function f(X) regularized by the matrix nuclear norm ‖X‖∗ with the domain being general matrices. Despite their optimal statistical performance in the literature, these two optimization problems have a high computational complexity even when solved using tailored fast convex solvers. To develop faster and more scalable algorithms, we follow the proposal of Burer and Monteiro to factor the low-rank variable X=UU⊤ (for semi-definite matrices) or X=UV⊤ (for general matrices) and also replace the nuclear norm ‖X‖∗ with (‖U‖2F+‖V‖2F)/2. In spite of the non-convexity of the resulting factored formulations, we prove that each critical point either corresponds to the global optimum of the original convex problems or is a strict saddle where the Hessian matrix has a strictly negative eigenvalue. Such a nice geometric structure of the factored formulations allows many local search algorithms to find a global optimizer even with random initializations.
]]></description>
<dc:subject>optimization representation matrices to-understand algorithms mathematical-programming information-theory to-translate</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:134a8f0c0987/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-programming"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:information-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-translate"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1803.10908">
    <title>[1803.10908] Matrix Product Operators for Sequence to Sequence Learning</title>
    <dc:date>2018-10-14T11:57:07+00:00</dc:date>
    <link>https://arxiv.org/abs/1803.10908</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[The method of choice to study one-dimensional strongly interacting many body quantum systems is based on matrix product states and operators. Such method allows to explore the most relevant, and numerically manageable, portion of an exponentially large space. It also allows to describe accurately correlations between distant parts of a system, an important ingredient to account for the context in machine learning tasks. Here we introduce a machine learning model in which matrix product operators are trained to implement sequence to sequence prediction, i.e. given a sequence at a time step, it allows one to predict the next sequence. We then apply our algorithm to cellular automata (for which we show exact analytical solutions in terms of matrix product operators), and to nonlinear coupled maps. We show advantages of the proposed algorithm when compared to conditional random fields and bidirectional long short-term memory neural network. To highlight the flexibility of the algorithm, we also show that it can readily perform classification tasks.
]]></description>
<dc:subject>representation machine-learning to-understand matrices quantum-computing classification algorithms</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:a5b68ceae9c9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:machine-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:quantum-computing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:classification"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://blogs.scientificamerican.com/roots-of-unity/the-metonymy-of-matrices/">
    <title>The Metonymy of Matrices - Scientific American Blog Network</title>
    <dc:date>2018-05-05T10:14:03+00:00</dc:date>
    <link>https://blogs.scientificamerican.com/roots-of-unity/the-metonymy-of-matrices/</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[As a tool, the matrix is so powerful that it is easy to forget that it is a representation of a function, not a function itself. A matrix truly is just the array of numbers, but I think in this context, most mathematicians are metonymists. (Metonymers? Metonymnistes?) We think of the matrix as the function itself, and it’s easy to lose sight of the fact that it's only notation. Matrices don’t even have to encode linear transformations. They are used in other contexts in mathematics, too, and restricting our definition to linear transformations can shortchange the other applications (though for my money, the value of the matrix as a way of representing linear transformations dwarfs any other use they have).
]]></description>
<dc:subject>matrices representation functions mathematical-recreations to-write-about</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:9dba67db5a54/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:functions"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-recreations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1709.08359">
    <title>[1709.08359] On the expressive power of query languages for matrices</title>
    <dc:date>2018-03-19T09:47:39+00:00</dc:date>
    <link>https://arxiv.org/abs/1709.08359</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We investigate the expressive power of 𝖬𝖠𝖳𝖫𝖠𝖭𝖦, a formal language for matrix manipulation based on common matrix operations and linear algebra. The language can be extended with the operation 𝗂𝗇𝗏 of inverting a matrix. In 𝖬𝖠𝖳𝖫𝖠𝖭𝖦+𝗂𝗇𝗏 we can compute the transitive closure of directed graphs, whereas we show that this is not possible without inversion. Indeed we show that the basic language can be simulated in the relational algebra with arithmetic operations, grouping, and summation. We also consider an operation 𝖾𝗂𝗀𝖾𝗇 for diagonalizing a matrix, which is defined so that different eigenvectors returned for a same eigenvalue are orthogonal. We show that 𝗂𝗇𝗏 can be expressed in 𝖬𝖠𝖳𝖫𝖠𝖭𝖦+𝖾𝗂𝗀𝖾𝗇. We put forward the open question whether there are boolean queries about matrices, or generic queries about graphs, expressible in 𝖬𝖠𝖳𝖫𝖠𝖭𝖦+𝖾𝗂𝗀𝖾𝗇 but not in 𝖬𝖠𝖳𝖫𝖠𝖭𝖦+𝗂𝗇𝗏. The evaluation problem for 𝖬𝖠𝖳𝖫𝖠𝖭𝖦+𝖾𝗂𝗀𝖾𝗇 is shown to be complete for the complexity class ∃R.]]></description>
<dc:subject>matrices programming-language representation rather-interesting nudge consider:representation to--do</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:c47e8c81a71d/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:programming-language"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to--do"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://parrt.cs.usfca.edu/doc/matrix-calculus/index.html">
    <title>[untitled]</title>
    <dc:date>2018-02-03T18:00:31+00:00</dc:date>
    <link>http://parrt.cs.usfca.edu/doc/matrix-calculus/index.html</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[This paper is an attempt to explain all the matrix calculus you need in order to understand the training of deep neural networks. We assume no math knowledge beyond what you learned in calculus 1, and provide links to help you refresh the necessary math where needed. Note that you do not need to understand this material before you start learning to train and use deep learning in practice; rather, this material is for those who are already familiar with the basics of neural networks, and wish to deepen their understanding of the underlying math. Don't worry if you get stuck at some point along the way---just go back and reread the previous section, and try writing down and working through some examples. And if you're still stuck, we're happy to answer your questions in the Theory category at forums.fast.ai. Note: There is a reference section at the end of the paper summarizing all the key matrix calculus rules and terminology discussed here.

]]></description>
<dc:subject>via:numerous matrices mathematics review calculus deep-learning</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:289ee818876d/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:via:numerous"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:review"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:calculus"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:deep-learning"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1604.02181">
    <title>[1604.02181] A Unified Framework for Sparse Non-Negative Least Squares using Multiplicative Updates and the Non-Negative Matrix Factorization Problem</title>
    <dc:date>2018-02-03T16:07:55+00:00</dc:date>
    <link>https://arxiv.org/abs/1604.02181</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We study the sparse non-negative least squares (S-NNLS) problem. S-NNLS occurs naturally in a wide variety of applications where an unknown, non-negative quantity must be recovered from linear measurements. We present a unified framework for S-NNLS based on a rectified power exponential scale mixture prior on the sparse codes. We show that the proposed framework encompasses a large class of S-NNLS algorithms and provide a computationally efficient inference procedure based on multiplicative update rules. Such update rules are convenient for solving large sets of S-NNLS problems simultaneously, which is required in contexts like sparse non-negative matrix factorization (S-NMF). We provide theoretical justification for the proposed approach by showing that the local minima of the objective function being optimized are sparse and the S-NNLS algorithms presented are guaranteed to converge to a set of stationary points of the objective function. We then extend our framework to S-NMF, showing that our framework leads to many well known S-NMF algorithms under specific choices of prior and providing a guarantee that a popular subclass of the proposed algorithms converges to a set of stationary points of the objective function. Finally, we study the performance of the proposed approaches on synthetic and real-world data.
]]></description>
<dc:subject>matrices inverse-problems algorithms rather-interesting nudge-targets performance-measure to-write-about</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:d453244854f0/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inverse-problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:performance-measure"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1706.02263">
    <title>[1706.02263] Graph Convolutional Matrix Completion</title>
    <dc:date>2018-01-28T15:17:29+00:00</dc:date>
    <link>https://arxiv.org/abs/1706.02263</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We consider matrix completion for recommender systems from the point of view of link prediction on graphs. Interaction data such as movie ratings can be represented by a bipartite user-item graph with labeled edges denoting observed ratings. Building on recent progress in deep learning on graph-structured data, we propose a graph auto-encoder framework based on differentiable message passing on the bipartite interaction graph. Our model shows competitive performance on standard collaborative filtering benchmarks. In settings where complimentary feature information or structured data such as a social network is available, our framework outperforms recent state-of-the-art methods.
]]></description>
<dc:subject>matrix-completion inference machine-learning representation matrices algorithms nudge-targets to-write-about</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:b41da50142dd/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrix-completion"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inference"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:machine-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1609.06349">
    <title>[1609.06349] A review of matrix scaling and Sinkhorn's normal form for matrices and positive maps</title>
    <dc:date>2017-12-29T13:36:53+00:00</dc:date>
    <link>https://arxiv.org/abs/1609.06349</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Given a nonnegative matrix A, can you find diagonal matrices D1, D2 such that D1AD2 is doubly stochastic? The answer to this question is known as Sinkhorn's theorem. It has been proved with a wide variety of methods, each presenting a variety of possible generalisations. Recently, generalisations such as to positive maps between matrix algebras have become more and more interesting for applications. This text gives a review of over 70 years of matrix scaling. The focus lies on the mathematical landscape surrounding the problem and its solution as well as the generalisation to positive maps and contains hardly any nontrivial unpublished results.
]]></description>
<dc:subject>matrices algorithms to-write-about nudge-targets consider:looking-to-see easily-checked</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:e3934cfd0075/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:easily-checked"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1711.02724">
    <title>[1711.02724] Algorithms to Approximate Column-Sparse Packing Problems</title>
    <dc:date>2017-11-12T12:38:38+00:00</dc:date>
    <link>https://arxiv.org/abs/1711.02724</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Column-sparse packing problems arise in several contexts in both deterministic and stochastic discrete optimization. We present two unifying ideas, (non-uniform) attenuation and multiple-chance algorithms, to obtain improved approximation algorithms for some well-known families of such problems. As three main examples, we attain the integrality gap, up to lower-order terms, for known LP relaxations for k-column sparse packing integer programs (Bansal et al., Theory of Computing, 2012) and stochastic k-set packing (Bansal et al., Algorithmica, 2012), and go "half the remaining distance" to optimal for a major integrality-gap conjecture of Furedi, Kahn and Seymour on hypergraph matching (Combinatorica, 1993).]]></description>
<dc:subject>integer-programming matrices optimization operations-research set-theory hypergraphs to-write-about approximation algorithms</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:f6bc80b822a9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:integer-programming"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:operations-research"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:set-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:hypergraphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1602.03311">
    <title>[1602.03311] Efficient weight vectors from pairwise comparison matrices</title>
    <dc:date>2017-11-09T12:07:19+00:00</dc:date>
    <link>https://arxiv.org/abs/1602.03311</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Pairwise comparison matrices are frequently applied in multi-criteria decision making. A weight vector is called efficient if no other weight vector is at least as good in approximating the elements of the pairwise comparison matrix, and strictly better in at least one position. A weight vector is weakly efficient if the pairwise ratios cannot be improved in all non-diagonal positions. We show that the principal eigenvector is always weakly efficient, but numerical examples show that it can be inefficient. The linear programs proposed test whether a given weight vector is (weakly) efficient, and in case of (strong) inefficiency, an efficient (strongly) dominating weight vector is calculated. The proposed algorithms are implemented in Pairwise Comparison Matrix Calculator, available at pcmc.online.]]></description>
<dc:subject>optimization multiobjective-optimization heuristics matrices inference rather-interesting try-not-to-do-this to-write-about consider:inverse-problem consider:robustness numerical-methods</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:866b57e789a1/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:multiobjective-optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:heuristics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inference"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:try-not-to-do-this"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:inverse-problem"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:robustness"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:numerical-methods"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1605.01078">
    <title>[1605.01078] Implementing Strassen's Algorithm with BLIS</title>
    <dc:date>2017-11-05T22:07:31+00:00</dc:date>
    <link>https://arxiv.org/abs/1605.01078</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We dispel with "street wisdom" regarding the practical implementation of Strassen's algorithm for matrix-matrix multiplication (DGEMM). Conventional wisdom: it is only practical for very large matrices. Our implementation is practical for small matrices. Conventional wisdom: the matrices being multiplied should be relatively square. Our implementation is practical for rank-k updates, where k is relatively small (a shape of importance for libraries like LAPACK). Conventional wisdom: it inherently requires substantial workspace. Our implementation requires no workspace beyond buffers already incorporated into conventional high-performance DGEMM implementations. Conventional wisdom: a Strassen DGEMM interface must pass in workspace. Our implementation requires no such workspace and can be plug-compatible with the standard DGEMM interface. Conventional wisdom: it is hard to demonstrate speedup on multi-core architectures. Our implementation demonstrates speedup over conventional DGEMM even on an Intel(R) Xeon Phi(TM) coprocessor utilizing 240 threads. We show how a distributed memory matrix-matrix multiplication also benefits from these advances.]]></description>
<dc:subject>matrices algorithms numerical-methods software-development-is-not-programming rather-interesting to-write-about hardware</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:36b522be5abe/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:numerical-methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:software-development-is-not-programming"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:hardware"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1611.08035">
    <title>[1611.08035] Automating the Last-Mile for High Performance Dense Linear Algebra</title>
    <dc:date>2017-11-05T14:46:20+00:00</dc:date>
    <link>https://arxiv.org/abs/1611.08035</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[High performance dense linear algebra (DLA) libraries often rely on a general matrix multiply (Gemm) kernel that is implemented using assembly or with vector intrinsics. In particular, the real-valued Gemm kernels provide the overwhelming fraction of performance for the complex-valued Gemm kernels, along with the entire level-3 BLAS and many of the real and complex LAPACK routines. Thus,achieving high performance for the Gemm kernel translates into a high performance linear algebra stack above this kernel. However, it is a monumental task for a domain expert to manually implement the kernel for every library-supported architecture. This leads to the belief that the craft of a Gemm kernel is more dark art than science. It is this premise that drives the popularity of autotuning with code generation in the domain of DLA. 
This paper, instead, focuses on an analytical approach to code generation of the Gemm kernel for different architecture, in order to shed light on the details or voo-doo required for implementing a high performance Gemm kernel. We distill the implementation of the kernel into an even smaller kernel, an outer-product, and analytically determine how available SIMD instructions can be used to compute the outer-product efficiently. We codify this approach into a system to automatically generate a high performance SIMD implementation of the Gemm kernel. Experimental results demonstrate that our approach yields generated kernels with performance that is competitive with kernels implemented manually or using empirical search.]]></description>
<dc:subject>matrices algorithms rather-interesting optimization code-generation nudge-targets consider:looking-to-see consider:performance-measures</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:3a2403022ae6/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:code-generation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:performance-measures"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1605.06848">
    <title>[1605.06848] Nonnegative Matrix Factorization Requires Irrationality</title>
    <dc:date>2017-11-05T14:16:11+00:00</dc:date>
    <link>https://arxiv.org/abs/1605.06848</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative n×m matrix M into a product of a nonnegative n×d matrix W and a nonnegative d×m matrix H. A longstanding open question, posed by Cohen and Rothblum in 1993, is whether a rational matrix M always has an NMF of minimal inner dimension d whose factors W and H are also rational. We answer this question negatively, by exhibiting a matrix for which W and H require irrational entries.]]></description>
<dc:subject>matrices computational-geometry rather-interesting to-write-about to-understand representation proof consider:classification</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:b4ac382dbffc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-geometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:proof"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:classification"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1702.02017">
    <title>[1702.02017] Pushing the Bounds for Matrix-Matrix Multiplication</title>
    <dc:date>2017-11-05T14:04:18+00:00</dc:date>
    <link>https://arxiv.org/abs/1702.02017</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[A tight lower bound for required I/O when computing a matrix-matrix multiplication on a processor with two layers of memory is established. Prior work obtained weaker lower bounds by reasoning about the number of \textit{phases} needed to perform C:=AB, where each phase is a series of operations involving S reads and writes to and from fast memory, and S is the size of fast memory. A lower bound on the number of phases was then determined by obtaining an upper bound on the number of scalar multiplications performed per phase. This paper follows the same high level approach, but improves the lower bound by considering C:=AB+C instead of C:=AB, and obtains the maximum number of scalar fused multiply-adds (FMAs) per phase instead of scalar additions. Key to obtaining the new result is the decoupling of the per-phase I/O from the size of fast memory. The new lower bound is 2mnk/S‾√−2S. The constant for the leading term is an improvement of a factor 42‾√. A theoretical algorithm that attains the lower bound is given, and how the state-of-the-art Goto's algorithm also in some sense meets the lower bound is discussed.]]></description>
<dc:subject>computational-complexity algorithms matrices rather-interesting nudge-targets consider:looking-to-see consider:representation consider:performance-measures</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:6caf84f19f7c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:performance-measures"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1602.06915">
    <title>[1602.06915] Periodicity in Rectangular Arrays</title>
    <dc:date>2017-10-18T12:01:07+00:00</dc:date>
    <link>https://arxiv.org/abs/1602.06915</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We discuss several two-dimensional generalizations of the familiar Lyndon-Schutzenberger periodicity theorem for words. We consider the notion of primitive array (as one that cannot be expressed as the repetition of smaller arrays). We count the number of m x n arrays that are primitive. Finally, we show that one can test primitivity and compute the primitive root of an array in linear time.
]]></description>
<dc:subject>matrices probability-theory to-understand data-structures rather-interesting consider:nudge-operators</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:f38934c2601b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:probability-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:data-structures"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:nudge-operators"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1709.08461">
    <title>[1709.08461] Mining a Sub-Matrix of Maximal Sum</title>
    <dc:date>2017-10-15T12:20:20+00:00</dc:date>
    <link>https://arxiv.org/abs/1709.08461</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Biclustering techniques have been widely used to identify homogeneous subgroups within large data matrices, such as subsets of genes similarly expressed across subsets of patients. Mining a max-sum sub-matrix is a related but distinct problem for which one looks for a (non-necessarily contiguous) rectangular sub-matrix with a maximal sum of its entries. Le Van et al. (Ranked Tiling, 2014) already illustrated its applicability to gene expression analysis and addressed it with a constraint programming (CP) approach combined with large neighborhood search (CP-LNS). In this work, we exhibit some key properties of this NP-hard problem and define a bounding function such that larger problems can be solved in reasonable time. Two different algorithms are proposed in order to exploit the highlighted characteristics of the problem: a CP approach with a global constraint (CPGC) and mixed integer linear programming (MILP). Practical experiments conducted both on synthetic and real gene expression data exhibit the characteristics of these approaches and their relative benefits over the original CP-LNS method. Overall, the CPGC approach tends to be the fastest to produce a good solution. Yet, the MILP formulation is arguably the easiest to formulate and can also be competitive.
]]></description>
<dc:subject>machine-learning matrices mathematical-programming benchmarking to-write-about nudge-targets</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:7256a5b3370d/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:machine-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-programming"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:benchmarking"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1607.05342">
    <title>[1607.05342] On Integer Programming and the Path-width of the Constraint Matrix</title>
    <dc:date>2017-10-15T12:15:28+00:00</dc:date>
    <link>https://arxiv.org/abs/1607.05342</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In the classic Integer Programming (IP) problem, the objective is to decide whether, for a given m×n matrix A and an m-vector b=(b1,…,bm), there is a non-negative integer n-vector x such that Ax=b. Solving (IP) is an important step in numerous algorithms and it is important to obtain an understanding of the precise complexity of this problem as a function of natural parameters of the input. Two significant results in this line of research are the pseudo-polynomial time algorithms for (IP) when the number of constraints is a constant [Papadimitriou, J. ACM 1981] and when the branch-width of the column-matroid corresponding to the constraint matrix is a constant [Cunningham and Geelen, IPCO 2007]. In this paper, we prove matching upper and lower bounds for (IP) when the path-width of the corresponding column-matroid is a constant. These lower bounds provide evidence that the algorithm of Cunningham and Geelen, are probably optimal. We also obtain a separate lower bound providing evidence that the algorithm of Papadimitriou is close to optimal.]]></description>
<dc:subject>classification benchmarking rather-interesting mathematical-programming matrices feature-construction nudge-targets consider:rediscovery consider:performance-measures computational-complexity</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:818f1324102a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:classification"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:benchmarking"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-programming"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:rediscovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:performance-measures"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1705.08743">
    <title>[1705.08743] Fast algorithms for anti-distance matrices as a generalization of Boolean matrices</title>
    <dc:date>2017-10-11T00:27:17+00:00</dc:date>
    <link>https://arxiv.org/abs/1705.08743</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We show that Boolean matrix multiplication, computed as a sum of products of column vectors with row vectors, is essentially the same as Warshall's algorithm for computing the transitive closure matrix of a graph from its adjacency matrix. 
Warshall's algorithm can be generalized to Floyd's algorithm for computing the distance matrix of a graph with weighted edges. We will generalize Boolean matrices in the same way, keeping matrix multiplication essentially equivalent to the Floyd-Warshall algorithm. This way, we get matrices over a semiring, which are similar to the so-called "funny matrices". 
We discuss our implementation of operations on Boolean matrices and on their generalization, which make use of vector instructions.
]]></description>
<dc:subject>matrices algorithms graph-theory rather-interesting insight nudge-targets consider:looking-to-see</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:c506dc1c7d69/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:insight"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1708.08377">
    <title>[1708.08377] Two-Dimensional Indirect Binary Search for the Positive One-in-Three Satisfiability Problem</title>
    <dc:date>2017-10-09T11:19:26+00:00</dc:date>
    <link>https://arxiv.org/abs/1708.08377</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In this paper, we propose an algorithm for the positive one-in-three satisfiability problem (Pos1in3SAT). The proposed algorithm can efficiently decide the existence of a satisfying assignment in all assignments for a given formula by using a 2-dimensional binary search method without constructing an exponential number of assignments.
]]></description>
<dc:subject>satisfiability algorithms computational-complexity machine-learning nudge-targets consider:looking-to-see consider:representation matrices</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:f4e2259c92b3/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:satisfiability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:machine-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1707.06356">
    <title>[1707.06356] Use of global interactions in efficient quantum circuit constructions</title>
    <dc:date>2017-09-28T00:10:41+00:00</dc:date>
    <link>https://arxiv.org/abs/1707.06356</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In this paper we study the ways to use a global entangling operator to efficiently implement circuitry common to a selection of important quantum algorithms. In particular, we focus on the circuits composed with global Ising entangling gates and arbitrary addressable single-qubit gates. We show that under certain circumstances the use of global operations can substantially improve the entangling gate count.
]]></description>
<dc:subject>quantum-computing engineering-design nudge-targets consider:primitives matrices algorithms</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:073526363b58/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:quantum-computing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:engineering-design"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:primitives"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1709.06079">
    <title>[1709.06079] Orthogonal Weight Normalization: Solution to Optimization over Multiple Dependent Stiefel Manifolds in Deep Neural Networks</title>
    <dc:date>2017-09-26T14:24:01+00:00</dc:date>
    <link>https://arxiv.org/abs/1709.06079</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Orthogonal matrix has shown advantages in training Recurrent Neural Networks (RNNs), but such matrix is limited to be square for the hidden-to-hidden transformation in RNNs. In this paper, we generalize such square orthogonal matrix to orthogonal rectangular matrix and formulating this problem in feed-forward Neural Networks (FNNs) as Optimization over Multiple Dependent Stiefel Manifolds (OMDSM). We show that the rectangular orthogonal matrix can stabilize the distribution of network activations and regularize FNNs. We also propose a novel orthogonal weight normalization method to solve OMDSM. Particularly, it constructs orthogonal transformation over proxy parameters to ensure the weight matrix is orthogonal and back-propagates gradient information through the transformation during training. To guarantee stability, we minimize the distortions between proxy parameters and canonical weights over all tractable orthogonal transformations. In addition, we design an orthogonal linear module (OLM) to learn orthogonal filter banks in practice, which can be used as an alternative to standard linear module. Extensive experiments demonstrate that by simply substituting OLM for standard linear module without revising any experimental protocols, our method largely improves the performance of the state-of-the-art networks, including Inception and residual networks on CIFAR and ImageNet datasets. In particular, we have reduced the test error of wide residual network on CIFAR-100 from 20.04% to 18.61% with such simple substitution. Our code is available online for result reproduction.
]]></description>
<dc:subject>machine-learning neural-networks learning algorithms matrices decomposition basis-functions to-understand consider:lexicase</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:8d1821ff5279/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:machine-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:neural-networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:decomposition"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:basis-functions"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:lexicase"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1108.2714">
    <title>[1108.2714] Approximate common divisors via lattices</title>
    <dc:date>2017-09-23T14:10:38+00:00</dc:date>
    <link>https://arxiv.org/abs/1108.2714</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We analyze the multivariate generalization of Howgrave-Graham's algorithm for the approximate common divisor problem. In the m-variable case with modulus N and approximate common divisor of size N^beta, this improves the size of the error tolerated from N^(beta^2) to N^(beta^((m+1)/m)), under a commonly used heuristic assumption. This gives a more detailed analysis of the hardness assumption underlying the recent fully homomorphic cryptosystem of van Dijk, Gentry, Halevi, and Vaikuntanathan. While these results do not challenge the suggested parameters, a 2^(n^epsilon) approximation algorithm with epsilon<2/3 for lattice basis reduction in n dimensions could be used to break these parameters. We have implemented our algorithm, and it performs better in practice than the theoretical analysis suggests. 
Our results fit into a broader context of analogies between cryptanalysis and coding theory. The multivariate approximate common divisor problem is the number-theoretic analogue of multivariate polynomial reconstruction, and we develop a corresponding lattice-based algorithm for the latter problem. In particular, it specializes to a lattice-based list decoding algorithm for Parvaresh-Vardy and Guruswami-Rudra codes, which are multivariate extensions of Reed-Solomon codes. This yields a new proof of the list decoding radii for these codes.]]></description>
<dc:subject>algorithms number-theory rather-interesting to-write-about to-understand nudge-targets consider:rediscovery approximation matrices</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:9c9ff512d578/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:number-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:rediscovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1203.2377">
    <title>[1203.2377] Matrix Stretching for Linear Equations</title>
    <dc:date>2017-09-19T11:36:40+00:00</dc:date>
    <link>https://arxiv.org/abs/1203.2377</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Stretching is a new sparse matrix method that makes matrices sparser by making them larger. Stretching has implications for computational complexity theory and applications in scientific and parallel computing. It changes matrix sparsity patterns to render linear equations more easily solved by parallel and sparse techniques. Some stretchings increase matrix condition numbers only moderately, and thus solve linear equations stably. For example, these stretchings solve arrow equations with accuracy and expense preferable to other solution methods.
]]></description>
<dc:subject>matrices algorithms representation rather-interesting out-of-the-box nudge-targets consider:rediscovery consider:performance-measures linear-algebra</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:90c9f32b2072/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:out-of-the-box"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:rediscovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:performance-measures"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:linear-algebra"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1605.08107">
    <title>[1605.08107] Dominance Products and Faster Algorithms for High-Dimensional Closest Pair under $L_infty$</title>
    <dc:date>2017-05-09T17:00:42+00:00</dc:date>
    <link>https://arxiv.org/abs/1605.08107</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We give improved algorithmic time bounds for two fundamental problems, and establish a new complexity connection between them. The first is computing dominance product: given a set of n points p1,…,pn in ℝd, compute a matrix D, such that D[i,j]=∣∣{k∣pi[k]≤pj[k]}∣∣; this is the number of coordinates at which pj dominates pi. Dominance product computation has often been applied in algorithm design over the last decade. 
The second problem is the L∞ Closest Pair in high dimensions: given a set S of n points in ℝd, find a pair of distinct points in S at minimum distance under the L∞ metric. When d is constant, there are efficient algorithms that solve this problem, and fast approximate solutions are known for general d. However, obtaining an exact solution in very high dimensions seems to be much less understood. We significantly simplify and improve previous results, showing that the problem can be solved by a deterministic strongly-polynomial algorithm that runs in O(DP(n,d)logn) time, where DP(n,d) is the time bound for computing the dominance product for n points in ℝd. For integer coordinates from some interval [−M,M], and for d=nr for some r>0, we obtain an algorithm that runs in Õ (min{Mnω(1,r,1),DP(n,d)}) time, where ω(1,r,1) is the exponent of multiplying an n×nr matrix by an nr×n matrix.
]]></description>
<dc:subject>multiobjective-optimization matrices algorithms rather-interesting to-understand consider:lexicase</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:add9ec716f6f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:multiobjective-optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:lexicase"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1608.04481">
    <title>[1608.04481] Lecture Notes on Randomized Linear Algebra</title>
    <dc:date>2017-05-09T16:05:40+00:00</dc:date>
    <link>https://arxiv.org/abs/1608.04481</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[These are lecture notes that are based on the lectures from a class I taught on the topic of Randomized Linear Algebra (RLA) at UC Berkeley during the Fall 2013 semester.
]]></description>
<dc:subject>matrices linear-algebra stochastic-systems algorithms optimization to-understand to-read consider:lexicase</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:f823aa119715/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:linear-algebra"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:stochastic-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:lexicase"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1104.5557">
    <title>[1104.5557] Randomized algorithms for matrices and data</title>
    <dc:date>2017-05-09T16:02:22+00:00</dc:date>
    <link>https://arxiv.org/abs/1104.5557</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Randomized algorithms for very large matrix problems have received a great deal of attention in recent years. Much of this work was motivated by problems in large-scale data analysis, and this work was performed by individuals from many different research communities. This monograph will provide a detailed overview of recent work on the theory of randomized matrix algorithms as well as the application of those ideas to the solution of practical problems in large-scale data analysis. An emphasis will be placed on a few simple core ideas that underlie not only recent theoretical advances but also the usefulness of these tools in large-scale data applications. Crucial in this context is the connection with the concept of statistical leverage. This concept has long been used in statistical regression diagnostics to identify outliers; and it has recently proved crucial in the development of improved worst-case matrix algorithms that are also amenable to high-quality numerical implementation and that are useful to domain scientists. Randomized methods solve problems such as the linear least-squares problem and the low-rank matrix approximation problem by constructing and operating on a randomized sketch of the input matrix. Depending on the specifics of the situation, when compared with the best previously-existing deterministic algorithms, the resulting randomized algorithms have worst-case running time that is asymptotically faster; their numerical implementations are faster in terms of clock-time; or they can be implemented in parallel computing environments where existing numerical algorithms fail to run at all. Numerous examples illustrating these observations will be described in detail.
]]></description>
<dc:subject>via:arthegall data-analysis matrices feature-extraction learning-from-data data-mining rather-interesting to-read to-understand</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:39273ba6e6fb/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:via:arthegall"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:data-analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-extraction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:learning-from-data"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:data-mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1505.07363">
    <title>[1505.07363] An Enumeration of the Equivalence Classes of Self-Dual Matrix Codes</title>
    <dc:date>2017-05-07T14:37:34+00:00</dc:date>
    <link>https://arxiv.org/abs/1505.07363</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[As a result of their applications in network coding, space-time coding, and coding for criss-cross errors, matrix codes have garnered significant attention; in various contexts, these codes have also been termed rank-metric codes, space-time codes over finite fields, and array codes. We focus on characterizing matrix codes that are both efficient (have high rate) and effective at error correction (have high minimum rank-distance). It is well known that the inherent trade-off between dimension and minimum distance for a matrix code is reversed for its dual code; specifically, if a matrix code has high dimension and low minimum distance, then its dual code will have low dimension and high minimum distance. With an aim towards finding codes with a perfectly balanced trade-off, we study self-dual matrix codes. In this work, we develop a framework based on double cosets of the matrix-equivalence maps to provide a complete classification of the equivalence classes of self-dual matrix codes, and we employ this method to enumerate the equivalence classes of these codes for small parameters.
]]></description>
<dc:subject>information-theory matrices combinatorics rather-interesting to-write-about nudge-targets consider:feature-discovery consider:rediscovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:f02b8eadee8b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:information-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:feature-discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:rediscovery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1704.00708">
    <title>[1704.00708] No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis</title>
    <dc:date>2017-05-07T12:12:16+00:00</dc:date>
    <link>https://arxiv.org/abs/1704.00708</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In this paper we develop a new framework that captures the common landscape underlying the common non-convex low-rank matrix problems including matrix sensing, matrix completion and robust PCA. In particular, we show for all above problems (including asymmetric cases): 1) all local minima are also globally optimal; 2) no high-order saddle points exists. These results explain why simple algorithms such as stochastic gradient descent have global converge, and efficiently optimize these non-convex objective functions in practice. Our framework connects and simplifies the existing analyses on optimization landscapes for matrix sensing and symmetric matrix completion. The framework naturally leads to new results for asymmetric matrix completion and robust PCA.
]]></description>
<dc:subject>compressed-sensing matrices optimization approximation rather-interesting machine-learning nudge-targets consider:representation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:7f006b0b1a17/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:compressed-sensing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:machine-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:representation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1605.08629">
    <title>[1605.08629] On Block Representations and Spectral Properties of Semimagic Square Matrices</title>
    <dc:date>2017-04-22T11:42:08+00:00</dc:date>
    <link>https://arxiv.org/abs/1605.08629</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Using the decomposition of semimagic squares into the associated and balanced symmetry types as a motivation, we introduce an equivalent representation in terms of block-structured matrices. This block representation provides a way of constructing such matrices with further symmetries and of studying their algebraic behaviour, significantly advancing and contributing to the understanding of these symmetry properties. In addition to studying classical attributes, such as dihedral equivalence and the spectral properties of these matrices, we show that the inherent structure of the block representation facilitates the definition of low-rank semimagic square matrices. This is achieved by means of tensor product blocks. Furthermore, we study the rank and eigenvector decomposition of these matrices, enabling the construction of a corresponding two-sided eigenvector matrix in rational terms of their entries. The paper concludes with the derivation of a correspondence between the tensor product block representations and quadratic form expressions of Gaussian type.]]></description>
<dc:subject>matrices magic-squares combinatorics feature-construction to-write-about nudge-targets consider:looking-to-see</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:6d799ff42368/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:magic-squares"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1702.06166">
    <title>[1702.06166] Bayesian Boolean Matrix Factorisation</title>
    <dc:date>2017-04-05T11:33:06+00:00</dc:date>
    <link>https://arxiv.org/abs/1702.06166</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Boolean matrix factorisation aims to decompose a binary data matrix into an approximate Boolean product of two low rank, binary matrices: one containing meaningful patterns, the other quantifying how the observations can be expressed as a combination of these patterns. We introduce the OrMachine, a probabilistic generative model for Boolean matrix factorisation and derive a Metropolised Gibbs sampler that facilitates efficient parallel posterior inference. On real world and simulated data, our method outperforms all currently existing approaches for Boolean matrix factorisation and completion. This is the first method to provide full posterior inference for Boolean Matrix factorisation which is relevant in applications, e.g. for controlling false positive rates in collaborative filtering and, crucially, improves the interpretability of the inferred patterns. The proposed algorithm scales to large datasets as we demonstrate by analysing single cell gene expression data in 1.3 million mouse brain cells across 11 thousand genes on commodity hardware.
]]></description>
<dc:subject>matrices inverse-problems rather-interesting statistics inference nudge-targets consider:looking-to-see</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:19ad4ea76fbb/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inverse-problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inference"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1202.4358">
    <title>[1202.4358] Natural Product Xn on matrices</title>
    <dc:date>2017-03-24T00:54:34+00:00</dc:date>
    <link>https://arxiv.org/abs/1202.4358</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[This book has eight chapters. The first chapter is introductory in nature. Polynomials with matrix coefficients are introduced in chapter two. Algebraic structures on these polynomials with matrix coefficients is defined and described in chapter three. Chapter four introduces natural product on matrices. Natural product on super matrices is introduced in chapter five. Super matrix linear algebra is introduced in chapter six. Chapter seven claims only after this notion becomes popular we can find interesting applications of them. The final chapter suggests over 100 problems some of which are at research level.
]]></description>
<dc:subject>matrices algebra open-questions rather-interesting book nudge-targets consider:looking-to-see</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:0aa13e0f4519/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algebra"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:open-questions"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:book"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.mathrecreation.com/2016/11/polynomial-grid-division-examples.html">
    <title>mathrecreation: polynomial grid division examples</title>
    <dc:date>2017-03-23T23:11:41+00:00</dc:date>
    <link>http://www.mathrecreation.com/2016/11/polynomial-grid-division-examples.html</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[There are not enough examples of polynomial division using the grid method out there. To remedy that, I have posted about 100 billion examples for your viewing pleasure. Please check ‘em out: https://dmackinnon1.github.io/polygrid/

Jokes aside, I was looking for a small JavaScript project, and this one looked like it would be fun. It was, and I learned a few things by building it. The page will generate a small number of examples, but you can get a fresh batch by reloading. Each example is calculated on the fly, and rendered using MathJax. Currently, the displayed calculations look like this:
]]></description>
<dc:subject>matrices javascript visualization nudge-targets to-write-about algorithms</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:50c2ffe034c9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:javascript"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:visualization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1703.00998">
    <title>[1703.00998] randUTV: A blocked randomized algorithm for computing a rank-revealing UTV factorization</title>
    <dc:date>2017-03-08T13:07:23+00:00</dc:date>
    <link>https://arxiv.org/abs/1703.00998</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[This manuscript describes the randomized algorithm randUTV for computing a so called UTV factorization efficiently. Given a matrix A, the algorithm computes a factorization A=UTV∗, where U and V have orthonormal columns, and T is triangular (either upper or lower, whichever is preferred). The algorithm randUTV is developed primarily to be a fast and easily parallelized alternative to algorithms for computing the Singular Value Decomposition (SVD). randUTV provides accuracy very close to that of the SVD for problems such as low-rank approximation, solving ill-conditioned linear systems, determining bases for various subspaces associated with the matrix, etc. Moreover, randUTV produces highly accurate approximations to the singular values of A. Unlike the SVD, the randomized algorithm proposed builds a UTV factorization in an incremental, single-stage, and non-iterative way, making it possible to halt the factorization process once a specified tolerance has been met. Numerical experiments comparing the accuracy and speed of randUTV to the SVD are presented. These experiments demonstrate that in comparison to column pivoted QR, which is another factorization that is often used as a relatively economic alternative to the SVD, randUTV compares favorably in terms of speed while providing far higher accuracy.]]></description>
<dc:subject>matrices algorithms numerical-methods to-understand nudge-targets consider:representation consider:libraries consider:looking-to-see</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:294e01fda515/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:numerical-methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:libraries"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1701.01207">
    <title>[1701.01207] A Matrix Factorization Approach for Learning Semidefinite-Representable Regularizers</title>
    <dc:date>2017-01-15T12:38:47+00:00</dc:date>
    <link>https://arxiv.org/abs/1701.01207</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Regularization techniques are widely employed in optimization-based approaches for solving ill-posed inverse problems in data analysis and scientific computing. These methods are based on augmenting the objective with a penalty function, which is specified based on prior domain-specific expertise to induce a desired structure in the solution. We consider the problem of learning suitable regularization functions from data in settings in which precise domain knowledge is not directly available. Previous work under the title of `dictionary learning' or `sparse coding' may be viewed as learning a regularization function that can be computed via linear programming. We describe generalizations of these methods to learn regularizers that can be computed and optimized via semidefinite programming. Our framework for learning such semidefinite regularizers is based on obtaining structured factorizations of data matrices, and our algorithmic approach for computing these factorizations combines recent techniques for rank minimization problems along with an operator analog of Sinkhorn scaling. Under suitable conditions on the input data, our algorithm provides a locally linearly convergent method for identifying the correct regularizer that promotes the type of structure contained in the data. Our analysis is based on the stability properties of Operator Sinkhorn scaling and their relation to geometric aspects of determinantal varieties (in particular tangent spaces with respect to these varieties). The regularizers obtained using our framework can be employed effectively in semidefinite programming relaxations for solving inverse problems.
]]></description>
<dc:subject>matrices inverse-problems approximation algorithms nudge-targets consider:looking-to-see to-write-about consider:representation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:3677f1937209/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inverse-problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:representation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1611.01120">
    <title>[1611.01120] Generating Families of Practical Fast Matrix Multiplication Algorithms</title>
    <dc:date>2016-12-31T13:09:11+00:00</dc:date>
    <link>https://arxiv.org/abs/1611.01120</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Matrix multiplication (GEMM) is a core operation to numerous scientific applications. Traditional implementations of Strassen-like fast matrix multiplication (FMM) algorithms often do not perform well except for very large matrix sizes, due to the increased cost of memory movement, which is particularly noticeable for non-square matrices. Such implementations also require considerable workspace and modifications to the standard BLAS interface. We propose a code generator framework to automatically implement a large family of FMM algorithms suitable for multiplications of arbitrary matrix sizes and shapes. By representing FMM with a triple of matrices [U,V,W] that capture the linear combinations of submatrices that are formed, we can use the Kronecker product to define a multi-level representation of Strassen-like algorithms. Incorporating the matrix additions that must be performed for Strassen-like algorithms into the inherent packing and micro-kernel operations inside GEMM avoids extra workspace and reduces the cost of memory movement. Adopting the same loop structures as high-performance GEMM implementations allows parallelization of all FMM algorithms with simple but efficient data parallelism without the overhead of task parallelism. We present a simple performance model for general FMM algorithms and compare actual performance of 20+ FMM algorithms to modeled predictions. Our implementations demonstrate a performance benefit over conventional GEMM on single core and multi-core systems. This study shows that Strassen-like fast matrix multiplication can be incorporated into libraries for practical use.
]]></description>
<dc:subject>genetic-programming rather-interesting matrices algorithms representation nudge-targets consider:looking-to-see consider:comparing-theory-and-practice</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:17b27978d74c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:genetic-programming"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:comparing-theory-and-practice"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1602.02262">
    <title>[1602.02262] Recovery guarantee of weighted low-rank approximation via alternating minimization</title>
    <dc:date>2016-12-25T23:09:51+00:00</dc:date>
    <link>https://arxiv.org/abs/1602.02262</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Many applications require recovering a ground truth low-rank matrix from noisy observations of the entries, which in practice is typically formulated as a weighted low-rank approximation problem and solved by non-convex optimization heuristics such as alternating minimization. In this paper, we provide provable recovery guarantee of weighted low-rank via a simple alternating minimization algorithm. In particular, for a natural class of matrices and weights and without any assumption on the noise, we bound the spectral norm of the difference between the recovered matrix and the ground truth, by the spectral norm of the weighted noise plus an additive error that decreases exponentially with the number of rounds of alternating minimization, from either initialization by SVD or, more importantly, random initialization. These provide the first theoretical results for weighted low-rank via alternating minimization with non-binary deterministic weights, significantly generalizing those for matrix completion, the special case with binary weights, since our assumptions are similar or weaker than those made in existing works. Furthermore, this is achieved by a very simple algorithm that improves the vanilla alternating minimization with a simple clipping step. 
The key technical challenge is that under non-binary deterministic weights, na\"ive alternating steps will destroy the incoherence and spectral properties of the intermediate solutions, which are needed for making progress towards the ground truth. We show that the properties only need to hold in an average sense and can be achieved by the clipping step. 
We further provide an alternating algorithm that uses a whitening step that keeps the properties via SDP and Rademacher rounding and thus requires weaker assumptions. This technique can potentially be applied in some other applications and is of independent interest.
]]></description>
<dc:subject>matrices approximation dimension-reduction compressed-sensing algorithms nudge-targets consider:looking-to-see consider:representation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:5bb405998c9b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:dimension-reduction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:compressed-sensing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:representation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1610.06145">
    <title>[1610.06145] A global optimization algorithm for sparse mixed membership matrix factorization</title>
    <dc:date>2016-12-23T12:41:12+00:00</dc:date>
    <link>https://arxiv.org/abs/1610.06145</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Mixed membership factorization is a popular approach for analyzing data sets that have within-sample heterogeneity. In recent years, several algorithms have been developed for mixed membership matrix factorization, but they only guarantee estimates from a local optimum. Here, we derive a global optimization (GOP) algorithm that provides a guaranteed ϵ-global optimum for a sparse mixed membership matrix factorization problem. We test the algorithm on simulated data and find the algorithm always bounds the global optimum across random initializations and explores multiple modes efficiently.
]]></description>
<dc:subject>matrices algorithms mathematical-programming optimization performance-measure constraint-satisfaction rather-interesting nudge-targets consider:looking-to-see consider:representation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:3ac8ef929501/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-programming"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:performance-measure"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:constraint-satisfaction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:representation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1609.05034">
    <title>[1609.05034] What You Will Gain By Rounding: Theory and Algorithms for Rounding Rank</title>
    <dc:date>2016-10-03T10:00:58+00:00</dc:date>
    <link>https://arxiv.org/abs/1609.05034</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[When analyzing discrete data such as binary matrices using matrix factorizations, we often have to make a choice between using expensive combinatorial methods that retain the discrete nature of the data and using continuous methods that can be more efficient but destroy the discrete structure. Alternatively, we can first compute a continuous factorization and subsequently apply a rounding procedure to obtain a discrete representation. But what will we gain by rounding? Will this yield lower reconstruction errors? Is it easy to find a low-rank matrix that rounds to a given binary matrix? Does it matter which threshold we use for rounding? Does it matter if we allow for only non-negative factorizations? In this paper, we approach these and further questions by presenting and studying the concept of rounding rank. We show that rounding rank is related to linear classification, dimensionality reduction, and nested matrices. We also report on an extensive experimental study that compares different algorithms for finding good factorizations under the rounding rank model.
]]></description>
<dc:subject>approximation matrices numerical-methods algorithms rather-interesting nudge-targets consider:looking-to-see</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:3ad9459432c2/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:numerical-methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1607.06303">
    <title>[1607.06303] High-Performance Algorithms for Computing the Sign Function of Triangular Matrices</title>
    <dc:date>2016-09-13T11:24:02+00:00</dc:date>
    <link>http://arxiv.org/abs/1607.06303</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Algorithms and implementations for computing the sign function of a triangular matrix are fundamental building blocks in algorithms for computing the sign of arbitrary square real or complex matrices. We present novel recursive and cache efficient algorithms that are based on Higham's stabilized specialization of Parlett's substitution algorithm for computing the sign of a triangular matrix. We show that the new recursive algorithms are asymptotically optimal in terms of the number of cache misses that they generate. One of the novel algorithms that we present performs more arithmetic than the non-recursive version, but this allows it to benefit from calling highly-optimized matrix-multiplication routines; the other performs the same number of operations as the non-recursive version, but it uses custom computational kernels instead. We present implementations of both, as well as a cache-efficient implementation of a block version of Parlett's algorithm. Our experiments show that the blocked and recursive versions are much faster than the previous algorithms, and that the inertia strongly influences their relative performance, as predicted by our analysis.
]]></description>
<dc:subject>matrices numerical-methods computational-complexity rather-interesting algorithms nudge-targets consider:looking-to-see</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:b53f67877b0f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:numerical-methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1602.00061">
    <title>[1602.00061] Spectrum Estimation from Samples</title>
    <dc:date>2016-08-06T13:03:36+00:00</dc:date>
    <link>http://arxiv.org/abs/1602.00061</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We consider the problem of approximating the set of eigenvalues of the covariance matrix of a multivariate distribution (equivalently, the problem of approximating the "population spectrum"), given access to samples drawn from the distribution. The eigenvalues of the covariance of a distribution contain basic information about the distribution, including the presence or lack of structure in the distribution, the effective dimensionality of the distribution, and the applicability of higher-level machine learning and multivariate statistical tools. We consider this fundamental recovery problem in the regime where the number of samples is comparable, or even sublinear in the dimensionality of the distribution in question. First, we propose a theoretically optimal and computationally efficient algorithm for recovering the moments of the eigenvalues of the population covariance matrix. We then leverage this accurate moment recovery, via a Wasserstein distance argument, to show that the vector of eigenvalues can be accurately recovered. Specifically, we show that our eigenvalue reconstruction algorithm is asymptotically consistent as the dimensionality of the distribution and sample size tend towards infinity, even in the sublinear sample regime where the ratio of the sample size to the dimensionality tends to zero. In addition to our theoretical results, we show that our approach performs well in practice for a broad range of distributions and sample sizes.
]]></description>
<dc:subject>matrices learning-from-data inference nudge-targets algorithms inverse-problems consider:feature-discovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:57b9af7313ac/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:learning-from-data"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inference"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inverse-problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:feature-discovery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1509.07766">
    <title>[1509.07766] When a local Hamiltonian must be frustration-free</title>
    <dc:date>2016-06-29T11:57:30+00:00</dc:date>
    <link>http://arxiv.org/abs/1509.07766</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[A broad range of quantum optimisation problems can be phrased as the question whether a specific system has a ground state at zero energy, i.e.\ whether its Hamiltonian is frustration free. Frustration-free Hamiltonians, in turn, play a central role for constructing and understanding new phases of matter in quantum many-body physics. Unfortunately, determining whether this is the case is known to be a complexity-theoretically intractable problem. This makes it highly desirable to search for efficient heuristics and algorithms in order to, at least, partially answer this question. Here we prove a general criterion - a sufficient condition - under which a local Hamiltonian is guaranteed to be frustration free by lifting Shearer's theorem from classical probability theory to the quantum world. Remarkably, evaluating this condition proceeds via a fully classical analysis of a hard-core lattice gas at negative fugacity on the Hamiltonian's interaction graph which, as a statistical mechanics problem, is of interest in its own right. We concretely apply this criterion to local Hamiltonians on various regular lattices, while bringing to bear the tools of spin glass physics which permit us to obtain new bounds on the SAT/UNSAT transition in random quantum satisfiability. These also lead us to natural conjectures for when such bounds will be tight, as well as to a novel notion of universality for these computer science problems. Besides providing concrete algorithms leading to detailed and quantitative insights, this underscores the power of marrying classical statistical mechanics with quantum computation and complexity theory.
]]></description>
<dc:subject>quantums matrices quantum-computing feature-construction rather-interesting nudge-targets consider:for-push</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:82d694d992c6/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:quantums"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:quantum-computing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:for-push"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1605.01695">
    <title>[1605.01695] Faster Online Matrix-Vector Multiplication</title>
    <dc:date>2016-05-11T12:14:59+00:00</dc:date>
    <link>http://arxiv.org/abs/1605.01695</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We consider the Online Boolean Matrix-Vector Multiplication (OMV) problem studied by Henzinger et al. [STOC'15]: given an n×n Boolean matrix M, we receive n Boolean vectors v1,…,vn one at a time, and are required to output Mvi (over the Boolean semiring) before seeing the vector vi+1, for all i. Previous known algorithms for this problem are combinatorial, running in O(n3/log2n) time. Henzinger et al. conjecture there is no O(n3−ε) time algorithm for OMV, for all ε>0; their OMV conjecture is shown to imply strong hardness results for many basic dynamic problems. 
We give a substantially faster method for computing OMV, running in n3/2Ω(logn√) randomized time. In fact, after seeing 2ω(logn√) vectors, we already achieve n2/2Ω(logn√) amortized time for matrix-vector multiplication. Our approach gives a way to reduce matrix-vector multiplication to solving a version of the Orthogonal Vectors problem, which in turn reduces to "small" algebraic matrix-matrix multiplication. Applications include faster independent set detection, partial match retrieval, and 2-CNF evaluation. 
We also show how a modification of our method gives a cell probe data structure for OMV with worst case O(n7/4/w‾‾√) time per query vector, where w is the word size. This result rules out an unconditional proof of the OMV conjecture using purely information-theoretic arguments.
]]></description>
<dc:subject>algorithms numerical-methods horse-races matrices nudge-targets consider:looking-to-see consider:rediscovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:0b3b4abc043f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:numerical-methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:horse-races"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:rediscovery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1407.3254">
    <title>[1407.3254] Matrix Completion for the Independence Model</title>
    <dc:date>2016-05-09T11:15:41+00:00</dc:date>
    <link>http://arxiv.org/abs/1407.3254</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We investigate the problem of completing partial matrices to rank-one matrices in the standard simplex. The motivation for studying this problem comes from statistics: A lack of eligible completion can provide a falsification test for partial observations to come from the independence model. For each pattern of specified entries, we give equations and inequalities which are satisfied if and only if an eligible completion exists. We also describe the set of valid completions, and we optimize over this set.
]]></description>
<dc:subject>matrices inference inverse-problems number-theory algebra probability-theory rather-interesting nudge-targets consider:looking-to-see consider:feature-discovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:97f232b90f5e/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inference"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inverse-problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:number-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algebra"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:probability-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:feature-discovery"/>
</rdf:Bag></taxo:topics>
</item>
</rdf:RDF>