Music and media search spell correction is distinct as it involves named entities like artist, album and podcast names, keywords from track titles and catchy phrases from lyrics. Users often mix artist names and keywords from track title or lyrics making spell correction highly contextual. Data drift in search queries caused during calendar event days or a newly released music album, brings a unique challenge of quickly adapting to new data points. Scalability of the solution is an essential requirement as the Music catalog is extremely large. In this work, we build a multi-stage framework for spell correction solution for music, media and named entity heavy search engines. We offer contextual spelling suggestions using a generative text transformer model and a mechanism to rapidly adapt to data drift as well as different market needs by using parameter efficient based fine tuning techniques. Furthermore, using a reinforcement learning approach our spell correction system can learn from a user's implicit and explicit feedback in real-time. Some key components of this system are being used in search at Amazon Music and showing significant improvements in customer engagement rate and other relevant metrics.

We consider a variation of the well known problem of computing the unique solution to a nonsingular system Ax=b of n linear equations over a field K. The variation assumes that A has generic rank profile and requires as output not only the single solution vector A-1b Ε Kn x 1, but rather the solution to all leading principle subsystems. Most importantly, the rows of the augmented system [A||b] are given one at a time from first to last, and as soon as the next row is given the solution to the next leading principal subsystem should be produced. We call this problem ONLINESYSTEM. The obvious iterative algorithm for ONLINESYSTEM has a cost in terms of field operations that is cubic in the dimension of A. In this paper we introduce a relaxed representation for the inverse and show how to obtain an algorithm for ONLINESYSTEM that allows us to incorporate matrix multiplication. As an application we show how to introduce fast matrix multiplication into the inherently iterative algorithm for row rank profile computation presented previously by the authors.

Randomized algorithms are given for linear algebra problems on an input matrix A ∈ Knxm over a field K. We give an algorithm that simultaneously computes the row and column rank profiles of A in 2r3 + (r2 + n + m + |A|)1+o(1) field operations from K, where r is the rank of A and |A| denotes the number of nonzero entries of A. Here, the +o(1) in cost estimates captures some missing log n and log m factors. The rank profiles algorithm is randomized of the Monte Carlo type: the correct answer will be returned with probability at least 1/2. Given a b ∈ Knx1, we give an algorithm that either computes a particular solution vector x ∈ Kmx1 to the system Ax = b, or produces an inconsistency certificate vector u ∈ K1xn such that uA = 0 and ub ≠ 0. The linear solver examines at most r + 1 rows and r columns of A and has running time 2r3 + (r2 + n + m + |R| + |C|)1+o(1) field operations from K, where |R| and |C| are the number of nonzero entries in the rows and columns, respectively, that are examined. The solver is randomized of the Las Vegas type: an incorrect result is never returned but the algorithm may report FAIL with probability at most 1/2. These cost estimates are achieved by making use of a novel randomized online data structure for the detection of linearly independent rows and columns.