Trace in non-orthogonal basis? Physicists define the trace of an operator $\rho$ as the follows,

$Tr(\rho)=\sum\limits_{|s\rangle \in B} \langle s| \rho |s\rangle$

where $B$ is some orthonormal basis, and this quantity is basis independent.
If we swapped $B$ with a non-orthogonal basis $C$, which, if any, of the properties of the trace will be preserved? In particular,


*
1) Is it now basis dependent? (The intuitive answer seems to be YES, but can we do better?) 

* 2) Under what conditions (on $C$ and $\rho$) will this value exceed the value of the actual trace? I will settle for an answer assuming $\rho$ is a density operator.
 A: The trace defined as you did in the initial equation in your question is well defined, i.e. independent from the basis when the basis is orthonormal. Otherwise that formula gives rise to a number which depends on the basis (if non-orthonormal) and does not has much interest in physics. If you want to use non-orthonormal bases, you should adopt a different definition involving the dual basis: if $\{\psi_n\}$ is a generic basis, its dual basis is defined as another basis $\{\phi_n\}$ with $\langle \phi_n|\psi_m\rangle = \delta_{nm}$. In this case, the trace of $\rho$, the same obtained with your formula for orthonormal basis (in that case $\phi_n=\psi_n$) is:
$$tr \rho = \sum_{n} \langle \phi_n | \rho \psi_n \rangle\:.$$ 
Everything I wrote holds for finite dimension, otherwise some further requirements on operators have to hold true.
ADDENDUM. (I am still considering the finite dimensional case with dimension $N>1$.) Using your definition of trace, let us indicate it by $Tr_C(\rho)$, you can always find $\rho$ and a non-orthogonal basis $C$ with $Tr_C(\rho)> tr(\rho)$. As an example pick out $\rho = |\psi \rangle \langle \psi |$ with $||\psi||=1$, so that $\rho$ is a pure state. Next fix a cone $V$  tightly concentrated around $\psi$. As every cone always includes a normalized basis, for every $\epsilon \in (0,1)$, suitably concentrating  $V$ around $\psi$ you can find a normalized basis $C:= \{\phi_n\}_{n=1,\ldots, N} \subset V$ with  $||\psi -\phi_n||^2 > 1-\epsilon$.
Consequently:
$$Tr_C(\rho) = \sum_{n}|\langle \psi|\phi_n\rangle|^2 > N(1-\epsilon) > 1 = tr (\rho)\:.$$ 
This is particularly evident for $N=2$, using $\phi_1:= \psi$ and $\phi_2$ close to $\phi_1$.
A: You can compute the trace of an endomorphism using any basis (including non-orthogonal ones).
In Dirac notation, you show this by inserting the identity expressed in the new basis and re-arranging:
$$\begin{align*}
\sum\limits_{|s\rangle \in B} \langle s^*| \rho |s\rangle
&= \sum\limits_{|s\rangle \in B} \langle s^*| \left( \sum\limits_{|t\rangle \in C} |t\rangle\langle t^*| \right) \rho |s\rangle
\\&= \sum\limits_{|s\rangle \in B} \sum\limits_{|t\rangle \in C}  \langle s^*|t\rangle\langle t^*| \rho |s\rangle
\\&= \sum\limits_{|s\rangle \in B} \sum\limits_{|t\rangle \in C} \langle t^*| \rho |s\rangle \langle s^*|t\rangle
\\&= \sum\limits_{|t\rangle \in C} \langle t^*| \rho \left( \sum\limits_{|s\rangle \in B} |s\rangle \langle s^*| \right)  |t\rangle
\\&= \sum\limits_{|t\rangle \in C} \langle t^*| \rho |t\rangle
\end{align*}$$
Here, I used the non-standard notation $\langle s^*|,\langle t^*|$ to denote the algebraically dual basis, which only consists of the bras $\langle s|,\langle t|$ if we started with an orthonormal one.
