Sachverhalt:
Sachverhalt:
A. Seit 1. Februar 1986 ist A._ (Beschwerdeführer) Mieter einer Vierzimmerwohnung in der Liegenschaft Y._. Vermieterin ist die Liegenschaftenverwaltung der Stadt-Basel (Beschwerdegegnerin). Seit 1. Juli 1995 ist der Beschwerdeführer zusätzlich Mieter von zwei Mansardenzimmern in derselben Liegenschaft. Bei den Mietobjekten handelt es sich um ehemalige Kommunalwohnungen. Die Mieter dieser Wohnungen profitierten unabhängig von ihren finanziellen Verhältnissen von grundverbilligten Mietzinsen. Der aktuelle Nettomietzins für die Vierzimmerwohnung beträgt Fr. 476.-- und für die beiden Mansardenzimmer je Fr. 75.--.
Am 1. Januar 1995 sind das Mietbeitragsgesetz (MBG, SG 890.500) und die Mietbeitragsverordnung (MIVO, SG 890.510) in Kraft getreten. Dadurch änderte sich das System insofern, als jetzt nicht mehr Wohnungen subventioniert werden, sondern die einzelnen Mieter finanzielle Hilfe erhalten, soweit sie diese benötigen.
Mit amtlichem Formular vom 11. September 2000 teilte die Beschwerdegegnerin dem Beschwerdeführer eine Erhöhung des Nettomietzinses für die Vierzimmerwohnung per 1. Mai 2001 von Fr. 476.-- auf Fr. 662.-- mit. Die Erhöhung wurde mit einer Anpassung an die orts- und quartierüblichen Mietzinsen begründet. Mit gleicher Begründung wurden auch die Mieten für die Mansardenzimmer von Fr. 75.-- auf je Fr. 121.-- erhöht.
Mit amtlichem Formular vom 11. September 2000 teilte die Beschwerdegegnerin dem Beschwerdeführer eine Erhöhung des Nettomietzinses für die Vierzimmerwohnung per 1. Mai 2001 von Fr. 476.-- auf Fr. 662.-- mit. Die Erhöhung wurde mit einer Anpassung an die orts- und quartierüblichen Mietzinsen begründet. Mit gleicher Begründung wurden auch die Mieten für die Mansardenzimmer von Fr. 75.-- auf je Fr. 121.-- erhöht.
B. Diese Mietzinserhöhung wurde vom Beschwerdeführer bei der Staatlichen Schlichtungsstelle für Mietstreitigkeiten angefochten. Nachdem keine Einigung erzielt werden konnte, erhob die Beschwerdegegnerin beim Zivilgerichtspräsidenten Klage. Mit Urteil vom 12. Juli 2001 wurde festgestellt, dass der Nettomietzins für die Vierzimmerwohnung mit Wirkung ab 1. Mai 2001 Fr. 662.-- sowie für die beiden Mansarden je Fr. 121.-- jeweils zuzüglich Nebenkosten betrage. Eine vom Beschwerdeführer gegen dieses Urteil erhobene Beschwerde hiess das Appellationsgericht des Kantons Basel-Stadt mit Urteil vom 16. August 2002 gut, hob das Urteil des Zivilgerichtspräsidenten vom 12. Juli 2001 auf, wies die Klage ab und stellte fest, dass die am 11. September 2000 per 1. Mai 2001 angekündigten Mietzinserhöhungen für die Vierzimmerwohnung und für die beiden Mansarden unzulässig bzw. nichtig seien. Gegen dieses Urteil erhob die Beschwerdegegnerin Berufung ans Bundesgericht und beanstandete die Feststellung der Nichtigkeit der Mietzinserhöhung für die Vierzimmerwohnung; in Bezug auf die Mansardenzimmer blieb das Urteil des Appellationsgerichtes vom 16. August 2002 unangefochten. Mit Urteil vom 31. Januar 2003 hiess das Bundesgericht die Berufung teilweise gut, hob das Urteil des Appellationsgerichtes des Kantons Basel-Stadt vom 16. August 2002 auf und wies die Sache zur Neuentscheidung ans Appellationsgericht zurück (4C.330/2002, publ. in MRA 2003 S. 39 ff.). Im Anschluss daran hiess das Appellationsgericht die Beschwerde des Beschwerdeführers mit Urteil vom 26. März 2003 teilweise gut und erklärte die Mietzinserhöhungen für die beiden Einzimmerwohnungen bzw. Mansarden für ungültig. Im Übrigen wurde die Beschwerde abgewiesen und das Urteil des Zivilgerichtspräsidenten insoweit bestätigt, als es einen Mietzins ab 1. Mai 2001 von Fr. 662.-- für die Vierzimmerwohnung als nicht missbräuchlich bezeichnete.
B. Diese Mietzinserhöhung wurde vom Beschwerdeführer bei der Staatlichen Schlichtungsstelle für Mietstreitigkeiten angefochten. Nachdem keine Einigung erzielt werden konnte, erhob die Beschwerdegegnerin beim Zivilgerichtspräsidenten Klage. Mit Urteil vom 12. Juli 2001 wurde festgestellt, dass der Nettomietzins für die Vierzimmerwohnung mit Wirkung ab 1. Mai 2001 Fr. 662.-- sowie für die beiden Mansarden je Fr. 121.-- jeweils zuzüglich Nebenkosten betrage. Eine vom Beschwerdeführer gegen dieses Urteil erhobene Beschwerde hiess das Appellationsgericht des Kantons Basel-Stadt mit Urteil vom 16. August 2002 gut, hob das Urteil des Zivilgerichtspräsidenten vom 12. Juli 2001 auf, wies die Klage ab und stellte fest, dass die am 11. September 2000 per 1. Mai 2001 angekündigten Mietzinserhöhungen für die Vierzimmerwohnung und für die beiden Mansarden unzulässig bzw. nichtig seien. Gegen dieses Urteil erhob die Beschwerdegegnerin Berufung ans Bundesgericht und beanstandete die Feststellung der Nichtigkeit der Mietzinserhöhung für die Vierzimmerwohnung; in Bezug auf die Mansardenzimmer blieb das Urteil des Appellationsgerichtes vom 16. August 2002 unangefochten. Mit Urteil vom 31. Januar 2003 hiess das Bundesgericht die Berufung teilweise gut, hob das Urteil des Appellationsgerichtes des Kantons Basel-Stadt vom 16. August 2002 auf und wies die Sache zur Neuentscheidung ans Appellationsgericht zurück (4C.330/2002, publ. in MRA 2003 S. 39 ff.). Im Anschluss daran hiess das Appellationsgericht die Beschwerde des Beschwerdeführers mit Urteil vom 26. März 2003 teilweise gut und erklärte die Mietzinserhöhungen für die beiden Einzimmerwohnungen bzw. Mansarden für ungültig. Im Übrigen wurde die Beschwerde abgewiesen und das Urteil des Zivilgerichtspräsidenten insoweit bestätigt, als es einen Mietzins ab 1. Mai 2001 von Fr. 662.-- für die Vierzimmerwohnung als nicht missbräuchlich bezeichnete.
C. Mit staatsrechtlicher Beschwerde vom 13. Juni 2003 beantragt der Beschwerdeführer dem Bundesgericht, das Urteil des Appellationsgerichtes vom 26. März 2003 sei insoweit aufzuheben, als damit seine Beschwerde abgewiesen und das Urteil des Zivilgerichtspräsidenten in Bezug auf die Vierzimmerwohnung bestätigt worden sei.
Die Beschwerdegegnerin beantragt die Abweisung der staatsrechtlichen Beschwerde, soweit darauf einzutreten sei. Das Appellationsgericht schliesst auf Abweisung der Beschwerde.
Die Beschwerdegegnerin beantragt die Abweisung der staatsrechtlichen Beschwerde, soweit darauf einzutreten sei. Das Appellationsgericht schliesst auf Abweisung der Beschwerde.
D. In der gleichen Sache gelangt der Beschwerdeführer auch mit Berufung ans Bundesgericht.
Das Bundesgericht zieht in Erwägung:
Das Bundesgericht zieht in Erwägung:
1. Erhebt eine Partei gleichzeitig staatsrechtliche Beschwerde und Berufung, so ist in der Regel zuerst über die staatsrechtliche Beschwerde zu befinden, und der Entscheid über die Berufung wird ausgesetzt (Art. 57 Abs. 5 OG). Der Verfahrensantrag des Beschwerdeführers, die Beschwerde und Berufung seien entsprechend BGE 111 II 398 ff. ausnahmsweise gleichzeitig zu beurteilen, ist abzuweisen. Während im erwähnten Fall weder auf die Berufung noch auf die Beschwerde einzutreten war, weil nur eine von mehreren selbständigen Begründungen im angefochtenen Urteil beanstandet worden war, können die Rechtsmittel im vorliegenden Fall nicht mit der identischen Begründung erledigt werden. Es rechtfertigt sich daher, entsprechend dem erwähnten Grundsatz zunächst die Beschwerde und alsdann die Berufung zu behandeln.
1. Erhebt eine Partei gleichzeitig staatsrechtliche Beschwerde und Berufung, so ist in der Regel zuerst über die staatsrechtliche Beschwerde zu befinden, und der Entscheid über die Berufung wird ausgesetzt (Art. 57 Abs. 5 OG). Der Verfahrensantrag des Beschwerdeführers, die Beschwerde und Berufung seien entsprechend BGE 111 II 398 ff. ausnahmsweise gleichzeitig zu beurteilen, ist abzuweisen. Während im erwähnten Fall weder auf die Berufung noch auf die Beschwerde einzutreten war, weil nur eine von mehreren selbständigen Begründungen im angefochtenen Urteil beanstandet worden war, können die Rechtsmittel im vorliegenden Fall nicht mit der identischen Begründung erledigt werden. Es rechtfertigt sich daher, entsprechend dem erwähnten Grundsatz zunächst die Beschwerde und alsdann die Berufung zu behandeln.
2. Der Zivilgerichtspräsident hat in seinem Urteil vom 12. Juli 2001 festgehalten, ein Vergleich der angefochtenen Mietzinserhöhung mit dem vom Statistischen Amt des Kantons Basel-Stadt herausgegebenen "Mietpreisraster" zeige, dass der angefochtene Mietzins derart weit unter den statistisch erhobenen Werten liege, dass von einem missbräuchlichen Mietzins keine Rede sein könne. Dies treffe umso mehr zu, als die Vermieterschaft immerhin fünf ähnliche Objekte zum Vergleich angeboten habe, bei welchen die Mietzinse wesentlich höher lägen als die hier zu beurteilende Mietzinserhöhung.
Das Appellationsgericht hat in seinem Urteil vom 26. März 2003 ausgeführt, dass gemäss Art. 11 Abs. 4 VMWG (SR 221.213.11) bei der Ermittlung der orts- und quartierüblichen Mietzinse amtliche Statistiken berücksichtigt werden dürften. Wenn wie im Fall des Basler "Mietpreisrasters" eine qualitativ gute amtliche Statistik vorliege und der zur Diskussion stehende Mietzins erheblich niedriger als der nach der Statistik übliche Zins sei, müsse davon abgesehen werden können, die vom Bundesgericht verlangte strikte Beweisführung mit mindestens fünf Vergleichobjekten zu verlangen. Wie es sich damit verhalte, könne aber offen gelassen werden, da sich der Zivilgerichtspräsident bei seinem Entscheid nicht nur auf die amtliche Statistik, sondern auch auf fünf von der Beschwerdegegnerin angeführte Vergleichsobjekte gestützt habe. Die vom Beschwerdeführer an den Vergleichsobjekten erhobene pauschale Kritik genüge dem im kantonalen Beschwerdeverfahren geltenden Rügeprinzip nicht. Vielmehr wäre es am Beschwerdeführer gewesen, in der Beschwerde detailliert auszuführen, aus welchen Gründen auf diese Objekte nicht hätte abgestellt werden dürfen. Da die fünf Vergleichsobjekte nicht substanziiert beanstandet worden seien, sei ohne weitere Prüfung davon auszugehen, dass der Nachweis der Orts- und Quartierüblichkeit schon mit den fünf angeführten Vergleichsobjekten erbracht worden sei. Insgesamt könne von einem missbräuchlichen Mietzins keine Rede sein.
3. 3.1 Soweit der Beschwerdeführer geltend macht, der Zivilgerichtspräsident habe sich in seinem Urteil vom 12. Juli 2001 nicht mit seinen Einwänden zu den Vergleichsobjekten auseinander gesetzt und damit seinen Anspruch auf rechtliches Gehör verletzt, ist auf die Beschwerde nicht einzutreten. Die staatsrechtliche Beschwerde ist nur gegen den letztinstanzlichen kantonalen Entscheid zulässig (Art. 86 Abs. 1 OG). Daran ändert auch das Argument des Beschwerdeführers nichts, das Appellationsgericht habe auf die Erwägungen der Vorinstanz verwiesen, weshalb das Urteil des Zivilgerichtspräsidenten vom 1. Juli 2001 Teil des angefochtenen Urteils geworden sei. Entgegen der Darstellung des Beschwerdeführers hat das Appellationsgericht nicht auf die Begründung des Zivilgerichtspräsidenten "verwiesen", sondern lediglich festgehalten, das erstinstanzliche Urteil sei nicht entsprechend den Bestimmungen des kantonalen Prozessrechtes substanziiert angefochten worden.
3.2 Ferner ist auf die Beschwerde insoweit nicht einzutreten, als eine willkürliche Anwendung von Art. 269a lit. a OR und Art. 11 VMWG gerügt wird. Die Verletzung von Bundesrecht kann mit Berufung gerügt werden (Art. 43 Abs. 1 OR). Eine staatsrechtliche Beschwerde steht nicht zur Verfügung (Art. 84 Abs. 2 OG).
3.3 Schliesslich erweist sich die Beschwerde auch insoweit als unzulässig, als geltend gemacht wird, das Appellationsgericht hätte nicht auf die amtliche Statistik - im vorliegenden Fall der "Mietpreisraster" der Stadt-Basel - abstellen dürfen, um das orts- und quartierübliche Mietzinsniveau zu bestimmen. Wie sich der orts- und quartierübliche Mietzins bestimmt, ist eine Frage des Bundesrechtes (Art. 269a lit. a OR und Art. 11 VMWG). Wie erwähnt ist die Kritik an der Anwendung von Bundesrecht im Beschwerdeverfahren unzulässig (Art. 84 Abs. 2 OG), weil diese Rüge in der Berufung zu erheben wäre (Art. 43 Abs. 1 OG).
3.3 Schliesslich erweist sich die Beschwerde auch insoweit als unzulässig, als geltend gemacht wird, das Appellationsgericht hätte nicht auf die amtliche Statistik - im vorliegenden Fall der "Mietpreisraster" der Stadt-Basel - abstellen dürfen, um das orts- und quartierübliche Mietzinsniveau zu bestimmen. Wie sich der orts- und quartierübliche Mietzins bestimmt, ist eine Frage des Bundesrechtes (Art. 269a lit. a OR und Art. 11 VMWG). Wie erwähnt ist die Kritik an der Anwendung von Bundesrecht im Beschwerdeverfahren unzulässig (Art. 84 Abs. 2 OG), weil diese Rüge in der Berufung zu erheben wäre (Art. 43 Abs. 1 OG).
4. 4.1 Weiter wirft der Beschwerdeführer dem Appellationsgericht vor, in willkürlicher Weise davon ausgegangen zu sein, dass die vom Beschwerdeführer an den Vergleichsobjekten erhobene pauschale Kritik dem im kantonalen Beschwerdeverfahren geltenden Rügeprinzip nicht genüge. Da der Zivilgerichtspräsident offensichtlich gar nicht auf die fünf Vergleichsobjekte abgestellt habe, sei es unlogisch und widersprüchlich, vom Beschwerdeführer im kantonalen Beschwerdeverfahren konkrete und substanziierte Beanstandungen der fünf Vergleichsobjekte zu verlangen.
4.2 Dazu ist zu bemerken, dass der Zivilgerichtspräsident entgegen der Darstellung des Beschwerdeführers für die Beurteilung der orts- und quartierüblichen Mietzinse unter anderem nebst der amtlichen Statistik auch auf die fünf Vergleichsobjekte abgestellt hat. Nachdem der Zivilgerichtspräsident festgehalten hatte, dass der angefochtene Mietzins aufgrund eines Vergleiches mit der amtlichen Statistik offensichtlich nicht missbräuchlich sei, führte er weiter aus, dies treffe umso mehr zu, als die Beschwerdegegnerin immerhin fünf ähnliche Objekte zum Vergleich angeboten habe, bei welchen die Mietzinsen wesentliche höher lägen als die umstrittene Mietzinserhöhung. Da der Zivilgerichtspräsident im Sinn einer kumulativen Begründung ("Dies trifft umso mehr zu...") auf die fünf Vergleichsobjekte abgestellt hat, hätte im kantonalen Beschwerdeverfahren Anlass zu einer substanziierten Beanstandung der fünf Vergleichsobjekte bestanden. Von einer willkürlichen Anwendung von kantonalem Prozessrecht - und damit einer Verletzung von Art. 9 BV - kann unter diesen Umständen keine Rede sein. Inwiefern der Gehörsanspruch - und damit Art. 29 Abs. 2 BV - in diesem Zusammenhang verletzt worden sein soll, ist nicht ersichtlich.
4.2 Dazu ist zu bemerken, dass der Zivilgerichtspräsident entgegen der Darstellung des Beschwerdeführers für die Beurteilung der orts- und quartierüblichen Mietzinse unter anderem nebst der amtlichen Statistik auch auf die fünf Vergleichsobjekte abgestellt hat. Nachdem der Zivilgerichtspräsident festgehalten hatte, dass der angefochtene Mietzins aufgrund eines Vergleiches mit der amtlichen Statistik offensichtlich nicht missbräuchlich sei, führte er weiter aus, dies treffe umso mehr zu, als die Beschwerdegegnerin immerhin fünf ähnliche Objekte zum Vergleich angeboten habe, bei welchen die Mietzinsen wesentliche höher lägen als die umstrittene Mietzinserhöhung. Da der Zivilgerichtspräsident im Sinn einer kumulativen Begründung ("Dies trifft umso mehr zu...") auf die fünf Vergleichsobjekte abgestellt hat, hätte im kantonalen Beschwerdeverfahren Anlass zu einer substanziierten Beanstandung der fünf Vergleichsobjekte bestanden. Von einer willkürlichen Anwendung von kantonalem Prozessrecht - und damit einer Verletzung von Art. 9 BV - kann unter diesen Umständen keine Rede sein. Inwiefern der Gehörsanspruch - und damit Art. 29 Abs. 2 BV - in diesem Zusammenhang verletzt worden sein soll, ist nicht ersichtlich.
5. Aus diesen Gründen erweist sich die staatsrechtliche Beschwerde als unbegründet, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 156 Abs. 1 und Art. 159 Abs. 2 OG).
Demnach erkennt das Bundesgericht:
Demnach erkennt das Bundesgericht:
1. Die staatsrechtliche Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
1. Die staatsrechtliche Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtsgebühr von Fr. 2'000.-- wird dem Beschwerdeführer auferlegt.
2. Die Gerichtsgebühr von Fr. 2'000.-- wird dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
3. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 13. Januar 2004
Im Namen der I. Zivilabteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: