3 votes

Alternatives to SVD for rank factorization

The proper search term in scientific journals is "Rank-Revealing Decomposition". If You want some theoretic guarantees on numeric accuracy/stability, the search term would be "Strong ...
DirkT's user avatar
  • 991
3 votes

How does numpy.linalg.inv calculate the inverse of a matrix?

The source code of this function is here, which is a wrapper for a C++ function here, which is calling some BLAS/LAPACK library functions. Specifically, in order to compute the inverse of a matrix $A$,...
Discrete lizard's user avatar
  • 8,248
3 votes

Can any SAT problem be converted to a system of linear equations over $\mathbf{Z}_2$?

Equivalence: Not every SAT instance can be expressed as a system of linear equations. For instance, $x_1 \lor x_2$ cannot be expressed as a system of linear equations. (Why not? Systems of linear ...
D.W.'s user avatar
  • 159k
2 votes
Accepted

Can a linear programming method be used to solve systems of inequalities with OR (disparate) compound inequalities?

First off, a couple of observations. If you allow three inequalities in each "compound inequality", then the problem of finding a feasible solution is NP-complete, since any 3-SAT problem ...
Pseudonym's user avatar
  • 22.1k
2 votes

Finding a vector of maximum Hamming distance from a subspace of $(\mathbb{Z}/2\mathbb{Z})^n$

Your problem is very likely NP-hard. If you don't add the restriction that $W$ is sub-space, but just receive a set of boolean vectors $W$, then it is NP-hard and known as a Covering Radius proven NP-...
Bernardo Subercaseaux's user avatar
1 vote

Given a set of points $S$ which is a subset of a vector space $V$, find the smallest subspace which intersect $S$ in at least $k$ points

In general, this problem is hard. For instance, if we have a vector space over $GF(2)$, then checking whether there is a one-dimensional subspace $A$ with the desired property is as hard as learning ...
D.W.'s user avatar
  • 159k
1 vote
Accepted

Strange notation in the article about sparse self-attention

The notation $$(x_i)_{i \in \{1,\dots,n\}}$$ is short-hand for $$(x_1,x_2,\dots,x_n).$$ Just two different ways to write the same thing. It is analogous to the relationship between $\sum_{i \in \{1,\...
D.W.'s user avatar
  • 159k
1 vote

Mathematical operation for removing duplicate rows in a matrix

A more efficient approach is to hash each row, insert them into a hash table, and find duplicates in that way. The running time will be $O(n^2)$. You can implement something like this using only ...
D.W.'s user avatar
  • 159k
1 vote
Accepted

Finding solution to Mv=v over $\mathbb{Z}$={0,1} for matrix M given a set linearly independent v

It is not possible. Such matrices don't exist. We always have $Mv=v$ whenever $v=0$ (the all-zeros vector). No set that contains the all-zeros vector is linearly independent, so surely $0 \notin V$....
D.W.'s user avatar
  • 159k
1 vote

Efficient algorithm for finding a vector to maximize the number of positive dot products with a given set (finding the maximum overlap of half-spaces)

If I understand your question correctly, you are describing a problem that is almost identical to the optimization problem in Support Vector Machines. The only difference is that in your case the ...
DirkT's user avatar
  • 991
1 vote

Solving systems of linear equations over semirings

Even for the canonical example of a semiring, $\mathbb N$, solving linear equations is hard; in a sense, NP-hard. See 0-1 Knapsack Problem, and Integer Knapsack Problem (Papadimitriou and Steiglitz, ...
Bjørn Kjos-Hanssen's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible